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-2020 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
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
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 */
241 
242  return SCIP_OKAY;
243 }
244 
245 /** branching execution method for fractional LP solutions */
246 static
247 SCIP_DECL_BRANCHEXECLP(branchExeclpNodereopt)
248 {/*lint --e{715}*/
249  assert(branchrule != NULL );
250  assert(*result != SCIP_BRANCHED);
251 
252  *result = SCIP_DIDNOTRUN;
253 
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  {
286 
287  SCIP_CALL( Exec(scip, result) );
288  }
289  }
290 
291  return SCIP_OKAY;
292 }
293 
294 /** branching execution method for external candidates */
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 
303  {
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 */
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 
322  {
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 */
338  SCIP* scip /**< SCIP data structure */
339  )
340 {
341  SCIP_BRANCHRULE* branchrule;
342 
343  assert(scip != NULL );
344 
345  /* include nodereopt branching rule */
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 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
reliable pseudo costs branching rule
static SCIP_DECL_BRANCHCOPY(branchCopyNodereopt)
internal methods for branch and bound tree
static SCIP_RETCODE Exec(SCIP *scip, SCIP_RESULT *result)
#define BRANCHRULE_MAXDEPTH
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip_solve.c:3446
SCIP_Real SCIPgetReoptSimilarity(SCIP *scip, int run1, int run2)
Definition: scip_reopt.c:398
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_RETCODE SCIPcheckReoptRestart(SCIP *scip, SCIP_NODE *node, SCIP_Bool *restart)
Definition: scip_solve.c:3506
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7420
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
#define FALSE
Definition: def.h:73
SCIP_RETCODE SCIPgetReoptChildIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int idssize, int *nids)
Definition: scip_reopt.c:60
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7430
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define BRANCHRULE_DESC
public methods for reoptimization
SCIP_EXPORT int SCIPreoptnodeGetNChildren(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5858
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:107
nodereopt branching rule
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
int SCIPgetNReoptRuns(SCIP *scip)
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_EXPORT unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7491
SCIP_RETCODE SCIPsplitReoptRoot(SCIP *scip, int *ncreatedchilds, int *naddedconss)
Definition: scip_reopt.c:480
static SCIP_DECL_BRANCHEXECPS(branchExecpsNodereopt)
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:100
static SCIP_DECL_BRANCHEXECLP(branchExeclpNodereopt)
#define NULL
Definition: lpi_spx1.cpp:155
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:58
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPincludeBranchruleNodereopt(SCIP *scip)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIP_Bool
Definition: def.h:70
#define BRANCHRULE_PRIORITY
SCIP_EXPORT SCIP_REOPTTYPE SCIPreoptnodeGetType(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5878
SCIP_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
#define BRANCHRULE_MAXBOUNDDIST
SCIP_EXPORT SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7450
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:256
static SCIP_DECL_BRANCHEXECEXT(branchExecextNodereopt)
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:373
#define SCIP_Real
Definition: def.h:163
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
SCIP_Bool SCIPreoptimizeNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_reopt.c:415
#define BRANCHRULE_NAME
SCIP_REOPTNODE * SCIPgetReoptnode(SCIP *scip, unsigned int id)
Definition: scip_reopt.c:145
SCIP callable library.
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115