SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
103{ /*lint --e{715}*/
104 assert(scip != NULL);
105 assert(nodesel != NULL);
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
117{ /*lint --e{715}*/
118 SCIP_NODESELDATA* nodeseldata;
119
120 assert(nodesel != NULL);
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
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);
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 )
181 else
183 SCIPdebugMsg(scip, " -> best node : lower=%g\n",
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 )
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 )
253 else
255 SCIPdebugMsg(scip, " -> selected best leaf: estimate=%g\n",
257 }
258 }
259 }
260 }
261 }
262
263 return SCIP_OKAY;
264}
265
266
267/** node comparison method of node selector */
268static
270{ /*lint --e{715}*/
271 SCIP_NODESELDATA* nodeseldata;
272 SCIP_Real score1;
273 SCIP_Real score2;
274
275 assert(nodesel != NULL);
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);
287 {
290
291 nodetype1 = SCIPnodeGetType(node1);
292 nodetype2 = SCIPnodeGetType(node2);
294 return -1;
296 return +1;
298 return -1;
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
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 */
343
344 assert(nodesel != NULL);
345
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 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
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:7480
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition tree.c:7510
SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition tree.c:7520
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition tree.c:7500
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)
void SCIPnodeselSetData(SCIP_NODESEL *nodesel, SCIP_NODESELDATA *nodeseldata)
Definition nodesel.c:1130
SCIP_RETCODE SCIPsetNodeselFree(SCIP *scip, SCIP_NODESEL *nodesel,)
SCIP_NODESELDATA * SCIPnodeselGetData(SCIP_NODESEL *nodesel)
Definition nodesel.c:1120
SCIP_RETCODE SCIPsetNodeselCopy(SCIP *scip, SCIP_NODESEL *nodesel,)
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
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
#define BESTNODEFREQ
static SCIP_Real getNodeselScore(SCIP_NODE *node, SCIP_Real estimweight)
#define NODESEL_NAME
#define MAXPLUNGEQUOT
#define NODESEL_MEMSAVEPRIORITY
#define NODESEL_STDPRIORITY
#define ESTIMWEIGHT
#define NODESEL_DESC
#define MINPLUNGEDEPTH
#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
#define SCIP_DECL_NODESELCOMP(x)
#define SCIP_DECL_NODESELCOPY(x)
#define SCIP_DECL_NODESELSELECT(x)
#define SCIP_DECL_NODESELFREE(x)
struct SCIP_NodeselData SCIP_NODESELDATA
enum SCIP_Retcode SCIP_RETCODE
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