Scippy

SCIP

Solving Constraint Integer Programs

struct_cons.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-2014 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_cons.h
17  * @brief datastructures for constraints and constraint handlers
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __SCIP_STRUCT_CONS_H__
24 #define __SCIP_STRUCT_CONS_H__
25 
26 #include "scip/def.h"
27 #include "scip/type_clock.h"
28 #include "scip/type_cons.h"
29 
30 
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34 
35 /** constraint data structure */
36 struct SCIP_Cons
37 {
38 #ifndef NDEBUG
39  SCIP* scip; /**< SCIP data structure */
40 #endif
41  SCIP_Real age; /**< age of constraint: number of successive times, the constraint was irrelevant */
42  char* name; /**< name of the constraint */
43  SCIP_CONSHDLR* conshdlr; /**< constraint handler for this constraint */
44  SCIP_CONSDATA* consdata; /**< data for this specific constraint */
45  SCIP_CONS* transorigcons; /**< for original constraints: associated transformed constraint or NULL,
46  * for transformed constraints: associated original constraint or NULL */
47  SCIP_CONSSETCHG* addconssetchg; /**< constraint change that added constraint to current subproblem, or NULL if
48  * constraint is from global problem */
49  int addarraypos; /**< position of constraint in the conssetchg's/prob's addedconss/conss array */
50  int consspos; /**< position of constraint in the handler's conss array */
51  int initconsspos; /**< position of constraint in the handler's initconss array */
52  int sepaconsspos; /**< position of constraint in the handler's sepaconss array */
53  int enfoconsspos; /**< position of constraint in the handler's enfoconss array */
54  int checkconsspos; /**< position of constraint in the handler's checkconss array */
55  int propconsspos; /**< position of constraint in the handler's propconss array */
56  int nlockspos; /**< number of times, the constraint locked rounding of its variables */
57  int nlocksneg; /**< number of times, the constraint locked vars for the constraint's negation */
58  int activedepth; /**< depth level of constraint activation (-2: inactive, -1: problem constraint) */
59  int validdepth; /**< depth level where constraint is valid (-1: equals activedepth) */
60  int nuses; /**< number of times, this constraint is referenced */
61  unsigned int markedprop:1; /**< TRUE iff the constraint is marked to be propagated during the next node processing */
62  unsigned int initial:1; /**< TRUE iff LP relaxation of constraint should be in initial LP, if possible */
63  unsigned int separate:1; /**< TRUE iff constraint should be separated during LP processing */
64  unsigned int enforce:1; /**< TRUE iff constraint should be enforced during node processing */
65  unsigned int check:1; /**< TRUE iff constraint should be checked for feasibility */
66  unsigned int propagate:1; /**< TRUE iff constraint should be propagated during node processing */
67  unsigned int sepaenabled:1; /**< TRUE iff constraint should be separated in the next separation call */
68  unsigned int propenabled:1; /**< TRUE iff constraint should be propagated in the next propagation call */
69  unsigned int local:1; /**< TRUE iff constraint is only valid locally */
70  unsigned int modifiable:1; /**< TRUE iff constraint is modifiable (subject to column generation) */
71  unsigned int dynamic:1; /**< TRUE iff constraint is subject to aging */
72  unsigned int removable:1; /**< TRUE iff relaxation should be removed from the LP due to aging or cleanup */
73  unsigned int stickingatnode:1; /**< TRUE iff the node should always be kept at the node where it was added */
74  unsigned int original:1; /**< TRUE iff constraint belongs to original problem */
75  unsigned int deleteconsdata:1; /**< TRUE iff constraint data has to be deleted if constraint is freed */
76  unsigned int active:1; /**< TRUE iff constraint is active in the current node; a constraint is
77  * active if it is global and was not removed during presolving or it was
78  * added locally (in that case the local flag is TRUE) and the current
79  * node belongs to the corresponding sub tree
80  */
81  unsigned int enabled:1; /**< TRUE iff constraint is enforced, separated, and propagated in current node */
82  unsigned int obsolete:1; /**< TRUE iff constraint is too seldomly used and therefore obsolete */
83  unsigned int markpropagate:1; /**< TRUE iff constraint is marked to be propagated in the next round */
84  unsigned int deleted:1; /**< TRUE iff constraint was globally deleted */
85  unsigned int update:1; /**< TRUE iff constraint has to be updated in update phase */
86  unsigned int updateinsert:1; /**< TRUE iff constraint has to be inserted in the conss array */
87  unsigned int updateactivate:1; /**< TRUE iff constraint has to be activated in update phase */
88  unsigned int updatedeactivate:1; /**< TRUE iff constraint has to be deactivated in update phase */
89  unsigned int updateenable:1; /**< TRUE iff constraint has to be enabled in update phase */
90  unsigned int updatedisable:1; /**< TRUE iff constraint has to be disabled in update phase */
91  unsigned int updatesepaenable:1; /**< TRUE iff constraint's separation has to be enabled in update phase */
92  unsigned int updatesepadisable:1;/**< TRUE iff constraint's separation has to be disabled in update phase */
93  unsigned int updatepropenable:1; /**< TRUE iff constraint's propagation has to be enabled in update phase */
94  unsigned int updatepropdisable:1;/**< TRUE iff constraint's propagation has to be disabled in update phase */
95  unsigned int updateobsolete:1; /**< TRUE iff obsolete status of constraint has to be updated in update phase */
96  unsigned int updatefree:1; /**< TRUE iff constraint has to be freed in update phase */
97  unsigned int updateactfocus:1; /**< TRUE iff delayed constraint activation happened at focus node */
98  unsigned int updatemarkpropagate:1;/**< TRUE iff constraint has to be marked to be propagated in update phase */
99  unsigned int updateunmarkpropagate:1;/**< TRUE iff constraint has to be unmarked to be propagated in update phase */
100  unsigned int nupgradelocks:29; /**< number of times, a constraint is locked against an upgrade
101  * (e.g. linear -> logicor), 0 means a constraint can be upgraded */
102 };
103 
104 /** tracks additions and removals of the set of active constraints */
105 struct SCIP_ConsSetChg
106 {
107  SCIP_CONS** addedconss; /**< constraints added to the set of active constraints */
108  SCIP_CONS** disabledconss; /**< constraints disabled in the set of active constraints */
109  int addedconsssize; /**< size of added constraints array */
110  int naddedconss; /**< number of added constraints */
111  int disabledconsssize; /**< size of disabled constraints array */
112  int ndisabledconss; /**< number of disabled constraints */
113 };
114 
115 /** constraint handler */
116 struct SCIP_Conshdlr
117 {
118  SCIP_Longint nsepacalls; /**< number of times, the separator was called */
119  SCIP_Longint nenfolpcalls; /**< number of times, the LP enforcer was called */
120  SCIP_Longint nenfopscalls; /**< number of times, the pseudo enforcer was called */
121  SCIP_Longint npropcalls; /**< number of times, the propagator was called */
122  SCIP_Longint ncheckcalls; /**< number of times, the feasibility check was called */
123  SCIP_Longint nrespropcalls; /**< number of times, the resolve propagation was called */
124  SCIP_Longint ncutoffs; /**< number of cutoffs found so far by this constraint handler */
125  SCIP_Longint ncutsfound; /**< number of cuts found by this constraint handler */
126  SCIP_Longint ncutsapplied; /**< number of cuts found by this constraint handler applied to lp */
127  SCIP_Longint nconssfound; /**< number of additional constraints added by this constraint handler */
128  SCIP_Longint ndomredsfound; /**< number of domain reductions found so far by this constraint handler */
129  SCIP_Longint nchildren; /**< number of children the constraint handler created during branching */
130  SCIP_Longint lastpropdomchgcount;/**< last bound change number, where the domain propagation was called */
131  SCIP_Longint storedpropdomchgcount;/**< bound change number, where the domain propagation was called last before starting probing */
132  SCIP_Longint lastenfolpdomchgcount;/**< last bound change number, where the LP enforcement was called */
133  SCIP_Longint lastenfopsdomchgcount;/**< last bound change number, where the pseudo enforcement was called */
134  SCIP_Longint lastenfolpnode; /**< last node at which the LP enforcement was called */
135  SCIP_Longint lastenfopsnode; /**< last node at which the pseudo enforcement was called */
136  SCIP_RESULT lastenfolpresult; /**< result of last LP enforcement call */
137  SCIP_RESULT lastenfopsresult; /**< result of last pseudo enforcement call */
138  SCIP_Real ageresetavg; /**< exp. decaying weighted average of constraint ages at moment of age reset */
139  char* name; /**< name of constraint handler */
140  char* desc; /**< description of constraint handler */
141  SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)); /**< copy method of constraint handler or NULL if you don't want to copy your plugin into sub-SCIPs */
142  SCIP_DECL_CONSFREE ((*consfree)); /**< destructor of constraint handler */
143  SCIP_DECL_CONSINIT ((*consinit)); /**< initialize constraint handler */
144  SCIP_DECL_CONSEXIT ((*consexit)); /**< deinitialize constraint handler */
145  SCIP_DECL_CONSINITPRE ((*consinitpre)); /**< presolving initialization method of constraint handler */
146  SCIP_DECL_CONSEXITPRE ((*consexitpre)); /**< presolving deinitialization method of constraint handler */
147  SCIP_DECL_CONSINITSOL ((*consinitsol)); /**< solving process initialization method of constraint handler */
148  SCIP_DECL_CONSEXITSOL ((*consexitsol)); /**< solving process deinitialization method of constraint handler */
149  SCIP_DECL_CONSDELETE ((*consdelete)); /**< free specific constraint data */
150  SCIP_DECL_CONSTRANS ((*constrans)); /**< transform constraint data into data belonging to the transformed problem */
151  SCIP_DECL_CONSINITLP ((*consinitlp)); /**< initialize LP with relaxations of "initial" constraints */
152  SCIP_DECL_CONSSEPALP ((*conssepalp)); /**< separate cutting planes for LP solution */
153  SCIP_DECL_CONSSEPASOL ((*conssepasol)); /**< separate cutting planes for arbitrary primal solution */
154  SCIP_DECL_CONSENFOLP ((*consenfolp)); /**< enforcing constraints for LP solutions */
155  SCIP_DECL_CONSENFOPS ((*consenfops)); /**< enforcing constraints for pseudo solutions */
156  SCIP_DECL_CONSCHECK ((*conscheck)); /**< check feasibility of primal solution */
157  SCIP_DECL_CONSPROP ((*consprop)); /**< propagate variable domains */
158  SCIP_DECL_CONSPRESOL ((*conspresol)); /**< presolving method */
159  SCIP_DECL_CONSRESPROP ((*consresprop)); /**< propagation conflict resolving method */
160  SCIP_DECL_CONSLOCK ((*conslock)); /**< variable rounding lock method */
161  SCIP_DECL_CONSACTIVE ((*consactive)); /**< activation notification method */
162  SCIP_DECL_CONSDEACTIVE((*consdeactive)); /**< deactivation notification method */
163  SCIP_DECL_CONSENABLE ((*consenable)); /**< enabling notification method */
164  SCIP_DECL_CONSDISABLE ((*consdisable)); /**< disabling notification method */
165  SCIP_DECL_CONSDELVARS ((*consdelvars)); /**< variable deletion method */
166  SCIP_DECL_CONSPRINT ((*consprint)); /**< constraint display method */
167  SCIP_DECL_CONSCOPY ((*conscopy)); /**< constraint copying method */
168  SCIP_DECL_CONSPARSE ((*consparse)); /**< constraint parsing method */
169  SCIP_DECL_CONSGETVARS ((*consgetvars)); /**< constraint get variables method */
170  SCIP_DECL_CONSGETNVARS((*consgetnvars)); /**< constraint get number of variable method */
171  SCIP_CONSHDLRDATA* conshdlrdata; /**< constraint handler data */
172  SCIP_CONS** conss; /**< array with all transformed constraints, active ones preceed inactive
173  * ones; a constraint is active if it is global and was not removed
174  * during presolving or it was added locally (in that case the local flag
175  * is TRUE) and the current node belongs to the corresponding sub tree */
176  SCIP_CONS** initconss; /**< array with active constraints that must enter the LP with their initial representation */
177  SCIP_CONS** sepaconss; /**< array with active constraints that must be separated during LP processing */
178  SCIP_CONS** enfoconss; /**< array with active constraints that must be enforced during node processing */
179  SCIP_CONS** checkconss; /**< array with active constraints that must be checked for feasibility */
180  SCIP_CONS** propconss; /**< array with active constraints that must be propagated during node processing */
181  SCIP_CONS** storedpropconss; /**< array to store constraints that were marked for propagation before
182  * starting probing mode
183  */
184  SCIP_CONS** updateconss; /**< array with constraints that changed and have to be update in the handler */
185  SCIP_CLOCK* setuptime; /**< time spend for setting up this constraint handler for the next stages */
186  SCIP_CLOCK* presoltime; /**< time used for presolving of this constraint handler */
187  SCIP_CLOCK* sepatime; /**< time used for separation of this constraint handler */
188  SCIP_CLOCK* enfolptime; /**< time used for LP enforcement of this constraint handler */
189  SCIP_CLOCK* enfopstime; /**< time used for pseudo enforcement of this constraint handler */
190  SCIP_CLOCK* proptime; /**< time used for propagation of this constraint handler */
191  SCIP_CLOCK* sbproptime; /**< time used for propagation of this constraint handler during strong branching */
192  SCIP_CLOCK* checktime; /**< time used for feasibility check of this constraint handler */
193  SCIP_CLOCK* resproptime; /**< time used for resolve propagation of this constraint handler */
194  SCIP_Longint lastsepalpcount; /**< last LP number, where the separations was called */
195  SCIP_Longint lastenfolplpcount; /**< last LP number, where the LP enforcement was called */
196  int sepapriority; /**< priority of the constraint handler for separation */
197  int enfopriority; /**< priority of the constraint handler for constraint enforcing */
198  int checkpriority; /**< priority of the constraint handler for checking infeasibility */
199  int sepafreq; /**< frequency for separating cuts; zero means to separate only in the root node */
200  int propfreq; /**< frequency for propagating domains; zero means only preprocessing propagation */
201  int eagerfreq; /**< frequency for using all instead of only the useful constraints in separation,
202  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
203  int maxprerounds; /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
204  int consssize; /**< size of conss array */
205  int nconss; /**< total number of constraints */
206  int nactiveconss; /**< total number of active constraints */
207  int maxnactiveconss; /**< maximal number of active constraints existing at the same time */
208  int startnactiveconss; /**< number of active constraints existing when problem solving started */
209  int initconsssize; /**< size of initconss array */
210  int ninitconss; /**< number of active constraints that must enter the LP */
211  int ninitconsskept; /**< number of active constraints that must enter the LP, but were not initialized at
212  * their valid node, so that they have to be initialized at every node at which they
213  * are active; these constraints come first in the initconss array */
214  int sepaconsssize; /**< size of sepaconss array */
215  int nsepaconss; /**< number of active constraints that may be separated during LP processing */
216  int nusefulsepaconss; /**< number of non-obsolete active constraints that should be separated */
217  int enfoconsssize; /**< size of enfoconss array */
218  int nenfoconss; /**< number of active constraints that must be enforced during node processing */
219  int nusefulenfoconss; /**< number of non-obsolete active constraints that must be enforced */
220  int checkconsssize; /**< size of checkconss array */
221  int ncheckconss; /**< number of active constraints that must be checked for feasibility */
222  int nusefulcheckconss; /**< number of non-obsolete active constraints that must be checked */
223  int propconsssize; /**< size of propconss array */
224  int npropconss; /**< number of active constraints that may be propagated during node processing */
225  int nmarkedpropconss; /**< number of active constraints which are marked to be propagated in the next round */
226  int nusefulpropconss; /**< number of non-obsolete active constraints that should be propagated */
227  int storedpropconsssize;/**< size of array for storing away marked propagation constraints */
228  int storednmarkedpropconss;/**< number of marked propagation constraints that are stored away */
229  int updateconsssize; /**< size of updateconss array */
230  int nupdateconss; /**< number of update constraints */
231  int nenabledconss; /**< total number of enabled constraints of the handler */
232  int lastnusefulpropconss;/**< number of already propagated useful constraints on current domains */
233  int lastnusefulsepaconss;/**< number of already separated useful constraints on current solution */
234  int lastnusefulenfoconss;/**< number of already enforced useful constraints on current solution */
235  int lastnfixedvars; /**< number of variables fixed before the last call to the presolver */
236  int lastnaggrvars; /**< number of variables aggregated before the last call to the presolver */
237  int lastnchgvartypes; /**< number of variable type changes before the last call to the presolver */
238  int lastnchgbds; /**< number of variable bounds tightened before the last call to the presolver */
239  int lastnaddholes; /**< number of domain holes added before the last call to the presolver */
240  int lastndelconss; /**< number of deleted constraints before the last call to the presolver */
241  int lastnaddconss; /**< number of added constraints before the last call to the presolver */
242  int lastnupgdconss; /**< number of upgraded constraints before the last call to the presolver */
243  int lastnchgcoefs; /**< number of changed coefficients before the last call to the presolver */
244  int lastnchgsides; /**< number of changed left or right hand sides before the last call to the presolver */
245  int nfixedvars; /**< total number of variables fixed by this presolver */
246  int naggrvars; /**< total number of variables aggregated by this presolver */
247  int nchgvartypes; /**< total number of variable type changes by this presolver */
248  int nchgbds; /**< total number of variable bounds tightened by this presolver */
249  int naddholes; /**< total number of domain holes added by this presolver */
250  int ndelconss; /**< total number of deleted constraints by this presolver */
251  int naddconss; /**< total number of added constraints by this presolver */
252  int nupgdconss; /**< total number of upgraded constraints by this presolver */
253  int nchgcoefs; /**< total number of changed coefficients by this presolver */
254  int nchgsides; /**< total number of changed left or right hand sides by this presolver */
255  int npresolcalls; /**< number of times the constraint handler was called in presolving and tried to find reductions */
256  int delayupdatecount; /**< must the updates of the constraint arrays be delayed until processUpdates()? */
257  SCIP_Bool delaysepa; /**< should separation method be delayed, if other separators found cuts? */
258  SCIP_Bool delayprop; /**< should propagation method be delayed, if other propagators found reductions? */
259  SCIP_Bool delaypresol; /**< should presolving method be delayed, if other presolvers found reductions? */
260  SCIP_Bool needscons; /**< should the constraint handler be skipped, if no constraints are available? */
261  SCIP_Bool sepalpwasdelayed; /**< was the LP separation method delayed at the last call? */
262  SCIP_Bool sepasolwasdelayed; /**< was the SOL separation method delayed at the last call? */
263  SCIP_Bool propwasdelayed; /**< was the propagation method delayed at the last call? */
264  SCIP_Bool presolwasdelayed; /**< was the presolving method delayed at the last call? */
265  SCIP_Bool initialized; /**< is constraint handler initialized? */
266  SCIP_Bool duringsepa; /**< is the constraint handler currently performing separation? */
267  SCIP_Bool duringprop; /**< is the constraint handler currently performing propagation? */
268  SCIP_PROPTIMING timingmask; /**< positions in the node solving loop where propagation method of constraint handlers should be executed */
269 
270  SCIP_QUEUE* pendingconss; /**< queue of pending constraints */
271 };
272 
273 #ifdef __cplusplus
274 }
275 #endif
276 
277 #endif
278