Scippy

SCIP

Solving Constraint Integer Programs

nodesel_bfs.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 2002-2022 Zuse Institute Berlin */
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_bfs.c
26  * @ingroup DEFPLUGINS_NODESEL
27  * @brief node selector for best first 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_bfs.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 "scip/type_misc.h"
45 #include <string.h>
46 
47 #define NODESEL_NAME "bfs"
48 #define NODESEL_DESC "best first search"
49 #define NODESEL_STDPRIORITY 100000
50 #define NODESEL_MEMSAVEPRIORITY 0
51 
52 
53 /*
54  * Default parameter settings
55  */
56 
57 #define MINPLUNGEDEPTH -1 /**< minimal plunging depth, before new best node may be selected (-1 for dynamic setting) */
58 #define MAXPLUNGEDEPTH -1 /**< maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting) */
59 #define MAXPLUNGEQUOT 0.25 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
60  * where plunging is performed */
61 
62 
63 /** node selector data for best first search node selection */
64 struct SCIP_NodeselData
65 {
66  SCIP_Real maxplungequot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
67  * where plunging is performed */
68  int minplungedepth; /**< minimal plunging depth, before new best node may be selected
69  * (-1 for dynamic setting) */
70  int maxplungedepth; /**< maximal plunging depth, before new best node is forced to be selected
71  * (-1 for dynamic setting) */
72 };
73 
74 
75 /*
76  * Callback methods
77  */
78 
79 /** copy method for node selector plugins (called when SCIP copies plugins) */
80 static
81 SCIP_DECL_NODESELCOPY(nodeselCopyBfs)
82 { /*lint --e{715}*/
83  assert(scip != NULL);
84  assert(nodesel != NULL);
85  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
86 
87  /* call inclusion method of node selector */
89 
90  return SCIP_OKAY;
91 }
92 
93 /** destructor of node selector to free user data (called when SCIP is exiting) */
94 /**! [SnippetNodeselFreeBfs] */
95 static
96 SCIP_DECL_NODESELFREE(nodeselFreeBfs)
97 { /*lint --e{715}*/
98  SCIP_NODESELDATA* nodeseldata;
99 
100  assert(nodesel != NULL);
101  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
102  assert(scip != NULL);
103 
104  /* free user data of node selector */
105  nodeseldata = SCIPnodeselGetData(nodesel);
106  assert(nodeseldata != NULL);
107  SCIPfreeBlockMemory(scip, &nodeseldata);
108  SCIPnodeselSetData(nodesel, nodeseldata);
109 
110  return SCIP_OKAY;
111 }
112 /**! [SnippetNodeselFreeBfs] */
113 
114 
115 /** node selection method of node selector */
116 static
117 SCIP_DECL_NODESELSELECT(nodeselSelectBfs)
118 { /*lint --e{715}*/
119  SCIP_NODESELDATA* nodeseldata;
120  int minplungedepth;
121  int maxplungedepth;
122  int plungedepth;
123  SCIP_Real maxplungequot;
124 
125  assert(nodesel != NULL);
126  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
127  assert(scip != NULL);
128  assert(selnode != NULL);
129 
130  *selnode = NULL;
131 
132  /* get node selector user data */
133  nodeseldata = SCIPnodeselGetData(nodesel);
134  assert(nodeseldata != NULL);
135 
136  /* calculate minimal and maximal plunging depth */
137  minplungedepth = nodeseldata->minplungedepth;
138  maxplungedepth = nodeseldata->maxplungedepth;
139  maxplungequot = nodeseldata->maxplungequot;
140  if( minplungedepth == -1 )
141  {
142  minplungedepth = SCIPgetMaxDepth(scip)/10;
144  minplungedepth += 10;
145  if( maxplungedepth >= 0 )
146  minplungedepth = MIN(minplungedepth, maxplungedepth);
147  }
148  if( maxplungedepth == -1 )
149  maxplungedepth = SCIPgetMaxDepth(scip)/2;
150  maxplungedepth = MAX(maxplungedepth, minplungedepth);
151 
152  /* check, if we exceeded the maximal plunging depth */
153  plungedepth = SCIPgetPlungeDepth(scip);
154  if( plungedepth >= maxplungedepth )
155  {
156  /* we don't want to plunge again: select best node from the tree */
157  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d -> abort plunging\n", minplungedepth, maxplungedepth, plungedepth);
158  *selnode = SCIPgetBestNode(scip);
159  SCIPdebugMsg(scip, " -> best node : lower=%g\n",
160  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
161  }
162  else
163  {
164  SCIP_NODE* node;
165  SCIP_Real maxbound;
166 
167  /* check, if plunging is forced at the current depth */
168  if( plungedepth < minplungedepth )
169  {
170  maxbound = SCIPinfinity(scip);
171  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d => maxbound: infinity\n",
172  minplungedepth, maxplungedepth, plungedepth);
173  }
174  else
175  {
176  SCIP_Real lowerbound;
177  SCIP_Real cutoffbound;
178  /* get global lower and cutoff bound */
179  lowerbound = SCIPgetLowerbound(scip);
180  cutoffbound = SCIPgetCutoffbound(scip);
181 
182  /* if we didn't find a solution yet, the cutoff bound is usually very bad:
183  * use only 20% of the gap as cutoff bound
184  */
185  if( SCIPgetNSolsFound(scip) == 0 )
186  cutoffbound = lowerbound + 0.2 * (cutoffbound - lowerbound);
187  /* calculate maximal plunging bound */
188  maxbound = lowerbound + maxplungequot * (cutoffbound - lowerbound);
189 
190  SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d, bounds: [%g,%g], maxbound: %g\n",
191  minplungedepth, maxplungedepth, plungedepth, lowerbound, cutoffbound, maxbound);
192  }
193 
194  /* we want to plunge again: prefer children over siblings, and siblings over leaves,
195  * but only select a child or sibling, if its dual bound is small enough;
196  * prefer using nodes with higher node selection priority assigned by the branching rule
197  */
198  node = SCIPgetPrioChild(scip);
199  if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
200  {
201  *selnode = node;
202  SCIPdebugMsg(scip, " -> selected prio child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
203  }
204  else
205  {
206  node = SCIPgetBestChild(scip);
207  if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
208  {
209  *selnode = node;
210  SCIPdebugMsg(scip, " -> selected best child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
211  }
212  else
213  {
214  node = SCIPgetPrioSibling(scip);
215  if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
216  {
217  *selnode = node;
218  SCIPdebugMsg(scip, " -> selected prio sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
219  }
220  else
221  {
222  node = SCIPgetBestSibling(scip);
223  if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
224  {
225  *selnode = node;
226  SCIPdebugMsg(scip, " -> selected best sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
227  }
228  else
229  {
230  *selnode = SCIPgetBestNode(scip);
231  SCIPdebugMsg(scip, " -> selected best leaf: lower=%g\n",
232  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
233  }
234  }
235  }
236  }
237  }
238 
239  return SCIP_OKAY;
240 }
241 
242 
243 /** node comparison method of node selector */
244 static
245 SCIP_DECL_NODESELCOMP(nodeselCompBfs)
246 { /*lint --e{715}*/
247  SCIP_Real lowerbound1;
248  SCIP_Real lowerbound2;
249 
250  assert(nodesel != NULL);
251  assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
252  assert(scip != NULL);
253 
254  lowerbound1 = SCIPnodeGetLowerbound(node1);
255  lowerbound2 = SCIPnodeGetLowerbound(node2);
256  if( SCIPisLT(scip, lowerbound1, lowerbound2) )
257  return -1;
258  else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
259  return +1;
260  else
261  {
262  SCIP_Real estimate1;
263  SCIP_Real estimate2;
264 
265  estimate1 = SCIPnodeGetEstimate(node1);
266  estimate2 = SCIPnodeGetEstimate(node2);
267  if( (SCIPisInfinity(scip, estimate1) && SCIPisInfinity(scip, estimate2)) ||
268  (SCIPisInfinity(scip, -estimate1) && SCIPisInfinity(scip, -estimate2)) ||
269  SCIPisEQ(scip, estimate1, estimate2) )
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, estimate1, estimate2) )
301  return -1;
302 
303  assert(SCIPisGT(scip, estimate1, estimate2));
304  return +1;
305  }
306 }
307 
308 
309 /*
310  * bfs specific interface methods
311  */
312 
313 /** creates the node selector for best first search and includes it in SCIP */
315  SCIP* scip /**< SCIP data structure */
316  )
317 {
318  SCIP_NODESELDATA* nodeseldata;
319  SCIP_NODESEL* nodesel;
320 
321  /* allocate and initialize node selector data; this has to be freed in the destructor */
322  SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );
323 
324  /* include node selector */
326  nodeselSelectBfs, nodeselCompBfs, nodeseldata) );
327 
328  assert(nodesel != NULL);
329 
330  SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyBfs) );
331  SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeBfs) );
332 
333  /* add node selector parameters */
335  "nodeselection/bfs/minplungedepth",
336  "minimal plunging depth, before new best node may be selected (-1 for dynamic setting)",
337  &nodeseldata->minplungedepth, TRUE, MINPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
339  "nodeselection/bfs/maxplungedepth",
340  "maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting)",
341  &nodeseldata->maxplungedepth, TRUE, MAXPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
343  "nodeselection/bfs/maxplungequot",
344  "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where plunging is performed",
345  &nodeseldata->maxplungequot, TRUE, MAXPLUNGEQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
346 
347  return SCIP_OKAY;
348 }
349 
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
public methods for branch and bound tree
type definitions for miscellaneous datastructures
#define NODESEL_STDPRIORITY
Definition: nodesel_bfs.c:49
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:7463
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)
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
#define MINPLUNGEDEPTH
Definition: nodesel_bfs.c:57
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7453
#define MAXPLUNGEQUOT
Definition: nodesel_bfs.c:59
#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
public methods for numerical tolerances
public methods for querying solving statistics
SCIP_RETCODE SCIPincludeNodeselBfs(SCIP *scip)
Definition: nodesel_bfs.c:315
public methods for the branch-and-bound tree
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:52
static SCIP_DECL_NODESELFREE(nodeselFreeBfs)
Definition: nodesel_bfs.c:97
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define NODESEL_DESC
Definition: nodesel_bfs.c:48
#define NULL
Definition: lpi_spx1.cpp:164
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1120
#define MAXPLUNGEDEPTH
Definition: nodesel_bfs.c:58
#define SCIP_CALL(x)
Definition: def.h:393
SCIP_Real SCIPgetLowerbound(SCIP *scip)
#define NODESEL_NAME
Definition: nodesel_bfs.c:47
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
public methods for node selectors
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:368
static SCIP_DECL_NODESELCOPY(nodeselCopyBfs)
Definition: nodesel_bfs.c:82
#define MAX(x, y)
Definition: tclique_def.h:92
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1052
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:7473
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:53
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_bfs.c:50
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Longint SCIPgetNStrongbranchLPIterations(SCIP *scip)
node selector for best first search
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:7433
#define SCIP_Real
Definition: def.h:186
static SCIP_DECL_NODESELCOMP(nodeselCompBfs)
Definition: nodesel_bfs.c:246
static SCIP_DECL_NODESELSELECT(nodeselSelectBfs)
Definition: nodesel_bfs.c:118
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
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