Scippy

SCIP

Solving Constraint Integer Programs

nodesel_bfs.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 nodesel_bfs.c
17  * @brief node selector for best first search
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/nodesel_bfs.h"
27 
28 
29 #define NODESEL_NAME "bfs"
30 #define NODESEL_DESC "best first search"
31 #define NODESEL_STDPRIORITY 100000
32 #define NODESEL_MEMSAVEPRIORITY 0
33 
34 
35 /*
36  * Default parameter settings
37  */
38 
39 #define MINPLUNGEDEPTH -1 /**< minimal plunging depth, before new best node may be selected (-1 for dynamic setting) */
40 #define MAXPLUNGEDEPTH -1 /**< maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting) */
41 #define MAXPLUNGEQUOT 0.25 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
42  * where plunging is performed */
43 
44 
45 /** node selector data for best first search node selection */
46 struct SCIP_NodeselData
47 {
48  SCIP_Real maxplungequot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
49  * where plunging is performed */
50  int minplungedepth; /**< minimal plunging depth, before new best node may be selected
51  * (-1 for dynamic setting) */
52  int maxplungedepth; /**< maximal plunging depth, before new best node is forced to be selected
53  * (-1 for dynamic setting) */
54 };
55 
56 
57 /*
58  * Callback methods
59  */
60 
61 /** copy method for node selector plugins (called when SCIP copies plugins) */
62 static
63 SCIP_DECL_NODESELCOPY(nodeselCopyBfs)
64 { /*lint --e{715}*/
65  assert(scip != NULL);
66  assert(nodesel != NULL);
67  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
68 
69  /* call inclusion method of node selector */
71 
72  return SCIP_OKAY;
73 }
74 
75 /** destructor of node selector to free user data (called when SCIP is exiting) */
76 /**! [SnippetNodeselFreeBfs] */
77 static
78 SCIP_DECL_NODESELFREE(nodeselFreeBfs)
79 { /*lint --e{715}*/
80  SCIP_NODESELDATA* nodeseldata;
81 
82  assert(nodesel != NULL);
83  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
84  assert(scip != NULL);
85 
86  /* free user data of node selector */
87  nodeseldata = SCIPnodeselGetData(nodesel);
88  assert(nodeseldata != NULL);
89  SCIPfreeBlockMemory(scip, &nodeseldata);
90  SCIPnodeselSetData(nodesel, nodeseldata);
91 
92  return SCIP_OKAY;
93 }
94 /**! [SnippetNodeselFreeBfs] */
95 
96 
97 /** node selection method of node selector */
98 static
99 SCIP_DECL_NODESELSELECT(nodeselSelectBfs)
100 { /*lint --e{715}*/
101  SCIP_NODESELDATA* nodeseldata;
102  int minplungedepth;
103  int maxplungedepth;
104  int plungedepth;
105  SCIP_Real maxplungequot;
106 
107  assert(nodesel != NULL);
108  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
109  assert(scip != NULL);
110  assert(selnode != NULL);
111 
112  *selnode = NULL;
113 
114  /* get node selector user data */
115  nodeseldata = SCIPnodeselGetData(nodesel);
116  assert(nodeseldata != NULL);
117 
118  /* calculate minimal and maximal plunging depth */
119  minplungedepth = nodeseldata->minplungedepth;
120  maxplungedepth = nodeseldata->maxplungedepth;
121  maxplungequot = nodeseldata->maxplungequot;
122  if( minplungedepth == -1 )
123  {
124  minplungedepth = SCIPgetMaxDepth(scip)/10;
126  minplungedepth += 10;
127  if( maxplungedepth >= 0 )
128  minplungedepth = MIN(minplungedepth, maxplungedepth);
129  }
130  if( maxplungedepth == -1 )
131  maxplungedepth = SCIPgetMaxDepth(scip)/2;
132  maxplungedepth = MAX(maxplungedepth, minplungedepth);
133 
134  /* check, if we exceeded the maximal plunging depth */
135  plungedepth = SCIPgetPlungeDepth(scip);
136  if( plungedepth >= maxplungedepth )
137  {
138  /* we don't want to plunge again: select best node from the tree */
139  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d -> abort plunging\n", minplungedepth, maxplungedepth, plungedepth);
140  *selnode = SCIPgetBestNode(scip);
141  SCIPdebugMsg(scip, " -> best node : lower=%g\n",
142  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
143  }
144  else
145  {
146  SCIP_NODE* node;
147  SCIP_Real maxbound;
148 
149  /* check, if plunging is forced at the current depth */
150  if( plungedepth < minplungedepth )
151  {
152  maxbound = SCIPinfinity(scip);
153  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d => maxbound: infinity\n",
154  minplungedepth, maxplungedepth, plungedepth);
155  }
156  else
157  {
158  SCIP_Real lowerbound;
159  SCIP_Real cutoffbound;
160  /* get global lower and cutoff bound */
161  lowerbound = SCIPgetLowerbound(scip);
162  cutoffbound = SCIPgetCutoffbound(scip);
163 
164  /* if we didn't find a solution yet, the cutoff bound is usually very bad:
165  * use only 20% of the gap as cutoff bound
166  */
167  if( SCIPgetNSolsFound(scip) == 0 )
168  cutoffbound = lowerbound + 0.2 * (cutoffbound - lowerbound);
169  /* calculate maximal plunging bound */
170  maxbound = lowerbound + maxplungequot * (cutoffbound - lowerbound);
171 
172  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d, bounds: [%g,%g], maxbound: %g\n",
173  minplungedepth, maxplungedepth, plungedepth, lowerbound, cutoffbound, maxbound);
174  }
175 
176  /* we want to plunge again: prefer children over siblings, and siblings over leaves,
177  * but only select a child or sibling, if its dual bound is small enough;
178  * prefer using nodes with higher node selection priority assigned by the branching rule
179  */
180  node = SCIPgetPrioChild(scip);
181  if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
182  {
183  *selnode = node;
184  SCIPdebugMsg(scip, " -> selected prio child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
185  }
186  else
187  {
188  node = SCIPgetBestChild(scip);
189  if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
190  {
191  *selnode = node;
192  SCIPdebugMsg(scip, " -> selected best child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
193  }
194  else
195  {
196  node = SCIPgetPrioSibling(scip);
197  if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
198  {
199  *selnode = node;
200  SCIPdebugMsg(scip, " -> selected prio sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
201  }
202  else
203  {
204  node = SCIPgetBestSibling(scip);
205  if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
206  {
207  *selnode = node;
208  SCIPdebugMsg(scip, " -> selected best sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
209  }
210  else
211  {
212  *selnode = SCIPgetBestNode(scip);
213  SCIPdebugMsg(scip, " -> selected best leaf: lower=%g\n",
214  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
215  }
216  }
217  }
218  }
219  }
220 
221  return SCIP_OKAY;
222 }
223 
224 
225 /** node comparison method of node selector */
226 static
227 SCIP_DECL_NODESELCOMP(nodeselCompBfs)
228 { /*lint --e{715}*/
229  SCIP_Real lowerbound1;
230  SCIP_Real lowerbound2;
231 
232  assert(nodesel != NULL);
233  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
234  assert(scip != NULL);
235 
236  lowerbound1 = SCIPnodeGetLowerbound(node1);
237  lowerbound2 = SCIPnodeGetLowerbound(node2);
238  if( SCIPisLT(scip, lowerbound1, lowerbound2) )
239  return -1;
240  else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
241  return +1;
242  else
243  {
244  SCIP_Real estimate1;
245  SCIP_Real estimate2;
246 
247  estimate1 = SCIPnodeGetEstimate(node1);
248  estimate2 = SCIPnodeGetEstimate(node2);
249  if( (SCIPisInfinity(scip, estimate1) && SCIPisInfinity(scip, estimate2)) ||
250  (SCIPisInfinity(scip, -estimate1) && SCIPisInfinity(scip, -estimate2)) ||
251  SCIPisEQ(scip, estimate1, estimate2) )
252  {
253  SCIP_NODETYPE nodetype1;
254  SCIP_NODETYPE nodetype2;
255 
256  nodetype1 = SCIPnodeGetType(node1);
257  nodetype2 = SCIPnodeGetType(node2);
258  if( nodetype1 == SCIP_NODETYPE_CHILD && nodetype2 != SCIP_NODETYPE_CHILD )
259  return -1;
260  else if( nodetype1 != SCIP_NODETYPE_CHILD && nodetype2 == SCIP_NODETYPE_CHILD )
261  return +1;
262  else if( nodetype1 == SCIP_NODETYPE_SIBLING && nodetype2 != SCIP_NODETYPE_SIBLING )
263  return -1;
264  else if( nodetype1 != SCIP_NODETYPE_SIBLING && nodetype2 == SCIP_NODETYPE_SIBLING )
265  return +1;
266  else
267  {
268  int depth1;
269  int depth2;
270 
271  depth1 = SCIPnodeGetDepth(node1);
272  depth2 = SCIPnodeGetDepth(node2);
273  if( depth1 < depth2 )
274  return -1;
275  else if( depth1 > depth2 )
276  return +1;
277  else
278  return 0;
279  }
280  }
281 
282  if( SCIPisLT(scip, estimate1, estimate2) )
283  return -1;
284 
285  assert(SCIPisGT(scip, estimate1, estimate2));
286  return +1;
287  }
288 }
289 
290 
291 /*
292  * bfs specific interface methods
293  */
294 
295 /** creates the node selector for best first search and includes it in SCIP */
297  SCIP* scip /**< SCIP data structure */
298  )
299 {
300  SCIP_NODESELDATA* nodeseldata;
301  SCIP_NODESEL* nodesel;
302 
303  /* allocate and initialize node selector data; this has to be freed in the destructor */
304  SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );
305 
306  /* include node selector */
308  nodeselSelectBfs, nodeselCompBfs, nodeseldata) );
309 
310  assert(nodesel != NULL);
311 
312  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyBfs) );
313  SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeBfs) );
314 
315  /* add node selector parameters */
317  "nodeselection/bfs/minplungedepth",
318  "minimal plunging depth, before new best node may be selected (-1 for dynamic setting)",
319  &nodeseldata->minplungedepth, TRUE, MINPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
321  "nodeselection/bfs/maxplungedepth",
322  "maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting)",
323  &nodeseldata->maxplungedepth, TRUE, MAXPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
325  "nodeselection/bfs/maxplungequot",
326  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where plunging is performed",
327  &nodeseldata->maxplungequot, TRUE, MAXPLUNGEQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
328 
329  return SCIP_OKAY;
330 }
331 
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip.c:8861
int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip.c:43154
#define NODESEL_STDPRIORITY
Definition: nodesel_bfs.c:31
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7360
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
Definition: scip.c:43613
SCIP_RETCODE SCIPincludeNodeselBasic(SCIP *scip, SCIP_NODESEL **nodesel, const char *name, const char *desc, int stdpriority, int memsavepriority, SCIP_DECL_NODESELSELECT((*nodeselselect)), SCIP_DECL_NODESELCOMP((*nodeselcomp)), SCIP_NODESELDATA *nodeseldata)
Definition: scip.c:8825
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:43089
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip.c:41643
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
#define MINPLUNGEDEPTH
Definition: nodesel_bfs.c:39
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7350
#define MAXPLUNGEQUOT
Definition: nodesel_bfs.c:41
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4265
SCIP_RETCODE SCIPincludeNodeselBfs(SCIP *scip)
Definition: nodesel_bfs.c:297
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:38
static SCIP_DECL_NODESELFREE(nodeselFreeBfs)
Definition: nodesel_bfs.c:79
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
#define NODESEL_DESC
Definition: nodesel_bfs.c:30
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1069
#define MAXPLUNGEDEPTH
Definition: nodesel_bfs.c:40
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Real SCIPgetLowerbound(SCIP *scip)
Definition: scip.c:43271
#define NODESEL_NAME
Definition: nodesel_bfs.c:29
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
Definition: scip.c:42648
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip.c:41675
static SCIP_DECL_NODESELCOPY(nodeselCopyBfs)
Definition: nodesel_bfs.c:64
#define MAX(x, y)
Definition: tclique_def.h:75
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1001
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip.c:41611
#define SCIP_REAL_MAX
Definition: def.h:150
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7370
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:44
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_bfs.c:32
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
SCIP_Longint SCIPgetNStrongbranchLPIterations(SCIP *scip)
Definition: scip.c:42756
node selector for best first search
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: scip.c:8877
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7330
#define SCIP_Real
Definition: def.h:149
static SCIP_DECL_NODESELCOMP(nodeselCompBfs)
Definition: nodesel_bfs.c:228
static SCIP_DECL_NODESELSELECT(nodeselSelectBfs)
Definition: nodesel_bfs.c:100
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip.c:41595
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip.c:41627
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1079
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4321