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-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_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
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 <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 */
66struct 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) */
86static
87SCIP_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) */
100static
101SCIP_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 */
120static
121SCIP_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 */
294static
295SCIP_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
#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 FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludeNodeselEstimate(SCIP *scip)
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 SCIPgetNNodes(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
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_NODE * SCIPgetBestNode(SCIP *scip)
Definition: scip_tree.c:368
int SCIPgetPlungeDepth(SCIP *scip)
Definition: scip_tree.c:713
SCIP_NODE * SCIPgetBestboundNode(SCIP *scip)
Definition: scip_tree.c:384
SCIP_NODE * SCIPgetPrioChild(SCIP *scip)
Definition: scip_tree.c:288
static SCIP_DECL_NODESELFREE(nodeselFreeEstimate)
#define DEFAULT_MAXPLUNGEDEPTH
#define NODESEL_NAME
static SCIP_DECL_NODESELCOMP(nodeselCompEstimate)
#define NODESEL_MEMSAVEPRIORITY
#define NODESEL_STDPRIORITY
#define NODESEL_DESC
#define DEFAULT_BESTNODEFREQ
static SCIP_DECL_NODESELCOPY(nodeselCopyEstimate)
static SCIP_DECL_NODESELSELECT(nodeselSelectEstimate)
#define DEFAULT_PLUNGEOFFSET
#define DEFAULT_BREADTHFIRSTDEPTH
#define DEFAULT_MINPLUNGEDEPTH
#define DEFAULT_MAXPLUNGEQUOT
node selector for best estimate 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
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