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