Scippy

SCIP

Solving Constraint Integer Programs

nodesel_estimate.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 visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file nodesel_estimate.c
17  * @brief node selector for best estimate 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_estimate.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 <string.h>
35 
36 #define NODESEL_NAME "estimate"
37 #define NODESEL_DESC "best estimate search"
38 #define NODESEL_STDPRIORITY 200000
39 #define NODESEL_MEMSAVEPRIORITY 100
40 
41 
42 /*
43  * Default parameter settings
44  */
45 
46 #define DEFAULT_MINPLUNGEDEPTH -1 /**< minimal plunging depth, before new best node may be selected (-1 for dynamic setting) */
47 #define DEFAULT_MAXPLUNGEDEPTH -1 /**< maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting) */
48 #define DEFAULT_MAXPLUNGEQUOT 0.25 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
49  * where plunging is performed */
50 #define DEFAULT_BESTNODEFREQ 10 /**< frequency at which the best node instead of the best estimate is selected (0: never) */
51 #define DEFAULT_BREADTHFIRSTDEPTH -1 /**< depth until breadth-first search is applied (-1: never) */
52 #define DEFAULT_PLUNGEOFFSET 0 /**< number of nodes before doing plunging the first time */
53 
54 
55 /** node selector data for best estimate search node selection */
56 struct SCIP_NodeselData
57 {
58  SCIP_Real maxplungequot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
59  * where plunging is performed */
60  int minplungedepth; /**< minimal plunging depth, before new best node may be selected
61  * (-1 for dynamic setting) */
62  int maxplungedepth; /**< maximal plunging depth, before new best node is forced to be selected
63  * (-1 for dynamic setting) */
64  int bestnodefreq; /**< frequency at which the best node instead of the best estimate is selected
65  * (0: never) */
66  int breadthfirstdepth; /**< depth until breadth-fisrt search is applied */
67  int plungeoffset; /**< number of nodes before doing plunging the first time */
68 };
69 
70 
71 /*
72  * Callback methods
73  */
74 
75 /** copy method for node selector plugins (called when SCIP copies plugins) */
76 static
77 SCIP_DECL_NODESELCOPY(nodeselCopyEstimate)
78 { /*lint --e{715}*/
79  assert(scip != NULL);
80  assert(nodesel != NULL);
81  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
82 
83  /* call inclusion method of node selector */
85 
86  return SCIP_OKAY;
87 }
88 
89 /** destructor of node selector to free user data (called when SCIP is exiting) */
90 static
91 SCIP_DECL_NODESELFREE(nodeselFreeEstimate)
92 { /*lint --e{715}*/
93  SCIP_NODESELDATA* nodeseldata;
94 
95  assert(nodesel != NULL);
96  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
97  assert(scip != NULL);
98 
99  /* free user data of node selector */
100  nodeseldata = SCIPnodeselGetData(nodesel);
101  assert(nodeseldata != NULL);
102  SCIPfreeBlockMemory(scip, &nodeseldata);
103  SCIPnodeselSetData(nodesel, nodeseldata);
104 
105  return SCIP_OKAY;
106 }
107 
108 
109 /** node selection method of node selector */
110 static
111 SCIP_DECL_NODESELSELECT(nodeselSelectEstimate)
112 { /*lint --e{715}*/
113  SCIP_NODESELDATA* nodeseldata;
114  int minplungedepth;
115  int maxplungedepth;
116  int plungedepth;
117  int bestnodefreq;
118  SCIP_Real maxplungequot;
119 
120  assert(nodesel != NULL);
121  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
122  assert(scip != NULL);
123  assert(selnode != NULL);
124 
125  *selnode = NULL;
126 
127  /* get node selector user data */
128  nodeseldata = SCIPnodeselGetData(nodesel);
129  assert(nodeseldata != NULL);
130 
131  /* check if the breadth-first search should be applied */
132  if( SCIPgetDepth(scip) <= nodeseldata->breadthfirstdepth )
133  {
134  SCIP_NODE* node;
135 
136  SCIPdebugMsg(scip, "perform breadth-first search at depth <%d>\n", SCIPgetDepth(scip));
137 
138  node = SCIPgetPrioSibling(scip);
139  if( node != NULL )
140  {
141  *selnode = node;
142  SCIPdebugMsg(scip, " -> selected prio sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
143  return SCIP_OKAY;
144  }
145 
146  node = SCIPgetPrioChild(scip);
147  if( node != NULL )
148  {
149  *selnode = node;
150  SCIPdebugMsg(scip, " -> selected prio child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
151  return SCIP_OKAY;
152  }
153  }
154 
155  bestnodefreq = (nodeseldata->bestnodefreq == 0 ? INT_MAX : nodeseldata->bestnodefreq);
156 
157  /* check if we don't want to do plunging yet */
158  if( SCIPgetNNodes(scip) < nodeseldata->plungeoffset )
159  {
160  /* we don't want to plunge yet: select best node from the tree */
161  SCIPdebugMsg(scip, "nnodes=%" SCIP_LONGINT_FORMAT " < %d=plungeoffset -> don't start plunging\n", SCIPgetNNodes(scip),
162  nodeseldata->plungeoffset);
163 
164  if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
165  *selnode = SCIPgetBestboundNode(scip);
166  else
167  *selnode = SCIPgetBestNode(scip);
168  SCIPdebugMsg(scip, " -> best node : lower=%g\n",
169  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
170  return SCIP_OKAY;
171  }
172 
173  /* calculate minimal and maximal plunging depth */
174  minplungedepth = nodeseldata->minplungedepth;
175  maxplungedepth = nodeseldata->maxplungedepth;
176  maxplungequot = nodeseldata->maxplungequot;
177  if( minplungedepth == -1 )
178  {
179  minplungedepth = SCIPgetMaxDepth(scip)/10;
181  minplungedepth += 10;
182  if( maxplungedepth >= 0 )
183  minplungedepth = MIN(minplungedepth, maxplungedepth);
184  }
185  if( maxplungedepth == -1 )
186  maxplungedepth = SCIPgetMaxDepth(scip)/2;
187  maxplungedepth = MAX(maxplungedepth, minplungedepth);
188 
189  /* check, if we exceeded the maximal plunging depth */
190  plungedepth = SCIPgetPlungeDepth(scip);
191  if( plungedepth > maxplungedepth )
192  {
193  /* we don't want to plunge again: select best node from the tree */
194  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d -> abort plunging\n", minplungedepth, maxplungedepth, plungedepth);
195  if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
196  *selnode = SCIPgetBestboundNode(scip);
197  else
198  *selnode = SCIPgetBestNode(scip);
199  SCIPdebugMsg(scip, " -> best node : lower=%g\n",
200  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
201  }
202  else
203  {
204  SCIP_NODE* node;
205  SCIP_Real lowerbound;
206  SCIP_Real cutoffbound;
207  SCIP_Real maxbound;
208 
209  /* get global lower and cutoff bound */
210  lowerbound = SCIPgetLowerbound(scip);
211  cutoffbound = SCIPgetCutoffbound(scip);
212 
213  /* if we didn't find a solution yet, the cutoff bound is usually very bad:
214  * use only 20% of the gap as cutoff bound
215  */
216  if( SCIPgetNSolsFound(scip) == 0 )
217  cutoffbound = lowerbound + 0.2 * (cutoffbound - lowerbound);
218 
219  /* check, if plunging is forced at the current depth */
220  if( plungedepth < minplungedepth )
221  maxbound = SCIPinfinity(scip);
222  else
223  {
224  /* calculate maximal plunging bound */
225  maxbound = lowerbound + maxplungequot * (cutoffbound - lowerbound);
226  }
227 
228  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d, bounds: [%g,%g], maxbound: %g\n",
229  minplungedepth, maxplungedepth, plungedepth, lowerbound, cutoffbound, maxbound);
230 
231  /* we want to plunge again: prefer children over siblings, and siblings over leaves,
232  * but only select a child or sibling, if its estimate is small enough;
233  * prefer using nodes with higher node selection priority assigned by the branching rule
234  */
235  node = SCIPgetPrioChild(scip);
236  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
237  {
238  *selnode = node;
239  SCIPdebugMsg(scip, " -> selected prio child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
240  }
241  else
242  {
243  node = SCIPgetBestChild(scip);
244  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
245  {
246  *selnode = node;
247  SCIPdebugMsg(scip, " -> selected best child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
248  }
249  else
250  {
251  node = SCIPgetPrioSibling(scip);
252  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
253  {
254  *selnode = node;
255  SCIPdebugMsg(scip, " -> selected prio sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
256  }
257  else
258  {
259  node = SCIPgetBestSibling(scip);
260  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
261  {
262  *selnode = node;
263  SCIPdebugMsg(scip, " -> selected best sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
264  }
265  else
266  {
267  if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
268  *selnode = SCIPgetBestboundNode(scip);
269  else
270  *selnode = SCIPgetBestNode(scip);
271  SCIPdebugMsg(scip, " -> selected best leaf: estimate=%g\n",
272  *selnode != NULL ? SCIPnodeGetEstimate(*selnode) : SCIPinfinity(scip));
273  }
274  }
275  }
276  }
277  }
278 
279  return SCIP_OKAY;
280 }
281 
282 
283 /** node comparison method of node selector */
284 static
285 SCIP_DECL_NODESELCOMP(nodeselCompEstimate)
286 { /*lint --e{715}*/
287  SCIP_Real estimate1;
288  SCIP_Real estimate2;
289 
290  assert(nodesel != NULL);
291  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
292  assert(scip != NULL);
293 
294  estimate1 = SCIPnodeGetEstimate(node1);
295  estimate2 = SCIPnodeGetEstimate(node2);
296  if( (SCIPisInfinity(scip, estimate1) && SCIPisInfinity(scip, estimate2)) ||
297  (SCIPisInfinity(scip, -estimate1) && SCIPisInfinity(scip, -estimate2)) ||
298  SCIPisEQ(scip, estimate1, estimate2) )
299  {
300  SCIP_Real lowerbound1;
301  SCIP_Real lowerbound2;
302 
303  lowerbound1 = SCIPnodeGetLowerbound(node1);
304  lowerbound2 = SCIPnodeGetLowerbound(node2);
305  if( SCIPisLT(scip, lowerbound1, lowerbound2) )
306  return -1;
307  else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
308  return +1;
309  else
310  {
311  SCIP_NODETYPE nodetype1;
312  SCIP_NODETYPE nodetype2;
313 
314  nodetype1 = SCIPnodeGetType(node1);
315  nodetype2 = SCIPnodeGetType(node2);
316  if( nodetype1 == SCIP_NODETYPE_CHILD && nodetype2 != SCIP_NODETYPE_CHILD )
317  return -1;
318  else if( nodetype1 != SCIP_NODETYPE_CHILD && nodetype2 == SCIP_NODETYPE_CHILD )
319  return +1;
320  else if( nodetype1 == SCIP_NODETYPE_SIBLING && nodetype2 != SCIP_NODETYPE_SIBLING )
321  return -1;
322  else if( nodetype1 != SCIP_NODETYPE_SIBLING && nodetype2 == SCIP_NODETYPE_SIBLING )
323  return +1;
324  else
325  {
326  int depth1;
327  int depth2;
328 
329  depth1 = SCIPnodeGetDepth(node1);
330  depth2 = SCIPnodeGetDepth(node2);
331  if( depth1 < depth2 )
332  return -1;
333  else if( depth1 > depth2 )
334  return +1;
335  else
336  return 0;
337  }
338  }
339  }
340 
341  if( SCIPisLT(scip, estimate1, estimate2) )
342  return -1;
343 
344  assert(SCIPisGT(scip, estimate1, estimate2));
345  return +1;
346 }
347 
348 
349 /*
350  * estimate specific interface methods
351  */
352 
353 /** creates the node selector for best estimate search and includes it in SCIP */
355  SCIP* scip /**< SCIP data structure */
356  )
357 {
358  SCIP_NODESELDATA* nodeseldata;
359  SCIP_NODESEL* nodesel;
360 
361  /* allocate and initialize node selector data; this has to be freed in the destructor */
362  SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );
363 
364  /* include node selector */
366  nodeselSelectEstimate, nodeselCompEstimate, nodeseldata) );
367 
368  assert(nodesel != NULL);
369 
370  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyEstimate) );
371  SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeEstimate) );
372 
373  /* add node selector parameters */
375  "nodeselection/estimate/minplungedepth",
376  "minimal plunging depth, before new best node may be selected (-1 for dynamic setting)",
377  &nodeseldata->minplungedepth, TRUE, DEFAULT_MINPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
379  "nodeselection/estimate/maxplungedepth",
380  "maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting)",
381  &nodeseldata->maxplungedepth, TRUE, DEFAULT_MAXPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
383  "nodeselection/estimate/maxplungequot",
384  "maximal quotient (estimate - lowerbound)/(cutoffbound - lowerbound) where plunging is performed",
385  &nodeseldata->maxplungequot, TRUE, DEFAULT_MAXPLUNGEQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
387  "nodeselection/estimate/bestnodefreq",
388  "frequency at which the best node instead of the best estimate is selected (0: never)",
389  &nodeseldata->bestnodefreq, FALSE, DEFAULT_BESTNODEFREQ, 0, INT_MAX, NULL, NULL) );
391  "nodeselection/estimate/breadthfirstdepth",
392  "depth until breadth-first search is applied",
393  &nodeseldata->breadthfirstdepth, FALSE, DEFAULT_BREADTHFIRSTDEPTH, -1, INT_MAX, NULL, NULL) );
395  "nodeselection/estimate/plungeoffset",
396  "number of nodes before doing plunging the first time",
397  &nodeseldata->plungeoffset, FALSE, DEFAULT_PLUNGEOFFSET, 0, INT_MAX, NULL, NULL) );
398 
399  return SCIP_OKAY;
400 }
401 
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:309
#define NULL
Definition: def.h:253
public methods for SCIP parameter handling
#define NODESEL_NAME
public methods for branch and bound tree
public methods for node selector plugins
public methods for memory management
#define DEFAULT_BESTNODEFREQ
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:128
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:293
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: scip_nodesel.c:144
#define FALSE
Definition: def.h:73
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7357
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_Longint SCIPgetNStrongbranchLPIterations(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:325
SCIP_EXPORT SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7367
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
static SCIP_DECL_NODESELFREE(nodeselFreeEstimate)
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:38
SCIP_Longint SCIPgetNNodes(SCIP *scip)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:357
static SCIP_DECL_NODESELCOPY(nodeselCopyEstimate)
#define NODESEL_STDPRIORITY
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1106
#define DEFAULT_MAXPLUNGEQUOT
#define NODESEL_DESC
#define SCIP_CALL(x)
Definition: def.h:365
node selector for best estimate search
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:277
public methods for node selectors
int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip_tree.c:680
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:637
#define MIN(x, y)
Definition: def.h:223
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1116
static SCIP_DECL_NODESELCOMP(nodeselCompEstimate)
#define DEFAULT_MINPLUNGEDEPTH
SCIP_RETCODE SCIPincludeNodeselEstimate(SCIP *scip)
SCIP_EXPORT SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7377
SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition: scip_tree.c:373
#define DEFAULT_MAXPLUNGEDEPTH
#define NODESEL_MEMSAVEPRIORITY
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:93
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:129
#define SCIP_REAL_MAX
Definition: def.h:165
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:44
#define SCIP_LONGINT_FORMAT
Definition: def.h:156
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1038
#define MAX(x, y)
Definition: def.h:222
#define DEFAULT_BREADTHFIRSTDEPTH
#define DEFAULT_PLUNGEOFFSET
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:73
#define SCIP_Real
Definition: def.h:164
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)
static SCIP_DECL_NODESELSELECT(nodeselSelectEstimate)
SCIP_EXPORT SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7337