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