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