Scippy

SCIP

Solving Constraint Integer Programs

struct_conflict.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file struct_conflict.h
17  * @ingroup INTERNALAPI
18  * @brief datastructures for conflict analysis
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_STRUCT_CONFLICT_H__
25 #define __SCIP_STRUCT_CONFLICT_H__
26 
27 
28 #include "scip/def.h"
29 #include "scip/type_clock.h"
30 #include "scip/type_misc.h"
31 #include "scip/type_var.h"
32 #include "scip/type_conflict.h"
33 #include "lpi/type_lpi.h"
34 
35 #ifdef __cplusplus
36 extern "C" {
37 #endif
38 
39 /** conflict handler */
41 {
42  char* name; /**< name of conflict handler */
43  char* desc; /**< description of conflict handler */
44  SCIP_DECL_CONFLICTCOPY((*conflictcopy)); /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */
45  SCIP_DECL_CONFLICTFREE((*conflictfree)); /**< destructor of conflict handler */
46  SCIP_DECL_CONFLICTINIT((*conflictinit)); /**< initialize conflict handler */
47  SCIP_DECL_CONFLICTEXIT((*conflictexit)); /**< deinitialize conflict handler */
48  SCIP_DECL_CONFLICTINITSOL((*conflictinitsol));/**< solving process initialization method of conflict handler */
49  SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol));/**< solving process deinitialization method of conflict handler */
50  SCIP_DECL_CONFLICTEXEC((*conflictexec)); /**< conflict processing method of conflict handler */
51  SCIP_CONFLICTHDLRDATA* conflicthdlrdata; /**< conflict handler data */
52  SCIP_CLOCK* setuptime; /**< time spend for setting up this conflict handler for the next stages */
53  SCIP_CLOCK* conflicttime; /**< conflict handler execution time */
54  int priority; /**< priority of the conflict handler */
55  SCIP_Bool initialized; /**< is conflict handler initialized? */
56 };
57 
58 /** set of conflicting bound changes */
60 {
61  SCIP_BDCHGINFO** bdchginfos; /**< bound change informations of the conflict set */
62  SCIP_BDCHGINFO* confbdchginfo; /**< a bound change at the conflict depth */
63  SCIP_Real* relaxedbds; /**< array of relaxed bounds which are efficient for a valid conflict */
64  SCIP_Real confrelaxedbd; /**< relaxed bound belonging the the bound change at the conflict depth */
65  int* sortvals; /**< aggregated var index/bound type values for sorting */
66  int bdchginfossize; /**< size of bdchginfos array */
67  int nbdchginfos; /**< number of bound change informations in the conflict set */
68  int validdepth; /**< depth in the tree where the conflict set is valid */
69  int insertdepth; /**< depth level where constraint should be added */
70  int conflictdepth; /**< depth in the tree where the conflict set yields a conflict */
71  int repropdepth; /**< depth at which the conflict set triggers a deduction */
72  unsigned int repropagate:1; /**< should the conflict constraint trigger a repropagation? */
73  unsigned int depthcalced:1; /**< are the conflict and repropagation depth calculated? */
74  unsigned int sorted:1; /**< is the conflict set sorted */
75  unsigned int usescutoffbound:1; /**< is the conflict based on the cutoff bound? */
76  SCIP_CONFTYPE conflicttype; /**< conflict type: unknown, infeasible LP, bound exceeding LP, propagation */
77 };
78 
79 /** set of LP bound change */
81 {
82  int* bdchginds; /**< array of column indices */
83  SCIP_Real* bdchglbs; /**< array of lower bounds */
84  SCIP_Real* bdchgubs; /**< array of upper bounds */
85  int* bdchgcolinds; /**< array of ???????????? */
86  SCIP_Bool* usedcols; /**< array to mark if a column is used */
87  int nbdchgs; /**< number of stored LP bound changes */
88 };
89 
90 /** conflict analysis data structure */
92 {
93  SCIP_Longint nglbchgbds; /**< total number of applied global bound changes */
94  SCIP_Longint nappliedglbconss; /**< total number of conflict constraints added globally to the problem */
95  SCIP_Longint nappliedglbliterals;/**< total number of literals in globally applied conflict constraints */
96  SCIP_Longint nlocchgbds; /**< total number of applied local bound changes */
97  SCIP_Longint nappliedlocconss; /**< total number of conflict constraints added locally to the problem */
98  SCIP_Longint nappliedlocliterals;/**< total number of literals in locally applied conflict constraints */
99  SCIP_Longint npropcalls; /**< number of calls to propagation conflict analysis */
100  SCIP_Longint npropsuccess; /**< number of calls yielding at least one conflict constraint */
101  SCIP_Longint npropconfconss; /**< number of valid conflict constraints detected in propagation conflict analysis */
102  SCIP_Longint npropconfliterals; /**< total number of literals in valid propagation conflict constraints */
103  SCIP_Longint npropreconvconss; /**< number of reconvergence constraints detected in propagation conflict analysis */
104  SCIP_Longint npropreconvliterals;/**< total number of literals in valid propagation reconvergence constraints */
105  SCIP_Longint ninflpcalls; /**< number of calls to infeasible LP conflict analysis */
106  SCIP_Longint ninflpsuccess; /**< number of calls yielding at least one conflict constraint */
107  SCIP_Longint ninflpconfconss; /**< number of valid conflict constraints detected in infeasible LP conflict
108  * analysis */
109  SCIP_Longint ninflpconfliterals; /**< total number of literals in valid infeasible LP conflict constraints */
110  SCIP_Longint ninflpreconvconss; /**< number of reconvergence constraints detected in infeasible LP conflict
111  * analysis */
112  SCIP_Longint ninflpreconvliterals; /**< total number of literals in valid infeasible LP reconvergence
113  * constraints */
114  SCIP_Longint ninflpiterations; /**< total number of LP iterations used in infeasible LP conflict analysis */
115  SCIP_Longint nboundlpcalls; /**< number of calls to bound exceeding LP conflict analysis */
116  SCIP_Longint nboundlpsuccess; /**< number of calls yielding at least one conflict constraint */
117  SCIP_Longint nboundlpconfconss; /**< number of valid conflict constraints detected in bound exceeding LP
118  * conflict analysis */
119  SCIP_Longint nboundlpconfliterals; /**< total number of literals in valid bound exceeding LP conflict
120  * constraints */
121  SCIP_Longint nboundlpreconvconss;/**< number of reconvergence constraints detected in bound exceeding LP
122  * conflict analysis */
123  SCIP_Longint nboundlpreconvliterals; /**< total number of literals in valid bound exceeding LP reconvergence
124  * constraints */
125  SCIP_Longint nboundlpiterations; /**< total number of LP iterations used in bound exceeding LP conflict
126  * analysis */
127  SCIP_Longint nsbcalls; /**< number of calls to infeasible strong branching conflict analysis */
128  SCIP_Longint nsbsuccess; /**< number of calls yielding at least one conflict constraint */
129  SCIP_Longint nsbconfconss; /**< number of conflict constraints detected in strong branching conflict analysis */
130  SCIP_Longint nsbconfliterals; /**< total number of literals in valid strong branching conflict constraints */
131  SCIP_Longint nsbreconvconss; /**< number of reconvergence constraints detected in strong branch conflict analysis */
132  SCIP_Longint nsbreconvliterals; /**< total number of literals in valid strong branching reconvergence constraints */
133  SCIP_Longint nsbiterations; /**< total number of LP iterations used in strong branching conflict analysis */
134  SCIP_Longint npseudocalls; /**< number of calls to pseudo solution conflict analysis */
135  SCIP_Longint npseudosuccess; /**< number of calls yielding at least one conflict constraint */
136  SCIP_Longint npseudoconfconss; /**< number of valid conflict constraints detected in pseudo sol conflict analysis */
137  SCIP_Longint npseudoconfliterals;/**< total number of literals in valid pseudo solution conflict constraints */
138  SCIP_Longint npseudoreconvconss; /**< number of reconvergence constraints detected in pseudo sol conflict analysis */
139  SCIP_Longint npseudoreconvliterals;/**< total number of literals in valid pseudo solution reconvergence constraints */
140  SCIP_Longint ndualrayinfglobal; /**< number of dual ray constraints added globally */
141  SCIP_Longint ndualrayinfsuccess; /**< number of successfully dual ray analysis calls for infeasible LPs */
142  SCIP_Longint ndualrayinfseparoot;/**< number of infeasible dual rays separating the root LP solution */
143 
144  SCIP_Longint dualrayinfnnonzeros;/**< number of non-zeros over all accepted dual rays */
145 
146  SCIP_CLOCK* dIBclock; /**< time used for detect implied bounds */
147 
148  SCIP_CLOCK* propanalyzetime; /**< time used for propagation conflict analysis */
149  SCIP_CLOCK* inflpanalyzetime; /**< time used for infeasible LP conflict analysis */
150  SCIP_CLOCK* boundlpanalyzetime; /**< time used for bound exceeding LP conflict analysis */
151  SCIP_CLOCK* sbanalyzetime; /**< time used for strong branching LP conflict analysis */
152  SCIP_CLOCK* pseudoanalyzetime; /**< time used for pseudo solution conflict analysis */
153  SCIP_PQUEUE* bdchgqueue; /**< unprocessed conflict bound changes */
154  SCIP_PQUEUE* forcedbdchgqueue; /**< unprocessed conflict bound changes that must be resolved */
155  SCIP_CONFLICTSET* conflictset; /**< bound changes resembling the current conflict set */
156  SCIP_CONFLICTSET** conflictsets; /**< conflict sets found at the current node */
157  SCIP_Real* conflictsetscores; /**< score values of the conflict sets found at the current node */
158  SCIP_BDCHGINFO** tmpbdchginfos; /**< temporarily created bound change information data */
159  int conflictsetssize; /**< size of conflictsets array */
160  int nconflictsets; /**< number of available conflict sets (used slots in conflictsets array) */
161  int tmpbdchginfossize; /**< size of tmpbdchginfos array */
162  int ntmpbdchginfos; /**< number of temporary created bound change information data */
163  int count; /**< conflict set counter to label binary conflict variables with */
164 };
165 
166 #ifdef __cplusplus
167 }
168 #endif
169 
170 #endif
SCIP_CLOCK * propanalyzetime
unsigned int sorted
SCIP_Longint ninflpconfliterals
unsigned int repropagate
SCIP_Longint ninflpreconvconss
type definitions for miscellaneous datastructures
SCIP_Real confrelaxedbd
SCIP_PQUEUE * bdchgqueue
SCIP_Longint nsbcalls
SCIP_Longint nappliedlocliterals
SCIP_CLOCK * inflpanalyzetime
SCIP_Real * bdchgubs
SCIP_Longint nappliedglbliterals
SCIP_Longint npseudoreconvliterals
SCIP_Longint npropconfliterals
SCIP_Longint nappliedglbconss
SCIP_Longint npseudoreconvconss
SCIP_Longint nlocchgbds
SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))
SCIP_DECL_CONFLICTCOPY((*conflictcopy))
SCIP_Real * relaxedbds
SCIP_Longint npropcalls
SCIP_Longint dualrayinfnnonzeros
SCIP_Longint nglbchgbds
SCIP_Real * bdchglbs
SCIP_Longint npropsuccess
SCIP_DECL_CONFLICTEXEC((*conflictexec))
SCIP_Longint nappliedlocconss
SCIP_Longint npseudosuccess
SCIP_Longint ninflpiterations
SCIP_Longint npropreconvliterals
SCIP_Longint npropconfconss
SCIP_Longint nboundlpcalls
SCIP_CLOCK * setuptime
SCIP_CLOCK * pseudoanalyzetime
SCIP_CLOCK * boundlpanalyzetime
SCIP_Longint ninflpreconvliterals
SCIP_BDCHGINFO ** tmpbdchginfos
SCIP_CLOCK * conflicttime
SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))
SCIP_CONFLICTHDLRDATA * conflicthdlrdata
SCIP_Longint npropreconvconss
type definitions for specific LP solvers interface
SCIP_DECL_CONFLICTEXIT((*conflictexit))
SCIP_Longint ninflpcalls
struct SCIP_ConflicthdlrData SCIP_CONFLICTHDLRDATA
Definition: type_conflict.h:40
unsigned int depthcalced
type definitions for problem variables
SCIP_Longint ndualrayinfseparoot
type definitions for conflict analysis
SCIP_CLOCK * sbanalyzetime
SCIP_Longint nboundlpsuccess
SCIP_CONFLICTSET * conflictset
SCIP_Longint nboundlpreconvconss
SCIP_DECL_CONFLICTFREE((*conflictfree))
#define SCIP_Bool
Definition: def.h:61
SCIP_CONFTYPE conflicttype
SCIP_PQUEUE * forcedbdchgqueue
SCIP_Longint ndualrayinfglobal
SCIP_Longint nboundlpreconvliterals
SCIP_Longint nsbconfconss
type definitions for clocks and timing issues
SCIP_Longint nsbconfliterals
SCIP_Longint nboundlpiterations
SCIP_Longint npseudoconfliterals
SCIP_Longint ninflpconfconss
SCIP_Longint nsbsuccess
SCIP_Longint nsbreconvliterals
SCIP_Longint nboundlpconfliterals
SCIP_Real * conflictsetscores
#define SCIP_Real
Definition: def.h:135
enum SCIP_ConflictType SCIP_CONFTYPE
Definition: type_conflict.h:53
SCIP_Longint npseudocalls
SCIP_DECL_CONFLICTINIT((*conflictinit))
SCIP_CLOCK * dIBclock
SCIP_Longint nsbiterations
SCIP_Longint nboundlpconfconss
#define SCIP_Longint
Definition: def.h:120
SCIP_Longint npseudoconfconss
SCIP_BDCHGINFO ** bdchginfos
unsigned int usescutoffbound
SCIP_CONFLICTSET ** conflictsets
common defines and data types used in all packages of SCIP
SCIP_Longint ndualrayinfsuccess
SCIP_BDCHGINFO * confbdchginfo
SCIP_Longint nsbreconvconss
SCIP_Bool * usedcols
SCIP_Longint ninflpsuccess