SCIP Doxygen Documentation
Loading...
Searching...
No Matches
struct_reopt.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_reopt.h
26
* @ingroup INTERNALAPI
27
* @brief data structures for collecting reoptimization information
28
* @author Jakob Witzig
29
*/
30
31
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33
#ifndef __SCIP_STRUCT_REOPT_H__
34
#define __SCIP_STRUCT_REOPT_H__
35
36
#include "
scip/def.h
"
37
#include "
scip/type_clock.h
"
38
#include "
scip/type_cons.h
"
39
#include "
scip/type_history.h
"
40
#include "
scip/type_lp.h
"
41
#include "
scip/type_misc.h
"
42
#include "
scip/type_reopt.h
"
43
#include "
scip/type_sol.h
"
44
#include "
scip/type_var.h
"
45
46
#ifdef __cplusplus
47
extern
"C"
{
48
#endif
49
50
/** nodes of SCIP_SolTree */
51
struct
SCIP_SolNode
52
{
53
SCIP_SOL
*
sol
;
/**< the stored solution */
54
SCIP_SOLNODE
*
father
;
/**< pointer to the parent node */
55
SCIP_SOLNODE
*
child
;
/**< pointer to left most child node, i.e., node representing the variable
56
* with smallest solution value
57
*/
58
SCIP_SOLNODE
*
sibling
;
/**< pointer to next sibling node */
59
SCIP_Real
value
;
/**< solution value represented by this node */
60
SCIP_Bool
updated
;
/**< flag if the solution is already updated
61
* w.r.t. the new objective function */
62
#ifndef NDEBUG
63
SCIP_VAR
*
var
;
/**< variable represented by this node */
64
#endif
65
};
66
67
/** tree for solution */
68
struct
SCIP_SolTree
69
{
70
SCIP_SOLNODE
***
sols
;
/**< array of arrays of solutions of the reoptimization runs */
71
SCIP_SOLNODE
*
root
;
/**< root node of the solution tree */
72
int
*
solssize
;
/**< size of sols[x] arrays */
73
int
*
nsols
;
/**< number of solutions stored in sols[x] array */
74
};
75
76
/** data for constraints to split nodes during reoptimization */
77
struct
SCIP_ReoptConsData
78
{
79
SCIP_VAR
**
vars
;
/**< array of variables */
80
SCIP_Real
* vals;
/**< array of variable coefficients or bounds */
81
SCIP_BOUNDTYPE
* boundtypes;
/**< array of variable bounds */
82
SCIP_Real
lhs;
/**< left hand side of the constraint */
83
SCIP_Real
rhs;
/**< right hand side of the constraint */
84
REOPT_CONSTYPE
constype;
/**< type of the constraint */
85
SCIP_Bool
linear;
/**< TRUE, iff the constraint is linear, otherwise the constraint is of
86
* type bounddisjunction
87
*/
88
int
varssize;
/**< available size in the arrays */
89
int
nvars
;
/**< number of entries in the arrays */
90
};
91
92
/** nodes of SCIP_ReoptTree */
93
struct
SCIP_ReoptNode
94
{
95
SCIP_REOPTCONSDATA
**
conss
;
/**< array of constraints added to the node, i.e., logic-or constraints */
96
SCIP_VAR
**
vars
;
/**< variables along the branching path up to the next stored node */
97
SCIP_VAR
**
afterdualvars
;
/**< variables along the branching path after the first decision based on dual information */
98
SCIP_REOPTCONSDATA
*
dualredscur
;
/**< dual reductions that need to be reconstructed the current round */
99
SCIP_REOPTCONSDATA
*
dualredsnex
;
/**< dual reductions that need to be reconstructed the next round */
100
SCIP_BOUNDTYPE
*
varboundtypes
;
/**< boundtypes along the branching path up to the next stored node */
101
SCIP_BOUNDTYPE
*
afterdualvarboundtypes
;
/**< boundtypes along the branching path after the first dual information */
102
SCIP_Real
*
varbounds
;
/**< bounds along the branching path up to the next stored node */
103
SCIP_Real
*
afterdualvarbounds
;
/**< bounds along the branching path after the first decision based on dual information */
104
SCIP_Real
lowerbound
;
/**< the last lowerbound of this node in the previous iteration */
105
SCIP_Bool
dualreds
;
/**< flag whether dual reduction were performed */
106
int
nvars
;
/**< number of branching decisions up to the next stored node */
107
int
varssize
;
/**< size of allocated memory */
108
int
nafterdualvars
;
/**< number of branching decisions after the first dual information */
109
int
afterdualvarssize
;
/**< size of allocated memory */
110
int
nchilds
;
/**< number of child nodes */
111
int
allocchildmem
;
/**< allocated memory for child nodes */
112
int
nconss
;
/**< number of added constraints */
113
int
consssize
;
/**< allocated memory for constraints */
114
unsigned
int
*
childids
;
/**< array of child nodes that need to be reoptimized */
115
116
unsigned
int
parentID
:29;
/**< id of the stored parent node */
117
unsigned
int
reopttype
:3;
/**< reason for storing the node */
118
};
119
120
/* tree to store the current search tree */
121
struct
SCIP_ReoptTree
122
{
123
SCIP_REOPTNODE
**
reoptnodes
;
/**< array of SCIP_REOPTNODE */
124
SCIP_QUEUE
*
openids
;
/**< queue of open positions in the reoptnodes array */
125
int
nreoptnodes
;
/**< number of saved nodes */
126
int
nfeasnodes
;
/**< number of feasible nodes in the current run */
127
int
ntotalfeasnodes
;
/**< number of feasible nodes over all runs */
128
int
ninfnodes
;
/**< number of (LP-)infeasible nodes in the current run */
129
int
ntotalinfnodes
;
/**< number of (LP-)infeasible nodes over all runs */
130
int
nprunednodes
;
/**< number of pruned nodes in the current run */
131
int
ntotalprunednodes
;
/**< number of pruned nodes over all runs */
132
int
ncutoffreoptnodes
;
/**< number of cut off reoptimized nodes in the current run */
133
int
ntotalcutoffreoptnodes
;
/**< number of cut off reoptimized nodes over all runs */
134
SCIP_Bool
initialized
;
/**< is the data structure initialized? */
135
unsigned
int
reoptnodessize
;
/**< size of allocated memory for the reoptnodes array and the openid queue */
136
};
137
138
/** reoptimization data and solution storage */
139
struct
SCIP_Reopt
140
{
141
SCIP_SOL
**
prevbestsols
;
/**< list of best solutions of all previous rounds */
142
SCIP_Real
**
objs
;
/**< list of objective coefficients */
143
SCIP_HISTORY
***
varhistory
;
/**< collected variable history */
144
SCIP_REOPTCONSDATA
**
glbconss
;
/**< global constraints that need to be added at the beginning of the next iteration */
145
SCIP_REOPTCONSDATA
*
dualreds
;
/**< dual reductions that probably need to be reconstructed at this node */
146
SCIP_REOPTTREE
*
reopttree
;
/**< data structure to store the current reoptimization search tree */
147
SCIP_SOLTREE
*
soltree
;
/**< tree to handle all saved solutions */
148
SCIP_RANDNUMGEN
*
randnumgen
;
/**< random number generator */
149
SCIP_CLOCK
*
savingtime
;
/**< time needed to store the nodes */
150
SCIP_CONS
**
addedconss
;
/**< array of added constraints */
151
SCIP_Real
simtolastobj
;
/**< similarity to the last objective function */
152
SCIP_Real
simtofirstobj
;
/**< similarity to the first objective function */
153
SCIP_Longint
lastbranched
;
/**< number of the last branched node */
154
SCIP_Longint
lastseennode
;
/**< node number of the last caught event */
155
int
nobjvars
;
/**< number of variables in the objective function */
156
int
addedconsssize
;
/**< size of addedconss array */
157
int
naddedconss
;
/**< number of constraints added */
158
SCIP_Bool
objhaschanged
;
/**< TRUE iff the objective fucntion has changd */
159
SCIP_Bool
consadded
;
/**< TRUE iff a constraint was added */
160
int
nactiveconss
;
/**< number of active constraints stored in activeconss */
161
SCIP_CONS
**
activeconss
;
/**< storage for active constraints */
162
int
nmaxactiveconss
;
/**< maximal number of active constraints stored in activeconss */
163
164
/* hashmaps to track global bound reductions and constraints deletion during presolving */
165
SCIP_HASHMAP
*
glblb
;
/**< global lower bounds after presolving of the first problem */
166
SCIP_HASHMAP
*
glbub
;
/**< global upper bounds after presolving of the first problem */
167
SCIP_HASHSET
*
activeconssset
;
/**< set of all active constraints after presolving the first problem */
168
169
/* data structure to track decisions based on dual information */
170
SCIP_Longint
currentnode
;
/**< number of the current node */
171
int
run
;
/**< number of the current reoptimization run */
172
int
runsize
;
/**< allocated memory for runs */
173
int
firstobj
;
/**< first non empty objective function */
174
int
noptsolsbyreoptsol
;
/**< number of successive optimal solutions found by heur_reoptsols */
175
int
nglbconss
;
/**< number of stored global constraints */
176
int
allocmemglbconss
;
/**< allocated memory for global constraints */
177
int
ncheckedsols
;
/**< number of updated solutions by reoptsols */
178
int
nimprovingsols
;
/**< number of improving solutions found by reoptsols */
179
int
nglbrestarts
;
/**< number of global restarts */
180
int
ntotallocrestarts
;
/**< number of local restarts over all runs */
181
int
nlocrestarts
;
/**< number of local restarts in the current iteration */
182
int
firstrestart
;
/**< run with the first global restart or -1 of no restart */
183
int
lastrestart
;
/**< run with the last global restart or -1 if no restart */
184
};
185
186
#ifdef __cplusplus
187
}
188
#endif
189
190
#endif
def.h
common defines and data types used in all packages of SCIP
SCIP_Longint
#define SCIP_Longint
Definition
def.h:157
SCIP_Bool
#define SCIP_Bool
Definition
def.h:91
SCIP_Real
#define SCIP_Real
Definition
def.h:172
nvars
int nvars
Definition
heur_intshifting.c:710
vars
static SCIP_VAR ** vars
Definition
heur_rootsoldiving.c:185
SCIP_ReoptNode
Definition
struct_reopt.h:94
SCIP_ReoptNode::afterdualvars
SCIP_VAR ** afterdualvars
Definition
struct_reopt.h:97
SCIP_ReoptNode::afterdualvarssize
int afterdualvarssize
Definition
struct_reopt.h:109
SCIP_ReoptNode::allocchildmem
int allocchildmem
Definition
struct_reopt.h:111
SCIP_ReoptNode::dualredscur
SCIP_REOPTCONSDATA * dualredscur
Definition
struct_reopt.h:98
SCIP_ReoptNode::dualredsnex
SCIP_REOPTCONSDATA * dualredsnex
Definition
struct_reopt.h:99
SCIP_ReoptNode::afterdualvarboundtypes
SCIP_BOUNDTYPE * afterdualvarboundtypes
Definition
struct_reopt.h:101
SCIP_ReoptNode::varboundtypes
SCIP_BOUNDTYPE * varboundtypes
Definition
struct_reopt.h:100
SCIP_ReoptNode::nafterdualvars
int nafterdualvars
Definition
struct_reopt.h:108
SCIP_ReoptNode::childids
unsigned int * childids
Definition
struct_reopt.h:114
SCIP_ReoptNode::dualreds
SCIP_Bool dualreds
Definition
struct_reopt.h:105
SCIP_ReoptNode::nvars
int nvars
Definition
struct_reopt.h:106
SCIP_ReoptNode::vars
SCIP_VAR ** vars
Definition
struct_reopt.h:96
SCIP_ReoptNode::nconss
int nconss
Definition
struct_reopt.h:112
SCIP_ReoptNode::afterdualvarbounds
SCIP_Real * afterdualvarbounds
Definition
struct_reopt.h:103
SCIP_ReoptNode::conss
SCIP_REOPTCONSDATA ** conss
Definition
struct_reopt.h:95
SCIP_ReoptNode::consssize
int consssize
Definition
struct_reopt.h:113
SCIP_ReoptNode::varssize
int varssize
Definition
struct_reopt.h:107
SCIP_ReoptNode::lowerbound
SCIP_Real lowerbound
Definition
struct_reopt.h:104
SCIP_ReoptNode::parentID
unsigned int parentID
Definition
struct_reopt.h:116
SCIP_ReoptNode::reopttype
unsigned int reopttype
Definition
struct_reopt.h:117
SCIP_ReoptNode::nchilds
int nchilds
Definition
struct_reopt.h:110
SCIP_ReoptNode::varbounds
SCIP_Real * varbounds
Definition
struct_reopt.h:102
SCIP_ReoptTree
Definition
struct_reopt.h:122
SCIP_ReoptTree::openids
SCIP_QUEUE * openids
Definition
struct_reopt.h:124
SCIP_ReoptTree::nprunednodes
int nprunednodes
Definition
struct_reopt.h:130
SCIP_ReoptTree::nreoptnodes
int nreoptnodes
Definition
struct_reopt.h:125
SCIP_ReoptTree::ncutoffreoptnodes
int ncutoffreoptnodes
Definition
struct_reopt.h:132
SCIP_ReoptTree::ntotalfeasnodes
int ntotalfeasnodes
Definition
struct_reopt.h:127
SCIP_ReoptTree::ntotalinfnodes
int ntotalinfnodes
Definition
struct_reopt.h:129
SCIP_ReoptTree::reoptnodessize
unsigned int reoptnodessize
Definition
struct_reopt.h:135
SCIP_ReoptTree::reoptnodes
SCIP_REOPTNODE ** reoptnodes
Definition
struct_reopt.h:123
SCIP_ReoptTree::nfeasnodes
int nfeasnodes
Definition
struct_reopt.h:126
SCIP_ReoptTree::ninfnodes
int ninfnodes
Definition
struct_reopt.h:128
SCIP_ReoptTree::ntotalcutoffreoptnodes
int ntotalcutoffreoptnodes
Definition
struct_reopt.h:133
SCIP_ReoptTree::ntotalprunednodes
int ntotalprunednodes
Definition
struct_reopt.h:131
SCIP_ReoptTree::initialized
SCIP_Bool initialized
Definition
struct_reopt.h:134
SCIP_Reopt
Definition
struct_reopt.h:140
SCIP_Reopt::firstobj
int firstobj
Definition
struct_reopt.h:173
SCIP_Reopt::nobjvars
int nobjvars
Definition
struct_reopt.h:155
SCIP_Reopt::firstrestart
int firstrestart
Definition
struct_reopt.h:182
SCIP_Reopt::nimprovingsols
int nimprovingsols
Definition
struct_reopt.h:178
SCIP_Reopt::glbconss
SCIP_REOPTCONSDATA ** glbconss
Definition
struct_reopt.h:144
SCIP_Reopt::naddedconss
int naddedconss
Definition
struct_reopt.h:157
SCIP_Reopt::consadded
SCIP_Bool consadded
Definition
struct_reopt.h:159
SCIP_Reopt::nactiveconss
int nactiveconss
Definition
struct_reopt.h:160
SCIP_Reopt::prevbestsols
SCIP_SOL ** prevbestsols
Definition
struct_reopt.h:141
SCIP_Reopt::reopttree
SCIP_REOPTTREE * reopttree
Definition
struct_reopt.h:146
SCIP_Reopt::dualreds
SCIP_REOPTCONSDATA * dualreds
Definition
struct_reopt.h:145
SCIP_Reopt::nglbrestarts
int nglbrestarts
Definition
struct_reopt.h:179
SCIP_Reopt::run
int run
Definition
struct_reopt.h:171
SCIP_Reopt::soltree
SCIP_SOLTREE * soltree
Definition
struct_reopt.h:147
SCIP_Reopt::runsize
int runsize
Definition
struct_reopt.h:172
SCIP_Reopt::lastbranched
SCIP_Longint lastbranched
Definition
struct_reopt.h:153
SCIP_Reopt::nlocrestarts
int nlocrestarts
Definition
struct_reopt.h:181
SCIP_Reopt::ntotallocrestarts
int ntotallocrestarts
Definition
struct_reopt.h:180
SCIP_Reopt::noptsolsbyreoptsol
int noptsolsbyreoptsol
Definition
struct_reopt.h:174
SCIP_Reopt::nmaxactiveconss
int nmaxactiveconss
Definition
struct_reopt.h:162
SCIP_Reopt::randnumgen
SCIP_RANDNUMGEN * randnumgen
Definition
struct_reopt.h:148
SCIP_Reopt::savingtime
SCIP_CLOCK * savingtime
Definition
struct_reopt.h:149
SCIP_Reopt::glblb
SCIP_HASHMAP * glblb
Definition
struct_reopt.h:165
SCIP_Reopt::lastseennode
SCIP_Longint lastseennode
Definition
struct_reopt.h:154
SCIP_Reopt::activeconss
SCIP_CONS ** activeconss
Definition
struct_reopt.h:161
SCIP_Reopt::currentnode
SCIP_Longint currentnode
Definition
struct_reopt.h:170
SCIP_Reopt::activeconssset
SCIP_HASHSET * activeconssset
Definition
struct_reopt.h:167
SCIP_Reopt::lastrestart
int lastrestart
Definition
struct_reopt.h:183
SCIP_Reopt::varhistory
SCIP_HISTORY *** varhistory
Definition
struct_reopt.h:143
SCIP_Reopt::objhaschanged
SCIP_Bool objhaschanged
Definition
struct_reopt.h:158
SCIP_Reopt::simtofirstobj
SCIP_Real simtofirstobj
Definition
struct_reopt.h:152
SCIP_Reopt::objs
SCIP_Real ** objs
Definition
struct_reopt.h:142
SCIP_Reopt::addedconsssize
int addedconsssize
Definition
struct_reopt.h:156
SCIP_Reopt::addedconss
SCIP_CONS ** addedconss
Definition
struct_reopt.h:150
SCIP_Reopt::ncheckedsols
int ncheckedsols
Definition
struct_reopt.h:177
SCIP_Reopt::nglbconss
int nglbconss
Definition
struct_reopt.h:175
SCIP_Reopt::glbub
SCIP_HASHMAP * glbub
Definition
struct_reopt.h:166
SCIP_Reopt::allocmemglbconss
int allocmemglbconss
Definition
struct_reopt.h:176
SCIP_Reopt::simtolastobj
SCIP_Real simtolastobj
Definition
struct_reopt.h:151
SCIP_SolNode
Definition
struct_reopt.h:52
SCIP_SolNode::sol
SCIP_SOL * sol
Definition
struct_reopt.h:53
SCIP_SolNode::var
SCIP_VAR * var
Definition
struct_reopt.h:63
SCIP_SolNode::value
SCIP_Real value
Definition
struct_reopt.h:59
SCIP_SolNode::child
SCIP_SOLNODE * child
Definition
struct_reopt.h:55
SCIP_SolNode::father
SCIP_SOLNODE * father
Definition
struct_reopt.h:54
SCIP_SolNode::sibling
SCIP_SOLNODE * sibling
Definition
struct_reopt.h:58
SCIP_SolNode::updated
SCIP_Bool updated
Definition
struct_reopt.h:60
SCIP_SolTree
Definition
struct_reopt.h:69
SCIP_SolTree::root
SCIP_SOLNODE * root
Definition
struct_reopt.h:71
SCIP_SolTree::sols
SCIP_SOLNODE *** sols
Definition
struct_reopt.h:70
SCIP_SolTree::solssize
int * solssize
Definition
struct_reopt.h:72
SCIP_SolTree::nsols
int * nsols
Definition
struct_reopt.h:73
type_clock.h
type definitions for clocks and timing issues
SCIP_CLOCK
struct SCIP_Clock SCIP_CLOCK
Definition
type_clock.h:49
type_cons.h
type definitions for constraints and constraint handlers
SCIP_CONS
struct SCIP_Cons SCIP_CONS
Definition
type_cons.h:63
type_history.h
type definitions for branching and inference history
SCIP_HISTORY
struct SCIP_History SCIP_HISTORY
Definition
type_history.h:50
type_lp.h
type definitions for LP management
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition
type_lp.h:59
type_misc.h
type definitions for miscellaneous datastructures
SCIP_HASHMAP
struct SCIP_HashMap SCIP_HASHMAP
Definition
type_misc.h:105
SCIP_RANDNUMGEN
struct SCIP_RandNumGen SCIP_RANDNUMGEN
Definition
type_misc.h:126
SCIP_HASHSET
struct SCIP_HashSet SCIP_HASHSET
Definition
type_misc.h:111
SCIP_QUEUE
struct SCIP_Queue SCIP_QUEUE
Definition
type_misc.h:75
type_reopt.h
type definitions for collecting reoptimization information
SCIP_REOPTCONSDATA
struct SCIP_ReoptConsData SCIP_REOPTCONSDATA
Definition
type_reopt.h:51
SCIP_REOPTTREE
struct SCIP_ReoptTree SCIP_REOPTTREE
Definition
type_reopt.h:45
SCIP_REOPTNODE
struct SCIP_ReoptNode SCIP_REOPTNODE
Definition
type_reopt.h:47
SCIP_SOLNODE
struct SCIP_SolNode SCIP_SOLNODE
Definition
type_reopt.h:43
REOPT_CONSTYPE
enum Reopt_ConsType REOPT_CONSTYPE
Definition
type_reopt.h:76
SCIP_SOLTREE
struct SCIP_SolTree SCIP_SOLTREE
Definition
type_reopt.h:41
type_sol.h
type definitions for storing primal CIP solutions
SCIP_SOL
struct SCIP_Sol SCIP_SOL
Definition
type_sol.h:57
type_var.h
type definitions for problem variables
SCIP_VAR
struct SCIP_Var SCIP_VAR
Definition
type_var.h:119
struct_reopt.h
© 2002-2024 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.13.2