Scippy

SCIP

Solving Constraint Integer Programs

branch_nodereopt.c
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 branch_nodereopt.c
26 * @ingroup DEFPLUGINS_BRANCH
27 * @brief branching rule to reconstruct the search tree
28 * @author Jakob Witzig
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32#include <assert.h>
33#include <string.h>
34
37#include "scip/scip.h"
38#include "scip/tree.h"
39#include "scip/pub_reopt.h"
40
41#define BRANCHRULE_NAME "nodereopt"
42#define BRANCHRULE_DESC "branching rule for node reoptimization"
43#define BRANCHRULE_PRIORITY -9000000
44#define BRANCHRULE_MAXDEPTH -1
45#define BRANCHRULE_MAXBOUNDDIST 1.0
46
47/*
48 * Data structures
49 */
50
51
52/** execute the branching of nodes with additional constraints */
53static
55 SCIP* scip, /**< SCIP data structure */
56 SCIP_RESULT* result /**< pointer to store the result */
57 )
58{
59 SCIP_REOPTNODE* reoptnode;
60 SCIP_NODE* curnode;
61 SCIP_REOPTTYPE reopttype;
62 SCIP_Bool localrestart;
63 unsigned int* childids;
64 unsigned int curid;
65 int naddedconss;
66 int nchilds;
67 int childnodessize;
68 int ncreatednodes;
69 int c;
70
71 assert(scip != NULL );
72 assert(SCIPisReoptEnabled(scip));
73
74 curnode = SCIPgetCurrentNode(scip);
75 assert(curnode != NULL);
76
77 curid = SCIPnodeGetReoptID(curnode);
78 assert(curid >= 1 || SCIPgetRootNode(scip) == curnode);
79
80 /* calculate local similarity and delete the induced subtree if the similarity is to low */
81 localrestart = FALSE;
82 SCIP_CALL( SCIPcheckReoptRestart(scip, curnode, &localrestart) );
83
84 ncreatednodes = 0;
85
86 if( localrestart )
87 {
88 *result = SCIP_DIDNOTRUN;
89 goto TERMINATE;
90 }
91
92 SCIPdebugMsg(scip, "current node is %lld, ID %u:\n", SCIPnodeGetNumber(curnode), curid);
93
94 /* get the corresponding node of the reoptimization tree */
95 reoptnode = SCIPgetReoptnode(scip, curid);
96 assert(reoptnode != NULL);
97 reopttype = (SCIP_REOPTTYPE)SCIPreoptnodeGetType(reoptnode);
98
99 /* The current node is equal to the root and dual reductions were performed. Since the root has a special role
100 * within the reoptimiziation we have to split the root node into several nodes and move all stored child nodes to
101 * the one representing the root node including all dual reductions as before.
102 *
103 * @note If the type is infsubtree, there cannot exist a child node and the method SCIPapplyReopt adds a global valid
104 * constraint only.
105 */
106 if( curid == 0 )
107 {
108 if( reopttype == SCIP_REOPTTYPE_STRBRANCHED || reopttype == SCIP_REOPTTYPE_INFSUBTREE )
109 {
110 int ncreatedchilds;
111
112 /* apply the reoptimization at the root node */
113 SCIP_CALL( SCIPsplitReoptRoot(scip, &ncreatedchilds, &naddedconss) );
114
115 if( reopttype == SCIP_REOPTTYPE_INFSUBTREE )
116 {
117 assert(ncreatedchilds == 0);
118 assert(naddedconss == 1);
119
120 /* there is nothing to do */
121 *result = SCIP_DIDNOTRUN;
122
123 goto TERMINATE;
124 }
125
126 assert(reopttype == SCIP_REOPTTYPE_STRBRANCHED);
127 assert(ncreatedchilds >= 2);
128
129 ncreatednodes += ncreatedchilds;
130
131 /* We decrease the counter by one because after splitting the root node and moving all children to the node
132 * representing the original root with all fixings (caused by dual reductions), we continue reactivating the
133 * original children nodes of the root. Thus, the node containing all the fixings can be replaced by the children
134 * nodes
135 */
136 --ncreatednodes;
137 }
138
139 goto REVIVE;
140 }
141
142 /* if we reach this part of the code the current has to be different to the root node */
143 assert(curid >= 1);
144
145 REVIVE:
146
147 /* get the IDs of all child nodes */
148 childnodessize = SCIPreoptnodeGetNChildren(reoptnode);
149 SCIP_CALL( SCIPallocBufferArray(scip, &childids, childnodessize) );
150 SCIP_CALL( SCIPgetReoptChildIDs(scip, curnode, childids, childnodessize, &nchilds) );
151
152 if( childnodessize < nchilds )
153 {
154 childnodessize = SCIPreoptnodeGetNChildren(reoptnode);
155 SCIP_CALL( SCIPreallocBufferArray(scip, &childids, childnodessize) );
156 SCIP_CALL( SCIPgetReoptChildIDs(scip, curnode, childids, childnodessize, &nchilds) );
157 }
158 assert(nchilds <= childnodessize);
159
160 naddedconss = 0;
161
162 for(c = 0; c < nchilds; c++)
163 {
164 SCIP_NODE** childnodes;
165 SCIP_Bool success;
166 unsigned int childid;
167 int ncreatedchilds;
168
169 childid = childids[c];
170 assert(childid >= 1);
171
172 SCIPdebugMsg(scip, "process child at ID %u\n", childid);
173
174 reoptnode = SCIPgetReoptnode(scip, childid);
175 assert(reoptnode != NULL);
176
177 reopttype = (SCIP_REOPTTYPE)SCIPreoptnodeGetType(reoptnode);
178 ncreatedchilds = 0;
179
180 /* check whether node need to be split */
181 if( reopttype == SCIP_REOPTTYPE_STRBRANCHED || reopttype == SCIP_REOPTTYPE_INFSUBTREE )
182 {
183 /* by default we assume the node get split into two node (because using a constraint to split the node is
184 * the default case */
185 childnodessize = 2;
186 }
187 else
188 {
189 /* we only need to reconstruct the node */
190 childnodessize = 1;
191 }
192
193 /* allocate buffer */
194 SCIP_CALL( SCIPallocBufferArray(scip, &childnodes, childnodessize) );
195
196 /* apply the reoptimization */
197 SCIP_CALL( SCIPapplyReopt(scip, reoptnode, childid, SCIPnodeGetEstimate(curnode), childnodes, &ncreatedchilds,
198 &naddedconss, childnodessize, &success) );
199
200 if( !success )
201 {
202 assert(ncreatedchilds > childnodessize);
203
204 /* reallocate buffer memory */
205 childnodessize = ncreatedchilds+1;
206 SCIP_CALL( SCIPreallocBufferArray(scip, &childnodes, childnodessize) );
207
208 /* apply the reoptimization */
209 SCIP_CALL( SCIPapplyReopt(scip, reoptnode, childid, SCIPnodeGetEstimate(curnode), childnodes, &ncreatedchilds,
210 &naddedconss, childnodessize, &success) );
211 }
212
213 assert(success);
214
215 /* free buffer memory */
216 SCIPfreeBufferArray(scip, &childnodes);
217
218 ncreatednodes += ncreatedchilds;
219 }
220
221 if( ncreatednodes == 0 )
222 *result = SCIP_DIDNOTRUN;
223 else
224 *result = SCIP_BRANCHED;
225
226 /* free the buffer memory */
227 SCIPfreeBufferArray(scip, &childids);
228
229 TERMINATE:
230
231 SCIPdebugMsg(scip, "**** finish reoptimizing %d child nodes of node %lld ****\n", ncreatednodes, SCIPnodeGetNumber(curnode));
232
233 return SCIP_OKAY;
234}
235
236/*
237 * Callback methods of branching rule
238 */
239
240/** copy method for branchrule plugins (called when SCIP copies plugins) */
241static
242SCIP_DECL_BRANCHCOPY(branchCopyNodereopt)
243{ /*lint --e{715}*/
244 assert(scip != NULL);
245 assert(branchrule != NULL);
246 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
247
248 /* call inclusion method of branchrule */
250
251 return SCIP_OKAY;
252}
253
254/** branching execution method for fractional LP solutions */
255static
256SCIP_DECL_BRANCHEXECLP(branchExeclpNodereopt)
257{/*lint --e{715}*/
258 assert(branchrule != NULL );
259 assert(*result != SCIP_BRANCHED);
260
261 *result = SCIP_DIDNOTRUN;
262
264 {
265 SCIP_VAR** branchcands;
266 SCIP_Real* branchcandssol;
267 SCIP_Real* branchcandsfrac;
268 SCIP_Real objsimrootlp;
269 SCIP_Bool sbinit;
270 int nbranchcands;
271
272 assert(SCIPgetNReoptRuns(scip) > 1);
273
274 SCIP_CALL( SCIPgetBoolParam(scip, "reoptimization/strongbranchinginit", &sbinit) );
275 SCIP_CALL( SCIPgetRealParam(scip, "reoptimization/objsimrootLP", &objsimrootlp) );
276
278 && SCIPgetReoptSimilarity(scip, SCIPgetNReoptRuns(scip)-1, SCIPgetNReoptRuns(scip)) <= objsimrootlp ) /* check objsimrootlp */
279 {
280 /* get branching candidates */
281 SCIP_CALL( SCIPgetLPBranchCands(scip, &branchcands, &branchcandssol, &branchcandsfrac, NULL, &nbranchcands, NULL) );
282
283 /* run strong branching initialization */
284 if( nbranchcands > 0 )
285 {
286 SCIP_CALL( SCIPexecRelpscostBranching(scip, branchcands, branchcandssol, branchcandsfrac, nbranchcands, FALSE, result) );
287 assert(*result == SCIP_DIDNOTRUN || *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM || *result == SCIP_CONSADDED);
288 }
289 }
290
291 if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
292 {
295
296 SCIP_CALL( Exec(scip, result) );
297 }
298 }
299
300 return SCIP_OKAY;
301}
302
303/** branching execution method for external candidates */
304static SCIP_DECL_BRANCHEXECEXT(branchExecextNodereopt)
305{/*lint --e{715}*/
306 assert(branchrule != NULL );
307 assert(*result != SCIP_BRANCHED);
308
309 *result = SCIP_DIDNOTRUN;
310
312 {
315
316 SCIP_CALL( Exec(scip, result) );
317 }
318
319 return SCIP_OKAY;
320}
321
322/** branching execution method for not completely fixed pseudo solutions */
323static SCIP_DECL_BRANCHEXECPS(branchExecpsNodereopt)
324{/*lint --e{715}*/
325 assert(branchrule != NULL );
326 assert(*result != SCIP_BRANCHED);
327
328 *result = SCIP_DIDNOTRUN;
329
331 {
334
335 SCIP_CALL( Exec(scip, result) );
336 }
337
338 return SCIP_OKAY;
339}
340
341/*
342 * branching rule specific interface methods
343 */
344
345/** creates the nodereopt branching rule and includes it in SCIP */
347 SCIP* scip /**< SCIP data structure */
348 )
349{
350 SCIP_BRANCHRULE* branchrule;
351
352 assert(scip != NULL );
353
354 /* include nodereopt branching rule */
357
358 assert(branchrule != NULL );
359
360 /* set non fundamental callbacks via setter functions */
361 SCIP_CALL(SCIPsetBranchruleCopy(scip, branchrule, branchCopyNodereopt));
362 SCIP_CALL(SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpNodereopt));
363 SCIP_CALL(SCIPsetBranchruleExecExt(scip, branchrule, branchExecextNodereopt));
364 SCIP_CALL(SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsNodereopt));
365
366 return SCIP_OKAY;
367}
#define BRANCHRULE_DESC
static SCIP_DECL_BRANCHEXECEXT(branchExecextNodereopt)
#define BRANCHRULE_PRIORITY
static SCIP_DECL_BRANCHEXECLP(branchExeclpNodereopt)
static SCIP_DECL_BRANCHEXECPS(branchExecpsNodereopt)
#define BRANCHRULE_NAME
static SCIP_DECL_BRANCHCOPY(branchCopyNodereopt)
static SCIP_RETCODE Exec(SCIP *scip, SCIP_RESULT *result)
#define BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
nodereopt branching rule
reliable pseudo costs branching rule
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
SCIP_RETCODE SCIPincludeBranchruleNodereopt(SCIP *scip)
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:265
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:116
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7523
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7564
SCIP_REOPTNODE * SCIPgetReoptnode(SCIP *scip, unsigned int id)
Definition: scip_reopt.c:154
SCIP_Bool SCIPreoptimizeNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_reopt.c:424
SCIP_RETCODE SCIPcheckReoptRestart(SCIP *scip, SCIP_NODE *node, SCIP_Bool *restart)
Definition: scip_solve.c:3558
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip_solve.c:3498
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
SCIP_Real SCIPgetReoptSimilarity(SCIP *scip, int run1, int run2)
Definition: scip_reopt.c:407
SCIP_RETCODE SCIPsplitReoptRoot(SCIP *scip, int *ncreatedchilds, int *naddedconss)
Definition: scip_reopt.c:489
SCIP_RETCODE SCIPgetReoptChildIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int idssize, int *nids)
Definition: scip_reopt.c:69
int SCIPgetNReoptRuns(SCIP *scip)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:110
public methods for reoptimization
SCIP_REOPTTYPE SCIPreoptnodeGetType(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5874
int SCIPreoptnodeGetNChildren(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5854
SCIP callable library.
internal methods for branch and bound tree
@ SCIP_REOPTTYPE_INFSUBTREE
Definition: type_reopt.h:60
@ SCIP_REOPTTYPE_STRBRANCHED
Definition: type_reopt.h:61
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:67
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_CONSADDED
Definition: type_result.h:52
@ SCIP_BRANCHED
Definition: type_result.h:54
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63