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