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 (c) 2002-2024 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_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"
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 */
64struct 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) */
80static
81SCIP_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] */
95static
96SCIP_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 */
116static
117SCIP_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 */
244static
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
#define NULL
Definition: def.h:267
#define SCIP_REAL_MAX
Definition: def.h:174
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL(x)
Definition: def.h:374
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludeNodeselBfs(SCIP *scip)
Definition: nodesel_bfs.c:314
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
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
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7483
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7513
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7523
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
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
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition: nodesel.c:1130
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELFREE((*nodeselfree)))
Definition: scip_nodesel.c:154
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1120
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel, SCIP_DECL_NODESELCOPY((*nodeselcopy)))
Definition: scip_nodesel.c:138
const char * SCIPnodeselGetName(SCIP_NODESEL *nodesel)
Definition: nodesel.c:1052
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_Longint SCIPgetNStrongbranchLPIterations(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetBestSibling(SCIP *scip)
Definition: scip_tree.c:336
SCIP_NODE * SCIPgetBestChild(SCIP *scip)
Definition: scip_tree.c:320
SCIP_NODE * SCIPgetPrioSibling(SCIP *scip)
Definition: scip_tree.c:304
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:368
int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip_tree.c:713
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:288
static SCIP_DECL_NODESELFREE(nodeselFreeBfs)
Definition: nodesel_bfs.c:96
#define NODESEL_NAME
Definition: nodesel_bfs.c:47
#define MAXPLUNGEQUOT
Definition: nodesel_bfs.c:59
static SCIP_DECL_NODESELSELECT(nodeselSelectBfs)
Definition: nodesel_bfs.c:117
static SCIP_DECL_NODESELCOMP(nodeselCompBfs)
Definition: nodesel_bfs.c:245
#define NODESEL_MEMSAVEPRIORITY
Definition: nodesel_bfs.c:50
#define NODESEL_STDPRIORITY
Definition: nodesel_bfs.c:49
#define NODESEL_DESC
Definition: nodesel_bfs.c:48
#define MINPLUNGEDEPTH
Definition: nodesel_bfs.c:57
static SCIP_DECL_NODESELCOPY(nodeselCopyBfs)
Definition: nodesel_bfs.c:81
#define MAXPLUNGEDEPTH
Definition: nodesel_bfs.c:58
node selector for best first search
public methods for message output
public methods for node selectors
public methods for branch and bound tree
public methods for memory management
public methods for message handling
public methods for node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for querying solving statistics
public methods for the branch-and-bound tree
type definitions for miscellaneous datastructures
struct SCIP_NodeselData SCIP_NODESELDATA
Definition: type_nodesel.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
enum SCIP_NodeType SCIP_NODETYPE
Definition: type_tree.h:53
@ SCIP_NODETYPE_CHILD
Definition: type_tree.h:44
@ SCIP_NODETYPE_SIBLING
Definition: type_tree.h:43