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