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-2017 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  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 
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  SCIPdebugMsg(scip, "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  SCIPdebugMsg(scip, "**** 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  SCIP_Real objsimrootlp;
261  SCIP_Bool sbinit;
262  int nbranchcands;
263 
264  assert(SCIPgetNReoptRuns(scip) > 1);
265 
266  SCIP_CALL( SCIPgetBoolParam(scip, "reoptimization/strongbranchinginit", &sbinit) );
267  SCIP_CALL( SCIPgetRealParam(scip, "reoptimization/objsimrootLP", &objsimrootlp) );
268 
269  if( sbinit && SCIPgetCurrentNode(scip) == SCIPgetRootNode(scip)
270  && SCIPgetReoptSimilarity(scip, SCIPgetNReoptRuns(scip)-1, SCIPgetNReoptRuns(scip)) <= objsimrootlp ) /* check objsimrootlp */
271  {
272  /* get branching candidates */
273  SCIP_CALL( SCIPgetLPBranchCands(scip, &branchcands, &branchcandssol, &branchcandsfrac, NULL, &nbranchcands, NULL) );
274 
275  /* run strong branching initialization */
276  if( nbranchcands > 0 )
277  {
278  SCIP_CALL( SCIPexecRelpscostBranching(scip, TRUE, branchcands, branchcandssol, branchcandsfrac, nbranchcands, FALSE, result) );
279  assert(*result == SCIP_DIDNOTRUN || *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM || *result == SCIP_CONSADDED);
280  }
281  }
282 
283  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
284  {
287 
288  SCIP_CALL( Exec(scip, result) );
289  }
290  }
291 
292  return SCIP_OKAY;
293 }
294 
295 /** branching execution method for external candidates */
296 static SCIP_DECL_BRANCHEXECEXT(branchExecextNodereopt)
297 {/*lint --e{715}*/
298  assert(branchrule != NULL );
299  assert(*result != SCIP_BRANCHED);
300 
301  *result = SCIP_DIDNOTRUN;
302 
304  {
307 
308  SCIP_CALL( Exec(scip, result) );
309  }
310 
311  return SCIP_OKAY;
312 }
313 
314 /** branching execution method for not completely fixed pseudo solutions */
315 static SCIP_DECL_BRANCHEXECPS(branchExecpsNodereopt)
316 {/*lint --e{715}*/
317  assert(branchrule != NULL );
318  assert(*result != SCIP_BRANCHED);
319 
320  *result = SCIP_DIDNOTRUN;
321 
323  {
326 
327  SCIP_CALL( Exec(scip, result) );
328  }
329 
330  return SCIP_OKAY;
331 }
332 
333 /*
334  * branching rule specific interface methods
335  */
336 
337 /** creates the nodereopt branching rule and includes it in SCIP */
339  SCIP* scip /**< SCIP data structure */
340  )
341 {
342  SCIP_BRANCHRULE* branchrule;
343 
344  assert(scip != NULL );
345 
346  /* include nodereopt branching rule */
349 
350  assert(branchrule != NULL );
351 
352  /* set non fundamental callbacks via setter functions */
353  SCIP_CALL(SCIPsetBranchruleCopy(scip, branchrule, branchCopyNodereopt));
354  SCIP_CALL(SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpNodereopt));
355  SCIP_CALL(SCIPsetBranchruleExecExt(scip, branchrule, branchExecextNodereopt));
356  SCIP_CALL(SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsNodereopt));
357 
358  return SCIP_OKAY;
359 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36128
reliable pseudo costs branching rule
static SCIP_DECL_BRANCHCOPY(branchCopyNodereopt)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:40453
SCIP_RETCODE SCIPincludeBranchruleNodereopt(SCIP *scip)
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip.c:9168
internal methods for branch and bound tree
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.c:4426
SCIP_Bool SCIPreoptimizeNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:17077
#define FALSE
Definition: def.h:64
#define TRUE
Definition: def.h:63
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:9038
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#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.c:9001
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7153
nodereopt branching rule
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip.c:40472
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9136
static SCIP_DECL_BRANCHEXECPS(branchExecpsNodereopt)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7143
SCIP_RETCODE SCIPgetReoptChildIDs(SCIP *scip, SCIP_NODE *node, unsigned int *ids, int idssize, int *nids)
Definition: scip.c:16383
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
Definition: scip.c:16981
static SCIP_DECL_BRANCHEXECLP(branchExeclpNodereopt)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip.c:4369
#define NULL
Definition: lpi_spx1.cpp:137
enum SCIP_ReoptType SCIP_REOPTTYPE
Definition: type_reopt.h:58
#define SCIP_CALL(x)
Definition: def.h:306
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_RETCODE SCIPcheckReoptRestart(SCIP *scip, SCIP_NODE *node, SCIP_Bool *restart)
Definition: scip.c:17041
int SCIPreoptnodeGetNChildren(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5768
#define SCIP_Bool
Definition: def.h:61
#define BRANCHRULE_PRIORITY
#define BRANCHRULE_MAXBOUNDDIST
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip.c:9152
SCIP_Real SCIPgetReoptSimilarity(SCIP *scip, int run1, int run2)
Definition: scip.c:17060
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7173
static SCIP_DECL_BRANCHEXECEXT(branchExecextNodereopt)
int SCIPgetNReoptRuns(SCIP *scip)
Definition: scip.c:41126
unsigned int SCIPnodeGetReoptID(SCIP_NODE *node)
Definition: tree.c:7214
SCIP_RETCODE SCIPsplitReoptRoot(SCIP *scip, int *ncreatedchilds, int *naddedconss)
Definition: scip.c:17142
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:16696
#define SCIP_Real
Definition: def.h:135
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1896
#define BRANCHRULE_NAME
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)
SCIP_REOPTTYPE SCIPreoptnodeGetType(SCIP_REOPTNODE *reoptnode)
Definition: reopt.c:5788
SCIP_REOPTNODE * SCIPgetReoptnode(SCIP *scip, unsigned int id)
Definition: scip.c:16468
SCIP callable library.
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:21929