SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
struct_var.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-2024 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
47extern "C" {
48#endif
49
50/** hole in a domain */
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 */
59{
60 SCIP_HOLE hole; /**< this hole */
61 SCIP_HOLELIST* next; /**< next hole in list */
62};
63
64/** change in a hole list */
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 */
73struct 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 */
79struct 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 */
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 */
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 */
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 */
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) */
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) */
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) */
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 */
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 */
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 */
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 */
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 */
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 */
202{
203 SCIP_Real constant; /**< constant shift c in negation */
204};
205
206/** variable of the problem */
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) */
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
common defines and data types used in all packages of SCIP
SCIP_VAR * var
SCIP_VAR * var
Definition struct_var.h:187
SCIP_Real scalar
Definition struct_var.h:185
SCIP_Real constant
Definition struct_var.h:186
SCIP_BDCHGIDX bdchgidx
Definition struct_var.h:121
SCIP_Real newbound
Definition struct_var.h:118
SCIP_INFERENCEDATA inferencedata
Definition struct_var.h:120
unsigned int boundchgtype
Definition struct_var.h:123
unsigned int boundtype
Definition struct_var.h:124
SCIP_VAR * var
Definition struct_var.h:119
unsigned int redundant
Definition struct_var.h:126
unsigned int inferboundtype
Definition struct_var.h:125
SCIP_Real oldbound
Definition struct_var.h:117
unsigned int pos
Definition struct_var.h:122
union SCIP_BoundChg::@126301315365336333353356203157377037022074222233 data
SCIP_Real newbound
Definition struct_var.h:93
unsigned int applied
Definition struct_var.h:103
unsigned int boundtype
Definition struct_var.h:101
SCIP_INFERENCEDATA inferencedata
Definition struct_var.h:97
unsigned int redundant
Definition struct_var.h:104
SCIP_VAR * var
Definition struct_var.h:99
SCIP_BRANCHINGDATA branchingdata
Definition struct_var.h:96
unsigned int inferboundtype
Definition struct_var.h:102
unsigned int boundchgtype
Definition struct_var.h:100
SCIP_BOUNDCHG * boundchgs
Definition struct_var.h:142
unsigned int nboundchgs
Definition struct_var.h:140
SCIP_HOLECHG * holechgs
Definition struct_var.h:143
unsigned int domchgtype
Definition struct_var.h:141
SCIP_BOUNDCHG * boundchgs
Definition struct_var.h:134
unsigned int domchgtype
Definition struct_var.h:133
unsigned int nboundchgs
Definition struct_var.h:132
SCIP_BOUNDCHG * boundchgs
Definition struct_var.h:152
SCIP_HOLECHG * holechgs
Definition struct_var.h:153
unsigned int nboundchgs
Definition struct_var.h:150
unsigned int domchgtype
Definition struct_var.h:151
SCIP_Real lb
Definition struct_var.h:170
SCIP_Real ub
Definition struct_var.h:171
SCIP_HOLELIST * holelist
Definition struct_var.h:172
SCIP_HOLELIST ** ptr
Definition struct_var.h:67
SCIP_HOLELIST * oldlist
Definition struct_var.h:69
SCIP_HOLELIST * newlist
Definition struct_var.h:68
SCIP_Real right
Definition struct_var.h:54
SCIP_Real left
Definition struct_var.h:53
SCIP_HOLELIST * next
Definition struct_var.h:61
SCIP_HOLE hole
Definition struct_var.h:60
SCIP_VAR ** vars
Definition struct_var.h:195
SCIP_Real constant
Definition struct_var.h:193
SCIP_Real * scalars
Definition struct_var.h:194
SCIP_Real constant
Definition struct_var.h:203
SCIP_DOM origdom
Definition struct_var.h:178
SCIP_VAR * transvar
Definition struct_var.h:179
SCIP_Real lazylb
Definition struct_var.h:223
SCIP_VARDATA * vardata
Definition struct_var.h:240
SCIP_EVENTFILTER * eventfilter
Definition struct_var.h:247
int nubchginfos
Definition struct_var.h:269
SCIP_Real lazyub
Definition struct_var.h:224
SCIP_ORIGINAL original
Definition struct_var.h:229
SCIP_VBOUNDS * vlbs
Definition struct_var.h:243
SCIP_AGGREGATE aggregate
Definition struct_var.h:231
SCIP_IMPLICS * implics
Definition struct_var.h:245
SCIP_VAR ** parentvars
Definition struct_var.h:241
SCIP_BDCHGINFO * lbchginfos
Definition struct_var.h:248
SCIP_Real rootsol
Definition struct_var.h:212
SCIP_DECL_VARDELTRANS((*vardeltrans))
SCIP_VAR * negatedvar
Definition struct_var.h:242
int eventqueueindexobj
Definition struct_var.h:257
SCIP * scip
Definition struct_var.h:288
unsigned int varstatus
Definition struct_var.h:281
int nlocksdown[NLOCKTYPES]
Definition struct_var.h:263
SCIP_Real bestrootsol
Definition struct_var.h:213
SCIP_HISTORY * historycrun
Definition struct_var.h:251
unsigned int relaxationonly
Definition struct_var.h:286
unsigned int donotmultaggr
Definition struct_var.h:279
int closestvubidx
Definition struct_var.h:273
SCIP_DOM glbdom
Definition struct_var.h:225
unsigned int vartype
Definition struct_var.h:280
SCIP_Real branchfactor
Definition struct_var.h:211
int pseudocandindex
Definition struct_var.h:256
int conflictubcount
Definition struct_var.h:271
SCIP_Real unchangedobj
Definition struct_var.h:210
unsigned int eventqueueimpl
Definition struct_var.h:284
SCIP_Real conflictrelaxedub
Definition struct_var.h:222
SCIP_BDCHGINFO * ubchginfos
Definition struct_var.h:249
unsigned int pseudocostflag
Definition struct_var.h:282
SCIP_Real conflictub
Definition struct_var.h:220
SCIP_Real bestrootredcost
Definition struct_var.h:214
char * name
Definition struct_var.h:235
SCIP_DECL_VARTRANS((*vartrans))
int eventqueueindexlb
Definition struct_var.h:258
int eventqueueindexub
Definition struct_var.h:259
union SCIP_Var::@062351145146014100220174313010263165251013276204 data
SCIP_Real conflictrelaxedlb
Definition struct_var.h:221
unsigned int deletable
Definition struct_var.h:276
unsigned int initial
Definition struct_var.h:274
SCIP_DOM locdom
Definition struct_var.h:226
unsigned int removable
Definition struct_var.h:275
SCIP_CLIQUELIST * cliquelist
Definition struct_var.h:246
SCIP_COL * col
Definition struct_var.h:230
unsigned int deleted
Definition struct_var.h:277
SCIP_MULTAGGR multaggr
Definition struct_var.h:232
SCIP_Real obj
Definition struct_var.h:209
int probindex
Definition struct_var.h:255
SCIP_Real nlpsol
Definition struct_var.h:217
int nlocksup[NLOCKTYPES]
Definition struct_var.h:264
int nlbchginfos
Definition struct_var.h:267
unsigned int branchdirection
Definition struct_var.h:283
unsigned int delglobalstructs
Definition struct_var.h:285
int lbchginfossize
Definition struct_var.h:266
SCIP_HISTORY * history
Definition struct_var.h:250
SCIP_VBOUNDS * vubs
Definition struct_var.h:244
int nparentvars
Definition struct_var.h:261
SCIP_DECL_VARDELORIG((*vardelorig))
unsigned int donotaggr
Definition struct_var.h:278
int parentvarssize
Definition struct_var.h:260
int closestvlbidx
Definition struct_var.h:272
SCIP_DECL_VARCOPY((*varcopy))
SCIP_NEGATE negate
Definition struct_var.h:233
SCIP_Real primsolavg
Definition struct_var.h:218
SCIP_Real conflictlb
Definition struct_var.h:219
SCIP_Real relaxsol
Definition struct_var.h:216
SCIP_Longint closestvblpcount
Definition struct_var.h:253
SCIP_Real bestrootlpobjval
Definition struct_var.h:215
int ubchginfossize
Definition struct_var.h:268
SCIP_VALUEHISTORY * valuehistory
Definition struct_var.h:252
int branchpriority
Definition struct_var.h:265
int conflictlbcount
Definition struct_var.h:270
type definitions for constraints and constraint handlers
type definitions for managing events
type definitions for branching and inference history
type definitions for implications, variable bounds, and cliques
type definitions for LP management
type definitions for propagators
type definitions for problem variables
struct SCIP_VarData SCIP_VARDATA
Definition type_var.h:120
#define NLOCKTYPES
Definition type_var.h:94
struct SCIP_BranchingData SCIP_BRANCHINGDATA
Definition type_var.h:109
struct SCIP_InferenceData SCIP_INFERENCEDATA
Definition type_var.h:110
SCIP_DOMCHGBOUND domchgbound
Definition struct_var.h:162
SCIP_DOMCHGDYN domchgdyn
Definition struct_var.h:164
SCIP_DOMCHGBOTH domchgboth
Definition struct_var.h:163