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