Scippy

SCIP

Solving Constraint Integer Programs

nodesel_hybridestim.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-2020 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_hybridestim.c
17  * @ingroup DEFPLUGINS_NODESEL
18  * @brief node selector for hybrid best estimate / best bound search
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
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 "hybridestim"
38 #define NODESEL_DESC "hybrid best estimate / best bound search"
39 #define NODESEL_STDPRIORITY 50000
40 #define NODESEL_MEMSAVEPRIORITY 50
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 #define BESTNODEFREQ 1000 /**< frequency at which the best node instead of the hybrid best estimate / best bound is selected (0: never) */
52 #define ESTIMWEIGHT 0.10 /**< weight of estimate value in node selection score (0: pure best bound search,
53  * 1: pure best estimate search) */
54 
55 
56 /** node selector data for hybrid best estimate / best bound search node selection */
57 struct SCIP_NodeselData
58 {
59  SCIP_Real maxplungequot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
60  * where plunging is performed */
61  SCIP_Real estimweight; /**< weight of estimate value in node selection score (0: pure best bound search,
62  * 1: pure best estimate search) */
63  int minplungedepth; /**< minimal plunging depth, before new best node may be selected
64  * (-1 for dynamic setting) */
65  int maxplungedepth; /**< maximal plunging depth, before new best node is forced to be selected
66  * (-1 for dynamic setting) */
67  int bestnodefreq; /**< frequency at which the best node instead of the hybrid best estimate / best bound is selected
68  * (0: never) */
69 };
70 
71 
72 /*
73  * Local methods
74  */
75 
76 /** returns a weighted sum of the node's lower bound and estimate value */
77 static
79  SCIP_NODE* node, /**< branching node */
80  SCIP_Real estimweight /**< weight of estimate in score */
81  )
82 {
83  return (1.0-estimweight) * SCIPnodeGetLowerbound(node) + estimweight * SCIPnodeGetEstimate(node);
84 }
85 
86 
87 /*
88  * Callback methods
89  */
90 
91 /** copy method for node selector plugins (called when SCIP copies plugins) */
92 static
93 SCIP_DECL_NODESELCOPY(nodeselCopyHybridestim)
94 { /*lint --e{715}*/
95  assert(scip != NULL);
96  assert(nodesel != NULL);
97  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
98 
99  /* call inclusion method of node selector */
101 
102  return SCIP_OKAY;
103 }
104 
105 /** destructor of node selector to free user data (called when SCIP is exiting) */
106 static
107 SCIP_DECL_NODESELFREE(nodeselFreeHybridestim)
108 { /*lint --e{715}*/
109  SCIP_NODESELDATA* nodeseldata;
110 
111  assert(nodesel != NULL);
112  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
113  assert(scip != NULL);
114 
115  /* free user data of node selector */
116  nodeseldata = SCIPnodeselGetData(nodesel);
117  assert(nodeseldata != NULL);
118  SCIPfreeBlockMemory(scip, &nodeseldata);
119  SCIPnodeselSetData(nodesel, nodeseldata);
120 
121  return SCIP_OKAY;
122 }
123 
124 
125 /** node selection method of node selector */
126 static
127 SCIP_DECL_NODESELSELECT(nodeselSelectHybridestim)
128 { /*lint --e{715}*/
129  SCIP_NODESELDATA* nodeseldata;
130  int minplungedepth;
131  int maxplungedepth;
132  int plungedepth;
133  int bestnodefreq;
134  SCIP_Real maxplungequot;
135 
136  assert(nodesel != NULL);
137  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
138  assert(scip != NULL);
139  assert(selnode != NULL);
140 
141  *selnode = NULL;
142 
143  /* get node selector user data */
144  nodeseldata = SCIPnodeselGetData(nodesel);
145  assert(nodeseldata != NULL);
146 
147  /* calculate minimal and maximal plunging depth */
148  minplungedepth = nodeseldata->minplungedepth;
149  maxplungedepth = nodeseldata->maxplungedepth;
150  maxplungequot = nodeseldata->maxplungequot;
151  if( minplungedepth == -1 )
152  {
153  minplungedepth = SCIPgetMaxDepth(scip)/10;
155  minplungedepth += 10;
156  if( maxplungedepth >= 0 )
157  minplungedepth = MIN(minplungedepth, maxplungedepth);
158  }
159  if( maxplungedepth == -1 )
160  maxplungedepth = SCIPgetMaxDepth(scip)/2;
161  maxplungedepth = MAX(maxplungedepth, minplungedepth);
162  bestnodefreq = (nodeseldata->bestnodefreq == 0 ? INT_MAX : nodeseldata->bestnodefreq);
163 
164  /* check, if we exceeded the maximal plunging depth */
165  plungedepth = SCIPgetPlungeDepth(scip);
166  if( plungedepth > maxplungedepth )
167  {
168  /* we don't want to plunge again: select best node from the tree */
169  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d -> abort plunging\n", minplungedepth, maxplungedepth, plungedepth);
170  if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
171  *selnode = SCIPgetBestboundNode(scip);
172  else
173  *selnode = SCIPgetBestNode(scip);
174  SCIPdebugMsg(scip, " -> best node : lower=%g\n",
175  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
176  }
177  else
178  {
179  SCIP_NODE* node;
180  SCIP_Real lowerbound;
181  SCIP_Real cutoffbound;
182  SCIP_Real maxbound;
183 
184  /* get global lower and cutoff bound */
185  lowerbound = SCIPgetLowerbound(scip);
186  cutoffbound = SCIPgetCutoffbound(scip);
187 
188  /* if we didn't find a solution yet, the cutoff bound is usually very bad:
189  * use only 20% of the gap as cutoff bound
190  */
191  if( SCIPgetNSolsFound(scip) == 0 )
192  cutoffbound = lowerbound + 0.2 * (cutoffbound - lowerbound);
193 
194  /* check, if plunging is forced at the current depth */
195  if( plungedepth < minplungedepth )
196  maxbound = SCIPinfinity(scip);
197  else
198  {
199  /* calculate maximal plunging bound */
200  maxbound = lowerbound + maxplungequot * (cutoffbound - lowerbound);
201  }
202 
203  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d, bounds: [%g,%g], maxbound: %g\n",
204  minplungedepth, maxplungedepth, plungedepth, lowerbound, cutoffbound, maxbound);
205 
206  /* we want to plunge again: prefer children over siblings, and siblings over leaves,
207  * but only select a child or sibling, if its estimate is small enough;
208  * prefer using nodes with higher node selection priority assigned by the branching rule
209  */
210  node = SCIPgetPrioChild(scip);
211  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
212  {
213  *selnode = node;
214  SCIPdebugMsg(scip, " -> selected prio child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
215  }
216  else
217  {
218  node = SCIPgetBestChild(scip);
219  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
220  {
221  *selnode = node;
222  SCIPdebugMsg(scip, " -> selected best child: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
223  }
224  else
225  {
226  node = SCIPgetPrioSibling(scip);
227  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
228  {
229  *selnode = node;
230  SCIPdebugMsg(scip, " -> selected prio sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
231  }
232  else
233  {
234  node = SCIPgetBestSibling(scip);
235  if( node != NULL && SCIPnodeGetEstimate(node) < maxbound )
236  {
237  *selnode = node;
238  SCIPdebugMsg(scip, " -> selected best sibling: estimate=%g\n", SCIPnodeGetEstimate(*selnode));
239  }
240  else
241  {
242  if( SCIPgetNNodes(scip) % bestnodefreq == 0 )
243  *selnode = SCIPgetBestboundNode(scip);
244  else
245  *selnode = SCIPgetBestNode(scip);
246  SCIPdebugMsg(scip, " -> selected best leaf: estimate=%g\n",
247  *selnode != NULL ? SCIPnodeGetEstimate(*selnode) : SCIPinfinity(scip));
248  }
249  }
250  }
251  }
252  }
253 
254  return SCIP_OKAY;
255 }
256 
257 
258 /** node comparison method of node selector */
259 static
260 SCIP_DECL_NODESELCOMP(nodeselCompHybridestim)
261 { /*lint --e{715}*/
262  SCIP_NODESELDATA* nodeseldata;
263  SCIP_Real score1;
264  SCIP_Real score2;
265 
266  assert(nodesel != NULL);
267  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
268  assert(scip != NULL);
269 
270  nodeseldata = SCIPnodeselGetData(nodesel);
271  assert(nodeseldata != NULL);
272 
273  score1 = getNodeselScore(node1, nodeseldata->estimweight);
274  score2 = getNodeselScore(node2, nodeseldata->estimweight);
275  if( (SCIPisInfinity(scip, score1) && SCIPisInfinity(scip, score2)) ||
276  (SCIPisInfinity(scip, -score1) && SCIPisInfinity(scip, -score2)) ||
277  SCIPisEQ(scip, score1, score2) )
278  {
279  SCIP_NODETYPE nodetype1;
280  SCIP_NODETYPE nodetype2;
281 
282  nodetype1 = SCIPnodeGetType(node1);
283  nodetype2 = SCIPnodeGetType(node2);
284  if( nodetype1 == SCIP_NODETYPE_CHILD && nodetype2 != SCIP_NODETYPE_CHILD )
285  return -1;
286  else if( nodetype1 != SCIP_NODETYPE_CHILD && nodetype2 == SCIP_NODETYPE_CHILD )
287  return +1;
288  else if( nodetype1 == SCIP_NODETYPE_SIBLING && nodetype2 != SCIP_NODETYPE_SIBLING )
289  return -1;
290  else if( nodetype1 != SCIP_NODETYPE_SIBLING && nodetype2 == SCIP_NODETYPE_SIBLING )
291  return +1;
292  else
293  {
294  int depth1;
295  int depth2;
296 
297  depth1 = SCIPnodeGetDepth(node1);
298  depth2 = SCIPnodeGetDepth(node2);
299  if( depth1 < depth2 )
300  return -1;
301  else if( depth1 > depth2 )
302  return +1;
303  else
304  return 0;
305  }
306  }
307 
308  if( SCIPisLT(scip, score1, score2) )
309  return -1;
310 
311  assert(SCIPisGT(scip, score1, score2));
312  return +1;
313 }
314 
315 
316 /*
317  * hybridestim specific interface methods
318  */
319 
320 /** creates the node selector for hybrid best estimate / best bound search and includes it in SCIP */
322  SCIP* scip /**< SCIP data structure */
323  )
324 {
325  SCIP_NODESELDATA* nodeseldata;
326  SCIP_NODESEL* nodesel;
327 
328  /* allocate and initialize node selector data; this has to be freed in the destructor */
329  SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );
330 
331  /* include node selector */
333  nodeselSelectHybridestim, nodeselCompHybridestim, nodeseldata) );
334 
335  assert(nodesel != NULL);
336 
337  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyHybridestim) );
338  SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeHybridestim) );
339 
340  /* add node selector parameters */
342  "nodeselection/hybridestim/minplungedepth",
343  "minimal plunging depth, before new best node may be selected (-1 for dynamic setting)",
344  &nodeseldata->minplungedepth, TRUE, MINPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
346  "nodeselection/hybridestim/maxplungedepth",
347  "maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting)",
348  &nodeseldata->maxplungedepth, TRUE, MAXPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
350  "nodeselection/hybridestim/maxplungequot",
351  "maximal quotient (estimate - lowerbound)/(cutoffbound - lowerbound) where plunging is performed",
352  &nodeseldata->maxplungequot, TRUE, MAXPLUNGEQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
354  "nodeselection/hybridestim/bestnodefreq",
355  "frequency at which the best node instead of the hybrid best estimate / best bound is selected (0: never)",
356  &nodeseldata->bestnodefreq, FALSE, BESTNODEFREQ, 0, INT_MAX, NULL, NULL) );
358  "nodeselection/hybridestim/estimweight",
359  "weight of estimate value in node selection score (0: pure best bound search, 1: pure best estimate search)",
360  &nodeseldata->estimweight, TRUE, ESTIMWEIGHT, 0.0, 1.0, NULL, NULL) );
361 
362  return SCIP_OKAY;
363 }
364 
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:310
static SCIP_DECL_NODESELCOPY(nodeselCopyHybridestim)
public methods for SCIP parameter handling
public methods for branch and bound tree
node selector for hybrid best estimate / best bound search
public methods for node selector plugins
public methods for memory management
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:129
#define NODESEL_MEMSAVEPRIORITY
#define BESTNODEFREQ
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:294
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: scip_nodesel.c:145
static SCIP_Real getNodeselScore(SCIP_NODE *node, SCIP_Real estimweight)
#define FALSE
Definition: def.h:73
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7430
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_DECL_NODESELFREE(nodeselFreeHybridestim)
#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:326
SCIP_EXPORT SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7440
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
#define ESTIMWEIGHT
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:43
SCIP_Longint SCIPgetNNodes(SCIP *scip)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:358
#define MAXPLUNGEDEPTH
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1111
#define MAXPLUNGEQUOT
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
#define NODESEL_STDPRIORITY
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:278
static SCIP_DECL_NODESELCOMP(nodeselCompHybridestim)
public methods for node selectors
int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip_tree.c:681
#define NODESEL_DESC
SCIP_Real SCIPinfinity(SCIP *scip)
#define MAX(x, y)
Definition: tclique_def.h:83
#define NODESEL_NAME
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1121
SCIP_EXPORT SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7450
SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition: scip_tree.c:374
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
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
#define SCIP_REAL_MAX
Definition: def.h:164
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:44
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1043
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:74
#define MINPLUNGEDEPTH
#define SCIP_Real
Definition: def.h:163
static SCIP_DECL_NODESELSELECT(nodeselSelectHybridestim)
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)
SCIP_EXPORT SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7410
SCIP_RETCODE SCIPincludeNodeselHybridestim(SCIP *scip)