Scippy

SCIP

Solving Constraint Integer Programs

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
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Real
Definition: def.h:173
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::@21 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
union SCIP_Var::@22 data
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
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
int index
Definition: struct_var.h:254
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 nuses
Definition: struct_var.h:262
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