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