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