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