Scippy

SCIP

Solving Constraint Integer Programs

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