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