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