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