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-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_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"
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 */
66struct 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 */
86static
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) */
101static
102SCIP_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) */
115static
116SCIP_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 */
135static
136SCIP_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 */
268static
269SCIP_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
#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_CALL(x)
Definition: def.h:374
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludeNodeselHybridestim(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
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
#define BESTNODEFREQ
static SCIP_Real getNodeselScore(SCIP_NODE *node, SCIP_Real estimweight)
static SCIP_DECL_NODESELFREE(nodeselFreeHybridestim)
static SCIP_DECL_NODESELSELECT(nodeselSelectHybridestim)
#define NODESEL_NAME
#define MAXPLUNGEQUOT
#define NODESEL_MEMSAVEPRIORITY
static SCIP_DECL_NODESELCOPY(nodeselCopyHybridestim)
#define NODESEL_STDPRIORITY
#define ESTIMWEIGHT
#define NODESEL_DESC
#define MINPLUNGEDEPTH
static SCIP_DECL_NODESELCOMP(nodeselCompHybridestim)
#define MAXPLUNGEDEPTH
node selector for hybrid best estimate / best bound 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