Scippy

SCIP

Solving Constraint Integer Programs

scip_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 scip_reopt.h
17  * @ingroup PUBLICCOREAPI
18  * @brief public methods for reoptimization
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Thorsten Koch
22  * @author Alexander Martin
23  * @author Marc Pfetsch
24  * @author Kati Wolter
25  * @author Gregor Hendel
26  * @author Robert Lion Gottwald
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #ifndef __SCIP_SCIP_REOPT_H__
32 #define __SCIP_SCIP_REOPT_H__
33 
34 
35 #include "scip/def.h"
36 #include "scip/type_lp.h"
37 #include "scip/type_reopt.h"
38 #include "scip/type_retcode.h"
39 #include "scip/type_scip.h"
40 #include "scip/type_tree.h"
41 #include "scip/type_var.h"
42 
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46 
47 /**@addtogroup PublicReoptimizationMethods
48  *
49  * @{
50  */
51 
52 /** return the ids of child nodes stored in the reoptimization tree
53  *
54  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
55  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
56  *
57  * @pre This method can be called if @p scip is in one of the following stages:
58  * - \ref SCIP_STAGE_PRESOLVED
59  * - \ref SCIP_STAGE_SOLVING
60  * - \ref SCIP_STAGE_SOLVED
61  */
64  SCIP* scip, /**< SCIP data structure */
65  SCIP_NODE* node, /**< node of the search tree */
66  unsigned int* ids, /**< array to store the ids of child nodes */
67  int mem, /**< allocated memory */
68  int* nids /**< number of child nodes */
69  );
70 
71 /** return the ids of all leave nodes store in the reoptimization tree induced by the given node
72  *
73  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
74  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
75  *
76  * @pre This method can be called if @p scip is in one of the following stages:
77  * - \ref SCIP_STAGE_PRESOLVED
78  * - \ref SCIP_STAGE_SOLVING
79  * - \ref SCIP_STAGE_SOLVED
80  */
83  SCIP* scip, /**< SCIP data strcuture */
84  SCIP_NODE* node, /**< node of the search tree */
85  unsigned int* ids, /**< array of ids */
86  int mem, /**< allocated memory */
87  int* nids /**< number of child nodes */
88  );
89 
90 /** returns the number of nodes in the reoptimization tree induced by @p node; if @p node == NULL, the method
91  * returns the number of nodes of the whole reoptimization tree.
92  */
95  SCIP* scip, /**< SCIP data structure */
96  SCIP_NODE* node /**< node of the search tree */
97  );
98 
99 /** returns the number of leave nodes of the subtree induced by @p node; if @p node == NULL, the method
100  * returns the number of leaf nodes of the whole reoptimization tree.
101  */
104  SCIP* scip, /**< SCIP data structure */
105  SCIP_NODE* node /**< node of the search tree */
106  );
107 
108 /** gets the node of the reoptimization tree corresponding to the unique @p id */
110  SCIP* scip, /**< SCIP data structure */
111  unsigned int id /**< unique id */
112  );
113 
114 /** add a variable bound change to a given reoptnode
115  *
116  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
117  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
118  *
119  * @pre This method can be called if @p scip is in one of the following stages:
120  * - \ref SCIP_STAGE_PRESOLVED
121  * - \ref SCIP_STAGE_SOLVING
122  * - \ref SCIP_STAGE_SOLVED
123  */
126  SCIP* scip, /**< SCIP data structure */
127  SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */
128  SCIP_VAR* var, /**< variable pointer */
129  SCIP_Real bound, /**< variable bound to add */
130  SCIP_BOUNDTYPE boundtype /**< bound type of the variable value */
131  );
132 
133 /** set the @p representation as the new search frontier
134  *
135  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
136  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
137  *
138  * @pre This method can be called if @p scip is in one of the following stages:
139  * - \ref SCIP_STAGE_PRESOLVED
140  */
143  SCIP* scip, /**< SCIP data structure */
144  SCIP_REOPTNODE** representation, /**< array of representatives */
145  int nrepresentatives, /**< number of representatives */
146  SCIP_Bool* success /**< pointer to store the result */
147  );
148 
149 /** add stored constraint to a reoptimization node
150  *
151  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
152  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
153  *
154  * @pre This method can be called if @p scip is in one of the following stages:
155  * - \ref SCIP_STAGE_PRESOLVED
156  */
159  SCIP* scip, /**< SCIP data structure */
160  SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */
161  SCIP_VAR** vars, /**< array of variables */
162  SCIP_Real* vals, /**< array of variable bounds */
163  SCIP_BOUNDTYPE* boundtypes, /**< array of variable boundtypes */
164  SCIP_Real lhs, /**< lhs of the constraint */
165  SCIP_Real rhs, /**< rhs of the constraint */
166  int nvars, /**< number of variables */
167  REOPT_CONSTYPE constype, /**< type of the constraint */
168  SCIP_Bool linear /**< the given constraint has a linear representation */
169  );
170 
171 /** return the branching path stored in the reoptree at ID id */
174  SCIP* scip, /**< SCIP data structure */
175  SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */
176  SCIP_VAR** vars, /**< array of variables */
177  SCIP_Real* vals, /**< array of variable bounds */
178  SCIP_BOUNDTYPE* boundtypes, /**< array of bound types */
179  int mem, /**< allocated memory */
180  int* nvars, /**< number of variables */
181  int* nafterdualvars /**< number of variables directly after the first based on dual information */
182  );
183 
184 /** initialize a set of empty reoptimization nodes
185  *
186  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
187  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
188  *
189  * @pre This method can be called if @p scip is in one of the following stages:
190  * - \ref SCIP_STAGE_PRESOLVED
191  */
194  SCIP* scip, /**< SCIP data structure */
195  SCIP_REOPTNODE** representatives, /**< array of representatives */
196  int nrepresentatives /**< number of representatives */
197  );
198 
199 /** reset a set of initialized reoptimization nodes
200  *
201  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
202  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
203  *
204  * @pre This method can be called if @p scip is in one of the following stages:
205  * - \ref SCIP_STAGE_PRESOLVED
206  */
208  SCIP* scip, /**< SCIP data structure */
209  SCIP_REOPTNODE** representatives, /**< array of representatives */
210  int nrepresentatives /**< number of representatives */
211  );
212 
213 /** free a set of initialized reoptimization nodes
214  *
215  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
216  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
217  *
218  * @pre This method can be called if @p scip is in one of the following stages:
219  * - \ref SCIP_STAGE_PRESOLVED
220  */
223  SCIP* scip, /**< SCIP data structure */
224  SCIP_REOPTNODE** representatives, /**< array of representatives */
225  int nrepresentatives /**< number of representatives */
226  );
227 
228 /** reactivate the given @p reoptnode and split them into several nodes if necessary
229  *
230  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
231  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
232  *
233  * @pre This method can be called if @p scip is in one of the following stages:
234  * - \ref SCIP_STAGE_SOLVING
235  * - \ref SCIP_STAGE_SOLVED
236  */
239  SCIP* scip, /**< SCIP data structure */
240  SCIP_REOPTNODE* reoptnode, /**< node to reactivate */
241  unsigned int id, /**< unique id of the reoptimization node */
242  SCIP_Real estimate, /**< estimate of the child nodes that should be created */
243  SCIP_NODE** childnodes, /**< array to store the created child nodes */
244  int* ncreatedchilds, /**< pointer to store number of created child nodes */
245  int* naddedconss, /**< pointer to store number of generated constraints */
246  int childnodessize, /**< available size of childnodes array */
247  SCIP_Bool* success /**< pointer store the result*/
248  );
249 
250 /** remove the stored information about bound changes based in dual information
251  *
252  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
253  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
254  *
255  * @pre This method can be called if @p scip is in one of the following stages:
256  * - \ref SCIP_STAGE_SOLVING
257  * - \ref SCIP_STAGE_SOLVED
258  */
261  SCIP* scip, /**< SCIP data structure */
262  SCIP_NODE* node /**< node of the search tree */
263  );
264 
265 /** splits the root into several nodes and moves the child nodes of the root to one of the created nodes
266  *
267  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
268  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
269  *
270  * @pre This method can be called if @p scip is in one of the following stages:
271  * - \ref SCIP_STAGE_TRANSFORMED
272  * - \ref SCIP_STAGE_SOLVING
273  */
276  SCIP* scip, /**< SCIP data structure */
277  int* ncreatedchilds, /**< pointer to store the number of created nodes */
278  int* naddedconss /**< pointer to store the number added constraints */
279  );
280 
281 /** returns if a node should be reoptimized */
284  SCIP* scip, /**< SCIP data structure */
285  SCIP_NODE* node /**< node of the search tree */
286  );
287 
288 /** deletes the given reoptimization node
289  *
290  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
291  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
292  *
293  * @pre This method can be called if @p scip is in one of the following stages:
294  * - \ref SCIP_STAGE_SOLVING
295  */
298  SCIP* scip, /**< SCIP data structure */
299  SCIP_REOPTNODE** reoptnode /**< node of the reoptimization tree */
300  );
301 
302 /** return the similarity between two objective functions */
305  SCIP* scip, /**< SCIP data structure */
306  int run1, /**< number of run */
307  int run2 /**< number of run */
308  );
309 
310 /** check the changes of the variable coefficient in the objective function */
312 void SCIPgetVarCoefChg(
313  SCIP* scip, /**< SCIP data structure */
314  int varidx, /**< index of variable */
315  SCIP_Bool* negated, /**< coefficient changed the sign */
316  SCIP_Bool* entering, /**< coefficient gets non-zero coefficient */
317  SCIP_Bool* leaving /**< coefficient gets zero coefficient */
318  );
319 
320 /* @} */
321 
322 #ifdef __cplusplus
323 }
324 #endif
325 
326 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_EXPORT SCIP_RETCODE SCIPfreeRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
Definition: scip_reopt.c:338
SCIP_EXPORT SCIP_RETCODE SCIPinitRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
Definition: scip_reopt.c:279
SCIP_EXPORT SCIP_Real SCIPgetReoptSimilarity(SCIP *scip, int run1, int run2)
Definition: scip_reopt.c:397
static long bound
#define SCIP_EXPORT
Definition: def.h:98
SCIP_EXPORT SCIP_RETCODE SCIPsetReoptCompression(SCIP *scip, SCIP_REOPTNODE **representation, int nrepresentatives, SCIP_Bool *success)
Definition: scip_reopt.c:194
SCIP_EXPORT SCIP_RETCODE SCIPgetReoptChildIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int mem, int *nids)
Definition: scip_reopt.c:59
SCIP_EXPORT void SCIPgetReoptnodePath(SCIP *scip, SCIP_REOPTNODE *reoptnode, SCIP_VAR **vars, SCIP_Real *vals, SCIP_BOUNDTYPE *boundtypes, int mem, int *nvars, int *nafterdualvars)
Definition: scip_reopt.c:250
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_EXPORT SCIP_RETCODE SCIPgetReoptLeaveIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int mem, int *nids)
Definition: scip_reopt.c:91
type definitions for return codes for SCIP methods
type definitions for collecting reoptimization information
SCIP_EXPORT SCIP_RETCODE SCIPsplitReoptRoot(SCIP *scip, int *ncreatedchilds, int *naddedconss)
Definition: scip_reopt.c:479
type definitions for LP management
SCIP_EXPORT SCIP_RETCODE SCIPaddReoptnodeCons(SCIP *scip, SCIP_REOPTNODE *reoptnode, SCIP_VAR **vars, SCIP_Real *vals, SCIP_BOUNDTYPE *boundtypes, SCIP_Real lhs, SCIP_Real rhs, int nvars, REOPT_CONSTYPE constype, SCIP_Bool linear)
Definition: scip_reopt.c:222
type definitions for SCIP&#39;s main datastructure
type definitions for problem variables
#define SCIP_Bool
Definition: def.h:70
type definitions for branch and bound tree
SCIP_EXPORT void SCIPgetVarCoefChg(SCIP *scip, int varidx, SCIP_Bool *negated, SCIP_Bool *entering, SCIP_Bool *leaving)
SCIP_EXPORT int SCIPgetNReoptnodes(SCIP *scip, SCIP_NODE *node)
Definition: scip_reopt.c:116
SCIP_EXPORT SCIP_RETCODE SCIPapplyReopt(SCIP *scip, SCIP_REOPTNODE *reoptnode, unsigned int id, SCIP_Real estimate, SCIP_NODE **childnodes, int *ncreatedchilds, int *naddedconss, int childnodessize, SCIP_Bool *success)
Definition: scip_reopt.c:372
#define SCIP_Real
Definition: def.h:164
SCIP_EXPORT SCIP_RETCODE SCIPresetReoptnodeDualcons(SCIP *scip, SCIP_NODE *node)
Definition: scip_reopt.c:506
SCIP_EXPORT SCIP_Bool SCIPreoptimizeNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_reopt.c:414
SCIP_EXPORT int SCIPgetNReoptLeaves(SCIP *scip, SCIP_NODE *node)
Definition: scip_reopt.c:131
SCIP_EXPORT SCIP_RETCODE SCIPdeleteReoptnode(SCIP *scip, SCIP_REOPTNODE **reoptnode)
Definition: scip_reopt.c:454
enum Reopt_ConsType REOPT_CONSTYPE
Definition: type_reopt.h:67
common defines and data types used in all packages of SCIP
SCIP_REOPTNODE * SCIPgetReoptnode(SCIP *scip, unsigned int id)
Definition: scip_reopt.c:144
SCIP_RETCODE SCIPresetRepresentation(SCIP *scip, SCIP_REOPTNODE **representatives, int nrepresentatives)
Definition: scip_reopt.c:309
SCIP_EXPORT SCIP_RETCODE SCIPaddReoptnodeBndchg(SCIP *scip, SCIP_REOPTNODE *reoptnode, SCIP_VAR *var, SCIP_Real bound, SCIP_BOUNDTYPE boundtype)
Definition: scip_reopt.c:166