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