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 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 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 
35 #include "scip/branch_nodereopt.h"
36 #include "scip/branch_relpscost.h"
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 */
53 static
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) */
241 static
242 SCIP_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 */
255 static
256 SCIP_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 
277  if( sbinit && SCIPgetCurrentNode(scip) == SCIPgetRootNode(scip)
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 */
304 static 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 */
323 static 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 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
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
reliable pseudo costs branching rule
static SCIP_DECL_BRANCHCOPY(branchCopyNodereopt)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_RETCODE SCIPincludeBranchruleNodereopt(SCIP *scip)
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
internal methods for branch and bound tree
SCIP_RETCODE SCIPcheckReoptRestart(SCIP *scip, SCIP_NODE *node, SCIP_Bool *restart)
Definition: scip_solve.c:3679
static SCIP_RETCODE Exec(SCIP *scip, SCIP_RESULT *result)
#define BRANCHRULE_MAXDEPTH
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIP_Bool SCIPreoptimizeNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_reopt.c:424
#define FALSE
Definition: def.h:96
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define BRANCHRULE_DESC
public methods for reoptimization
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
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7453
nodereopt branching rule
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:110
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip_solve.c:3619
static SCIP_DECL_BRANCHEXECPS(branchExecpsNodereopt)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7443
SCIP_RETCODE SCIPgetReoptChildIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int idssize, int *nids)
Definition: scip_reopt.c:69
static SCIP_DECL_BRANCHEXECLP(branchExeclpNodereopt)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
#define NULL
Definition: lpi_spx1.cpp:164
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:67
#define SCIP_CALL(x)
Definition: def.h:393
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
int SCIPreoptnodeGetNChildren(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5901
#define SCIP_Bool
Definition: def.h:93
#define BRANCHRULE_PRIORITY
#define BRANCHRULE_MAXBOUNDDIST
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:265
SCIP_Real SCIPgetReoptSimilarity(SCIP *scip, int run1, int run2)
Definition: scip_reopt.c:407
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7473
static SCIP_DECL_BRANCHEXECEXT(branchExecextNodereopt)
int SCIPgetNReoptRuns(SCIP *scip)
unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7514
SCIP_RETCODE SCIPsplitReoptRoot(SCIP *scip, int *ncreatedchilds, int *naddedconss)
Definition: scip_reopt.c:489
SCIP_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
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
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
#define BRANCHRULE_NAME
SCIP_REOPTTYPE SCIPreoptnodeGetType(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5921
SCIP_REOPTNODE * SCIPgetReoptnode(SCIP *scip, unsigned int id)
Definition: scip_reopt.c:154
SCIP callable library.
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128