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-2014 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 */
77  SCIP_CALL( SCIPincludeNodeselEstimate(scip) );
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  /* cehck 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=%lld < %d=plungeoffset -> don't start plunging\n", SCIPgetNNodes(scip), nodeseldata->plungeoffset);
155  if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
156  *selnode = SCIPgetBestboundNode(scip);
157  else
158  *selnode = SCIPgetBestNode(scip);
159  SCIPdebugMessage(" -> best node : lower=%g\n",
160  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
161  return SCIP_OKAY;
162  }
163 
164  /* calculate minimal and maximal plunging depth */
165  minplungedepth = nodeseldata->minplungedepth;
166  maxplungedepth = nodeseldata->maxplungedepth;
167  maxplungequot = nodeseldata->maxplungequot;
168  if( minplungedepth == -1 )
169  {
170  minplungedepth = SCIPgetMaxDepth(scip)/10;
171  if( SCIPgetNStrongbranchLPIterations(scip) > 2*SCIPgetNNodeLPIterations(scip) )
172  minplungedepth += 10;
173  if( maxplungedepth >= 0 )
174  minplungedepth = MIN(minplungedepth, maxplungedepth);
175  }
176  if( maxplungedepth == -1 )
177  maxplungedepth = SCIPgetMaxDepth(scip)/2;
178  maxplungedepth = MAX(maxplungedepth, minplungedepth);
179 
180  /* check, if we exceeded the maximal plunging depth */
181  plungedepth = SCIPgetPlungeDepth(scip);
182  if( plungedepth > maxplungedepth )
183  {
184  /* we don't want to plunge again: select best node from the tree */
185  SCIPdebugMessage("plungedepth: [%d,%d], cur: %d -> abort plunging\n", minplungedepth, maxplungedepth, plungedepth);
186  if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
187  *selnode = SCIPgetBestboundNode(scip);
188  else
189  *selnode = SCIPgetBestNode(scip);
190  SCIPdebugMessage(" -> best node : lower=%g\n",
191  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
192  }
193  else
194  {
195  SCIP_NODE* node;
196  SCIP_Real lowerbound;
197  SCIP_Real cutoffbound;
198  SCIP_Real maxbound;
199 
200  /* get global lower and cutoff bound */
201  lowerbound = SCIPgetLowerbound(scip);
202  cutoffbound = SCIPgetCutoffbound(scip);
203 
204  /* if we didn't find a solution yet, the cutoff bound is usually very bad:
205  * use only 20% of the gap as cutoff bound
206  */
207  if( SCIPgetNSolsFound(scip) == 0 )
208  cutoffbound = lowerbound + 0.2 * (cutoffbound - lowerbound);
209 
210  /* check, if plunging is forced at the current depth */
211  if( plungedepth < minplungedepth )
212  maxbound = SCIPinfinity(scip);
213  else
214  {
215  /* calculate maximal plunging bound */
216  maxbound = lowerbound + maxplungequot * (cutoffbound - lowerbound);
217  }
218 
219  SCIPdebugMessage("plungedepth: [%d,%d], cur: %d, bounds: [%g,%g], maxbound: %g\n",
220  minplungedepth, maxplungedepth, plungedepth, lowerbound, cutoffbound, maxbound);
221 
222  /* we want to plunge again: prefer children over siblings, and siblings over leaves,
223  * but only select a child or sibling, if its estimate is small enough;
224  * prefer using nodes with higher node selection priority assigned by the branching rule
225  */
226  node = SCIPgetPrioChild(scip);
227  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
228  {
229  *selnode = node;
230  SCIPdebugMessage(" -> selected prio child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
231  }
232  else
233  {
234  node = SCIPgetBestChild(scip);
235  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
236  {
237  *selnode = node;
238  SCIPdebugMessage(" -> selected best child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
239  }
240  else
241  {
242  node = SCIPgetPrioSibling(scip);
243  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
244  {
245  *selnode = node;
246  SCIPdebugMessage(" -> selected prio sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
247  }
248  else
249  {
250  node = SCIPgetBestSibling(scip);
251  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
252  {
253  *selnode = node;
254  SCIPdebugMessage(" -> selected best sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
255  }
256  else
257  {
258  if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
259  *selnode = SCIPgetBestboundNode(scip);
260  else
261  *selnode = SCIPgetBestNode(scip);
262  SCIPdebugMessage(" -> selected best leaf: estimate=%g\n",
263  *selnode != NULL ? SCIPnodeGetEstimate(*selnode) : SCIPinfinity(scip));
264  }
265  }
266  }
267  }
268  }
269 
270  return SCIP_OKAY;
271 }
272 
273 
274 /** node comparison method of node selector */
275 static
276 SCIP_DECL_NODESELCOMP(nodeselCompEstimate)
277 { /*lint --e{715}*/
278  SCIP_Real estimate1;
279  SCIP_Real estimate2;
280 
281  assert(nodesel != NULL);
282  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
283  assert(scip != NULL);
284 
285  estimate1 = SCIPnodeGetEstimate(node1);
286  estimate2 = SCIPnodeGetEstimate(node2);
287  if( (SCIPisInfinity(scip, estimate1) && SCIPisInfinity(scip, estimate2)) ||
288  (SCIPisInfinity(scip, -estimate1) && SCIPisInfinity(scip, -estimate2)) ||
289  SCIPisEQ(scip, estimate1, estimate2) )
290  {
291  SCIP_Real lowerbound1;
292  SCIP_Real lowerbound2;
293 
294  lowerbound1 = SCIPnodeGetLowerbound(node1);
295  lowerbound2 = SCIPnodeGetLowerbound(node2);
296  if( SCIPisLT(scip, lowerbound1, lowerbound2) )
297  return -1;
298  else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
299  return +1;
300  else
301  {
302  SCIP_NODETYPE nodetype1;
303  SCIP_NODETYPE nodetype2;
304 
305  nodetype1 = SCIPnodeGetType(node1);
306  nodetype2 = SCIPnodeGetType(node2);
307  if( nodetype1 == SCIP_NODETYPE_CHILD && nodetype2 != SCIP_NODETYPE_CHILD )
308  return -1;
309  else if( nodetype1 != SCIP_NODETYPE_CHILD && nodetype2 == SCIP_NODETYPE_CHILD )
310  return +1;
311  else if( nodetype1 == SCIP_NODETYPE_SIBLING && nodetype2 != SCIP_NODETYPE_SIBLING )
312  return -1;
313  else if( nodetype1 != SCIP_NODETYPE_SIBLING && nodetype2 == SCIP_NODETYPE_SIBLING )
314  return +1;
315  else
316  {
317  int depth1;
318  int depth2;
319 
320  depth1 = SCIPnodeGetDepth(node1);
321  depth2 = SCIPnodeGetDepth(node2);
322  if( depth1 < depth2 )
323  return -1;
324  else if( depth1 > depth2 )
325  return +1;
326  else
327  return 0;
328  }
329  }
330  }
331 
332  if( SCIPisLT(scip, estimate1, estimate2) )
333  return -1;
334 
335  assert(SCIPisGT(scip, estimate1, estimate2));
336  return +1;
337 }
338 
339 
340 /*
341  * estimate specific interface methods
342  */
343 
344 /** creates the node selector for best estimate search and includes it in SCIP */
345 SCIP_RETCODE SCIPincludeNodeselEstimate(
346  SCIP* scip /**< SCIP data structure */
347  )
348 {
349  SCIP_NODESELDATA* nodeseldata;
350  SCIP_NODESEL* nodesel;
351 
352  /* allocate and initialize node selector data; this has to be freed in the destructor */
353  SCIP_CALL( SCIPallocMemory(scip, &nodeseldata) );
354 
355  /* include node selector */
356  SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY,
357  nodeselSelectEstimate, nodeselCompEstimate, nodeseldata) );
358 
359  assert(nodesel != NULL);
360 
361  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyEstimate) );
362  SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeEstimate) );
363 
364  /* add node selector parameters */
365  SCIP_CALL( SCIPaddIntParam(scip,
366  "nodeselection/estimate/minplungedepth",
367  "minimal plunging depth, before new best node may be selected (-1 for dynamic setting)",
368  &nodeseldata->minplungedepth, TRUE, DEFAULT_MINPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
369  SCIP_CALL( SCIPaddIntParam(scip,
370  "nodeselection/estimate/maxplungedepth",
371  "maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting)",
372  &nodeseldata->maxplungedepth, TRUE, DEFAULT_MAXPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
373  SCIP_CALL( SCIPaddRealParam(scip,
374  "nodeselection/estimate/maxplungequot",
375  "maximal quotient (estimate - lowerbound)/(cutoffbound - lowerbound) where plunging is performed",
376  &nodeseldata->maxplungequot, TRUE, DEFAULT_MAXPLUNGEQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
377  SCIP_CALL( SCIPaddIntParam(scip,
378  "nodeselection/estimate/bestnodefreq",
379  "frequency at which the best node instead of the best estimate is selected (0: never)",
380  &nodeseldata->bestnodefreq, FALSE, DEFAULT_BESTNODEFREQ, 0, INT_MAX, NULL, NULL) );
381  SCIP_CALL( SCIPaddIntParam(scip,
382  "nodeselection/estimate/breadthfirstdepth",
383  "depth until breadth-first search is applied",
384  &nodeseldata->breadthfirstdepth, FALSE, DEFAULT_BREADTHFIRSTDEPTH, -1, INT_MAX, NULL, NULL) );
385  SCIP_CALL( SCIPaddIntParam(scip,
386  "nodeselection/estimate/plungeoffset",
387  "number of nodes before doing plunging the first time",
388  &nodeseldata->plungeoffset, FALSE, DEFAULT_PLUNGEOFFSET, 0, INT_MAX, NULL, NULL) );
389 
390  return SCIP_OKAY;
391 }
392 
393