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