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_var.h 17 * @ingroup INTERNALAPI 18 * @brief datastructures for problem variables 19 * @author Tobias Achterberg 20 */ 21 22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 23 24 #ifndef __SCIP_STRUCT_VAR_H__ 25 #define __SCIP_STRUCT_VAR_H__ 26 27 28 #include "scip/def.h" 29 #include "scip/type_history.h" 30 #include "scip/type_event.h" 31 #include "scip/type_var.h" 32 #include "scip/type_implics.h" 33 #include "scip/type_cons.h" 34 #include "scip/type_prop.h" 35 #include "scip/type_lp.h" 36 37 #ifdef __cplusplus 38 extern "C" { 39 #endif 40 41 /** hole in a domain */ 42 struct SCIP_Hole 43 { 44 SCIP_Real left; /**< left bound of open interval defining the hole (left,right) */ 45 SCIP_Real right; /**< right bound of open interval defining the hole (left,right) */ 46 }; 47 48 /** list of domain holes */ 49 struct SCIP_Holelist 50 { 51 SCIP_HOLE hole; /**< this hole */ 52 SCIP_HOLELIST* next; /**< next hole in list */ 53 }; 54 55 /** change in a hole list */ 56 struct SCIP_HoleChg 57 { 58 SCIP_HOLELIST** ptr; /**< changed list pointer */ 59 SCIP_HOLELIST* newlist; /**< new value of list pointer */ 60 SCIP_HOLELIST* oldlist; /**< old value of list pointer */ 61 }; 62 63 /** data for branching decision bound changes */ 64 struct SCIP_BranchingData 65 { 66 SCIP_Real lpsolval; /**< sol val of var in last LP prior to bound change, or SCIP_INVALID if unknown */ 67 }; 68 69 /** data for infered bound changes */ 70 struct SCIP_InferenceData 71 { 72 SCIP_VAR* var; /**< variable that was changed (parent of var, or var itself) */ 73 union 74 { 75 SCIP_CONS* cons; /**< constraint that infered this bound change, or NULL */ 76 SCIP_PROP* prop; /**< propagator that infered this bound change, or NULL */ 77 } reason; 78 int info; /**< user information for inference to help resolving the conflict */ 79 }; 80 81 /** change in one bound of a variable */ 82 struct SCIP_BoundChg 83 { 84 SCIP_Real newbound; /**< new value for bound */ 85 union 86 { 87 SCIP_BRANCHINGDATA branchingdata; /**< data for branching decisions */ 88 SCIP_INFERENCEDATA inferencedata; /**< data for infered bound changes */ 89 } data; 90 SCIP_VAR* var; /**< active variable to change the bounds for */ 91 unsigned int boundchgtype:2; /**< bound change type: branching decision or infered bound change */ 92 unsigned int boundtype:1; /**< type of bound for var: lower or upper bound */ 93 unsigned int inferboundtype:1; /**< type of bound for inference var (see inference data): lower or upper bound */ 94 unsigned int applied:1; /**< was this bound change applied at least once? */ 95 unsigned int redundant:1; /**< is this bound change redundant? */ 96 }; 97 98 /** bound change index representing the time of the bound change in path from root to current node */ 99 struct SCIP_BdChgIdx 100 { 101 int depth; /**< depth of node where the bound change was created */ 102 int pos; /**< position of bound change in node's domchg array */ 103 }; 104 105 /** bound change information to track bound changes from root node to current node */ 106 struct SCIP_BdChgInfo 107 { 108 SCIP_Real oldbound; /**< old value for bound */ 109 SCIP_Real newbound; /**< new value for bound */ 110 SCIP_VAR* var; /**< active variable that changed the bounds */ 111 SCIP_INFERENCEDATA inferencedata; /**< data for infered bound changes */ 112 SCIP_BDCHGIDX bdchgidx; /**< bound change index in path from root to current node */ 113 unsigned int pos:27; /**< position in the variable domain change array */ 114 unsigned int boundchgtype:2; /**< bound change type: branching decision or infered bound change */ 115 unsigned int boundtype:1; /**< type of bound for var: lower or upper bound */ 116 unsigned int inferboundtype:1; /**< type of bound for inference var (see inference data): lower or upper bound */ 117 unsigned int redundant:1; /**< does the bound change info belong to a redundant bound change? */ 118 }; 119 120 /** tracks changes of the variables' domains (static arrays, bound changes only) */ 121 struct SCIP_DomChgBound 122 { 123 unsigned int nboundchgs:30; /**< number of bound changes (must be first structure entry!) */ 124 unsigned int domchgtype:2; /**< type of domain change data (must be first structure entry!) */ 125 SCIP_BOUNDCHG* boundchgs; /**< array with changes in bounds of variables */ 126 }; 127 128 /** tracks changes of the variables' domains (static arrays, bound and hole changes) */ 129 struct SCIP_DomChgBoth 130 { 131 unsigned int nboundchgs:30; /**< number of bound changes (must be first structure entry!) */ 132 unsigned int domchgtype:2; /**< type of domain change data (must be first structure entry!) */ 133 SCIP_BOUNDCHG* boundchgs; /**< array with changes in bounds of variables */ 134 SCIP_HOLECHG* holechgs; /**< array with changes in hole lists */ 135 int nholechgs; /**< number of hole list changes */ 136 }; 137 138 /** tracks changes of the variables' domains (dynamic arrays) */ 139 struct SCIP_DomChgDyn 140 { 141 unsigned int nboundchgs:30; /**< number of bound changes (must be first structure entry!) */ 142 unsigned int domchgtype:2; /**< type of domain change data (must be first structure entry!) */ 143 SCIP_BOUNDCHG* boundchgs; /**< array with changes in bounds of variables */ 144 SCIP_HOLECHG* holechgs; /**< array with changes in hole lists */ 145 int nholechgs; /**< number of hole list changes */ 146 int boundchgssize; /**< size of bound changes array */ 147 int holechgssize; /**< size of hole changes array */ 148 }; 149 150 /** tracks changes of the variables' domains */ 151 union SCIP_DomChg 152 { 153 SCIP_DOMCHGBOUND domchgbound; /**< bound changes */ 154 SCIP_DOMCHGBOTH domchgboth; /**< bound and hole changes */ 155 SCIP_DOMCHGDYN domchgdyn; /**< bound and hole changes with dynamic arrays */ 156 }; 157 158 /** domain of a variable */ 159 struct SCIP_Dom 160 { 161 SCIP_Real lb; /**< lower bounds of variables */ 162 SCIP_Real ub; /**< upper bounds of variables */ 163 SCIP_HOLELIST* holelist; /**< list of holes */ 164 }; 165 166 /** original variable information */ 167 struct SCIP_Original 168 { 169 SCIP_DOM origdom; /**< domain of variable in original problem */ 170 SCIP_VAR* transvar; /**< pointer to representing transformed variable */ 171 }; 172 173 /** aggregation information: x = a*y + c */ 174 struct SCIP_Aggregate 175 { 176 SCIP_Real scalar; /**< multiplier a in aggregation */ 177 SCIP_Real constant; /**< constant shift c in aggregation */ 178 SCIP_VAR* var; /**< variable y in aggregation */ 179 }; 180 181 /** multiple aggregation information: x = a_1*y_1 + ... + a_k*y_k + c */ 182 struct SCIP_Multaggr 183 { 184 SCIP_Real constant; /**< constant shift c in multiple aggregation */ 185 SCIP_Real* scalars; /**< multipliers a in multiple aggregation */ 186 SCIP_VAR** vars; /**< variables y in multiple aggregation */ 187 int nvars; /**< number of variables in aggregation */ 188 int varssize; /**< size of vars and scalars arrays */ 189 }; 190 191 /** negation information: x' = c - x */ 192 struct SCIP_Negate 193 { 194 SCIP_Real constant; /**< constant shift c in negation */ 195 }; 196 197 /** variable of the problem */ 198 struct SCIP_Var 199 { 200 SCIP_Real obj; /**< objective function value of variable (might be changed temporarily in probing mode)*/ 201 SCIP_Real unchangedobj; /**< unchanged objective function value of variable (ignoring temporary changes in probing mode) */ 202 SCIP_Real branchfactor; /**< factor to weigh variable's branching score with */ 203 SCIP_Real rootsol; /**< last primal solution of variable in root node, or zero */ 204 SCIP_Real bestrootsol; /**< best primal solution of variable in root node, or zero, w.r.t. root LP value and root reduced cost */ 205 SCIP_Real bestrootredcost; /**< best reduced costs of variable in root node, or zero, w.r.t. root LP value and root solution value */ 206 SCIP_Real bestrootlpobjval; /**< best root LP objective value, or SCIP_INVALID, w.r.t. root solution value and root reduced cost */ 207 SCIP_Real relaxsol; /**< primal solution of variable in current relaxation solution, or SCIP_INVALID */ 208 SCIP_Real nlpsol; /**< primal solution of variable in current NLP solution, or SCIP_INVALID */ 209 SCIP_Real primsolavg; /**< weighted average of all values of variable in primal feasible solutions */ 210 SCIP_Real conflictlb; /**< maximal lower bound of variable in the current conflict */ 211 SCIP_Real conflictub; /**< minimal upper bound of variable in the current conflict */ 212 SCIP_Real conflictrelaxedlb; /**< minimal relaxed lower bound of variable in the current conflict (conflictrelqxlb <= conflictlb) */ 213 SCIP_Real conflictrelaxedub; /**< minimal release upper bound of variable in the current conflict (conflictrelqxlb <= conflictlb) */ 214 SCIP_Real lazylb; /**< global lower bound that is ensured by constraints and has not to be added to the LP */ 215 SCIP_Real lazyub; /**< global upper bound that is ensured by constraints and has not to be added to the LP */ 216 SCIP_DOM glbdom; /**< domain of variable in global problem */ 217 SCIP_DOM locdom; /**< domain of variable in current subproblem */ 218 union 219 { 220 SCIP_ORIGINAL original; /**< original variable information */ 221 SCIP_COL* col; /**< LP column (for column variables) */ 222 SCIP_AGGREGATE aggregate; /**< aggregation information (for aggregated variables) */ 223 SCIP_MULTAGGR multaggr; /**< multiple aggregation information (for multiple aggregated variables) */ 224 SCIP_NEGATE negate; /**< negation information (for negated variables) */ 225 } data; 226 char* name; /**< name of the variable */ 227 SCIP_DECL_VARCOPY ((*varcopy)); /**< copies variable data if wanted to subscip, or NULL */ 228 SCIP_DECL_VARDELORIG ((*vardelorig)); /**< frees user data of original variable */ 229 SCIP_DECL_VARTRANS ((*vartrans)); /**< creates transformed user data by transforming original user data */ 230 SCIP_DECL_VARDELTRANS ((*vardeltrans)); /**< frees user data of transformed variable */ 231 SCIP_VARDATA* vardata; /**< user data for this specific variable */ 232 SCIP_VAR** parentvars; /**< parent variables in the aggregation tree */ 233 SCIP_VAR* negatedvar; /**< pointer to the variables negation: x' = lb + ub - x, or NULL if not created */ 234 SCIP_VBOUNDS* vlbs; /**< variable lower bounds x >= b*y + d */ 235 SCIP_VBOUNDS* vubs; /**< variable upper bounds x <= b*y + d */ 236 SCIP_IMPLICS* implics; /**< implications y >=/<= b following from x <= 0 and x >= 1 (x binary), or NULL if x is not binary */ 237 SCIP_CLIQUELIST* cliquelist; /**< list of cliques the variable and its negation is member of */ 238 SCIP_EVENTFILTER* eventfilter; /**< event filter for events concerning this variable; not for ORIGINAL vars */ 239 SCIP_BDCHGINFO* lbchginfos; /**< bound change informations for lower bound changes from root to current node */ 240 SCIP_BDCHGINFO* ubchginfos; /**< bound change informations for upper bound changes from root to current node */ 241 SCIP_HISTORY* history; /**< branching and inference history information */ 242 SCIP_HISTORY* historycrun; /**< branching and inference history information for current run */ 243 SCIP_VALUEHISTORY* valuehistory; /**< branching and inference history information which are value based, or NULL if not used */ 244 SCIP_Longint closestvblpcount; /**< LP count for which the closestvlbidx/closestvubidx entries are valid */ 245 int index; /**< consecutively numbered variable identifier */ 246 int probindex; /**< array position in problems vars array, or -1 if not assigned to a problem */ 247 int pseudocandindex; /**< array position in pseudo branching candidates array, or -1 */ 248 int eventqueueindexobj; /**< array position in event queue of objective change event, or -1 */ 249 int eventqueueindexlb; /**< array position in event queue of lower bound change event, or -1 */ 250 int eventqueueindexub; /**< array position in event queue of upper bound change event, or -1 */ 251 int parentvarssize; /**< available slots in parentvars array */ 252 int nparentvars; /**< number of parent variables in aggregation tree (used slots of parentvars) */ 253 int nuses; /**< number of times, this variable is referenced */ 254 int nlocksdown[NLOCKTYPES]; /**< array of variable locks for rounding down; if zero, rounding down is always feasible */ 255 int nlocksup[NLOCKTYPES]; /**< array of variable locks for rounding up; if zero, rounding up is always feasible */ 256 int branchpriority; /**< priority of the variable for branching */ 257 int lbchginfossize; /**< available slots in lbchginfos array */ 258 int nlbchginfos; /**< number of lower bound changes from root node to current node */ 259 int ubchginfossize; /**< available slots in ubchginfos array */ 260 int nubchginfos; /**< number of upper bound changes from root node to current node */ 261 int conflictlbcount; /**< number of last conflict, the lower bound was member of */ 262 int conflictubcount; /**< number of last conflict, the upper bound was member of */ 263 int closestvlbidx; /**< index of closest VLB variable in current LP solution, or -1 */ 264 int closestvubidx; /**< index of closest VUB variable in current LP solution, or -1 */ 265 unsigned int initial:1; /**< TRUE iff var's column should be present in the initial root LP */ 266 unsigned int removable:1; /**< TRUE iff var's column is removable from the LP (due to aging or cleanup) */ 267 unsigned int deletable:1; /**< TRUE iff the variable is removable from the problem */ 268 unsigned int deleted:1; /**< TRUE iff variable was marked for deletion from the problem */ 269 unsigned int donotmultaggr:1; /**< TRUE iff variable is not allowed to be multi-aggregated */ 270 unsigned int vartype:2; /**< type of variable: binary, integer, implicit integer, continuous */ 271 unsigned int varstatus:3; /**< status of variable: original, loose, column, fixed, aggregated, multiaggregated, negated */ 272 unsigned int pseudocostflag:2; /**< temporary flag used in pseudo cost update */ 273 unsigned int branchdirection:2; /**< preferred branching direction of the variable (downwards, upwards, auto) */ 274 unsigned int eventqueueimpl:1; /**< is an IMPLADDED event on this variable currently in the event queue? */ 275 unsigned int delglobalstructs:1; /**< is variable marked to be removed from global structures (cliques etc.)? */ 276 unsigned int relaxationonly:1; /**< TRUE if variable has been introduced only to define a relaxation */ 277 #ifndef NDEBUG 278 SCIP* scip; /**< SCIP data structure */ 279 #endif 280 }; 281 282 #ifdef __cplusplus 283 } 284 #endif 285 286 #endif 287