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-2016 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  * @brief branching rule to reconstruct the search tree
18  * @author Jakob Witzig
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 #include <assert.h>
23 #include <string.h>
24 
25 #include "scip/branch_nodereopt.h"
26 #include "scip/branch_relpscost.h"
27 #include "scip/cons_logicor.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  SCIPdebugMessage("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 
91  /* The current node is equal to the root and dual reductions were performed. Since the root has a special role
92  * within the reoptimiziation we have to split the root node into several nodes and move all stored child nodes to
93  * the one representing the root node including all dual reductions as before.
94  *
95  * @note If the type is infsubtree, there cannot exist a child node and the method SCIPapplyReopt adds a global valid
96  * constraint only.
97  */
98  if( curid == 0 )
99  {
100  if( reopttype == SCIP_REOPTTYPE_STRBRANCHED || reopttype == SCIP_REOPTTYPE_INFSUBTREE )
101  {
102  int ncreatedchilds;
103 
104  /* apply the reoptimization at the root node */
105  SCIP_CALL( SCIPsplitReoptRoot(scip, &ncreatedchilds, &naddedconss) );
106 
107  if( reopttype == SCIP_REOPTTYPE_INFSUBTREE )
108  {
109  assert(ncreatedchilds == 0);
110  assert(naddedconss == 1);
111 
112  /* there is nothing to do */
113  *result = SCIP_DIDNOTRUN;
114 
115  goto TERMINATE;
116  }
117 
118  assert(reopttype == SCIP_REOPTTYPE_STRBRANCHED);
119  assert(ncreatedchilds >= 2);
120 
121  ncreatednodes += ncreatedchilds;
122 
123  /* We decrease the counter by one because after splitting the root node and moving all children to the node
124  * representing the original root with all fixings (caused by dual reductions), we continue reactivating the
125  * original children nodes of the root. Thus, the node containing all the fixings can be replaced by the children
126  * nodes
127  */
128  --ncreatednodes;
129  }
130 
131  goto REVIVE;
132  }
133 
134  /* if we reach this part of the code the current has to be different to the root node */
135  assert(curid >= 1);
136 
137  REVIVE:
138 
139  /* get the IDs of all child nodes */
140  childnodessize = SCIPreoptnodeGetNChildren(reoptnode);
141  SCIP_CALL( SCIPallocBufferArray(scip, &childids, childnodessize) );
142  SCIP_CALL( SCIPgetReoptChildIDs(scip, curnode, childids, childnodessize, &nchilds) );
143 
144  if( childnodessize < nchilds )
145  {
146  childnodessize = SCIPreoptnodeGetNChildren(reoptnode);
147  SCIP_CALL( SCIPreallocBufferArray(scip, &childids, childnodessize) );
148  SCIP_CALL( SCIPgetReoptChildIDs(scip, curnode, childids, childnodessize, &nchilds) );
149  }
150  assert(nchilds <= childnodessize);
151 
152  naddedconss = 0;
153 
154  for(c = 0; c < nchilds; c++)
155  {
156  SCIP_NODE** childnodes;
157  SCIP_Bool success;
158  unsigned int childid;
159  int ncreatedchilds;
160 
161  childid = childids[c];
162  assert(childid >= 1);
163 
164  SCIPdebugMessage("process child at ID %u\n", childid);
165 
166  reoptnode = SCIPgetReoptnode(scip, childid);
167  assert(reoptnode != NULL);
168 
169  reopttype = (SCIP_REOPTTYPE)SCIPreoptnodeGetType(reoptnode);
170  ncreatedchilds = 0;
171 
172  /* check whether node need to be split */
173  if( reopttype == SCIP_REOPTTYPE_STRBRANCHED || reopttype == SCIP_REOPTTYPE_INFSUBTREE )
174  {
175  /* by default we assume the node get split into two node (because using a constraint to split the node is
176  * the default case */
177  childnodessize = 2;
178  }
179  else
180  {
181  /* we only need to reconstruct the node */
182  childnodessize = 1;
183  }
184 
185  /* allocate buffer */
186  SCIP_CALL( SCIPallocBufferArray(scip, &childnodes, childnodessize) );
187 
188  /* apply the reoptimization */
189  SCIP_CALL( SCIPapplyReopt(scip, reoptnode, childid, SCIPnodeGetEstimate(curnode), childnodes, &ncreatedchilds,
190  &naddedconss, childnodessize, &success) );
191 
192  if( !success )
193  {
194  assert(ncreatedchilds > childnodessize);
195 
196  /* reallocate buffer memory */
197  childnodessize = ncreatedchilds+1;
198  SCIP_CALL( SCIPreallocBufferArray(scip, &childnodes, childnodessize) );
199 
200  /* apply the reoptimization */
201  SCIP_CALL( SCIPapplyReopt(scip, reoptnode, childid, SCIPnodeGetEstimate(curnode), childnodes, &ncreatedchilds,
202  &naddedconss, childnodessize, &success) );
203  }
204 
205  assert(success);
206 
207  /* free buffer memory */
208  SCIPfreeBufferArray(scip, &childnodes);
209 
210  ncreatednodes += ncreatedchilds;
211  }
212 
213  if( ncreatednodes == 0 )
214  *result = SCIP_DIDNOTRUN;
215  else
216  *result = SCIP_BRANCHED;
217 
218  /* free the buffer memory */
219  SCIPfreeBufferArray(scip, &childids);
220 
221  TERMINATE:
222 
223  SCIPdebugMessage("**** finish reoptimizing %d child nodes of node %lld ****\n", ncreatednodes, SCIPnodeGetNumber(curnode));
224 
225  return SCIP_OKAY;
226 }
227 
228 /*
229  * Callback methods of branching rule
230  */
231 
232 /** copy method for branchrule plugins (called when SCIP copies plugins) */
233 static
234 SCIP_DECL_BRANCHCOPY(branchCopyNodereopt)
235 { /*lint --e{715}*/
236  assert(scip != NULL);
237  assert(branchrule != NULL);
238  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
239 
240  /* call inclusion method of branchrule */
242 
243  return SCIP_OKAY;
244 }
245 
246 /** branching execution method for fractional LP solutions */
247 static
248 SCIP_DECL_BRANCHEXECLP(branchExeclpNodereopt)
249 {/*lint --e{715}*/
250  assert(branchrule != NULL );
251  assert(*result != SCIP_BRANCHED);
252 
253  *result = SCIP_DIDNOTRUN;
254 
256  {
257  SCIP_VAR** branchcands;
258  SCIP_Real* branchcandssol;
259  SCIP_Real* branchcandsfrac;
260  int nbranchcands;
261 
262  SCIP_Bool sbinit;
263  SCIP_Real objsimrootlp;
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), 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, TRUE, branchcands, branchcandssol, branchcandsfrac, nbranchcands, FALSE, result) );
278  assert(*result == SCIP_DIDNOTRUN || *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM);
279  }
280  }
281 
282  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM)
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  SCIP_BRANCHRULEDATA* branchruledata;
343 
344  assert(scip != NULL );
345 
346  /* no branching rule data */
347  branchruledata = NULL;
348 
349  /* include nodereopt branching rule */
352 
353  assert(branchrule != NULL );
354 
355  /* set non fundamental callbacks via setter functions */
356  SCIP_CALL(SCIPsetBranchruleCopy(scip, branchrule, branchCopyNodereopt));
357  SCIP_CALL(SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpNodereopt));
358  SCIP_CALL(SCIPsetBranchruleExecExt(scip, branchrule, branchExecextNodereopt));
359  SCIP_CALL(SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsNodereopt));
360 
361  return SCIP_OKAY;
362 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:51
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:33125
reliable pseudo costs branching rule
static SCIP_DECL_BRANCHCOPY(branchCopyNodereopt)
SCIP_RETCODE SCIPgetReoptChildIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int idssize, int *nids)
Definition: scip.c:14953
unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7087
internal methods for branch and bound tree
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:20589
static SCIP_RETCODE Exec(SCIP *scip, SCIP_RESULT *result)
#define BRANCHRULE_MAXDEPTH
SCIP_REOPTNODE * SCIPgetReoptnode(SCIP *scip, unsigned int id)
Definition: scip.c:15038
#define NULL
Definition: lpi_spx.cpp:130
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7026
SCIP_RETCODE SCIPsplitReoptRoot(SCIP *scip, int *ncreatedchilds, int *naddedconss)
Definition: scip.c:15642
#define FALSE
Definition: def.h:56
#define TRUE
Definition: def.h:55
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_CALL(x)
Definition: def.h:266
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1877
SCIP_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_Bool allowaddcons, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
#define BRANCHRULE_DESC
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:8290
public methods for reoptimization
#define SCIPdebugMessage
Definition: pub_message.h:77
nodereopt branching rule
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip.c:8420
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7016
static SCIP_DECL_BRANCHEXECPS(branchExecpsNodereopt)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:8388
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.c:8253
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip.c:36798
SCIP_RETCODE SCIPcheckReoptRestart(SCIP *scip, SCIP_NODE *node, SCIP_Bool *restart)
Definition: scip.c:15541
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
static SCIP_DECL_BRANCHEXECLP(branchExeclpNodereopt)
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:56
int SCIPgetNReoptRuns(SCIP *scip)
Definition: scip.c:37345
int SCIPreoptnodeGetNChildren(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:4654
#define SCIP_Bool
Definition: def.h:53
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip.c:8404
#define BRANCHRULE_PRIORITY
#define BRANCHRULE_MAXBOUNDDIST
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:36779
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7046
static SCIP_DECL_BRANCHEXECEXT(branchExecextNodereopt)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:20585
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.c:15261
#define SCIP_Real
Definition: def.h:127
#define BRANCHRULE_NAME
SCIP_Real SCIPgetReoptSimilarity(SCIP *scip, int run1, int run2)
Definition: scip.c:15560
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:20597
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:3797
SCIP_RETCODE SCIPincludeBranchruleNodereopt(SCIP *scip)
SCIP_REOPTTYPE SCIPreoptnodeGetType(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:4674
SCIP_Bool SCIPreoptimizeNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:15577
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip.c:3740
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip.c:15481
SCIP callable library.