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