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