1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file nodesel_bfs.c
17 * @ingroup DEFPLUGINS_NODESEL
18 * @brief node selector for best first search
19 * @author Tobias Achterberg
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include "scip/nodesel_bfs.h"
25 #include "scip/pub_message.h"
26 #include "scip/pub_nodesel.h"
27 #include "scip/pub_tree.h"
28 #include "scip/scip_mem.h"
29 #include "scip/scip_message.h"
30 #include "scip/scip_nodesel.h"
31 #include "scip/scip_numerics.h"
32 #include "scip/scip_param.h"
33 #include "scip/scip_solvingstats.h"
34 #include "scip/scip_tree.h"
35 #include "scip/type_misc.h"
36 #include <string.h>
37
38 #define NODESEL_NAME "bfs"
39 #define NODESEL_DESC "best first search"
40 #define NODESEL_STDPRIORITY 100000
41 #define NODESEL_MEMSAVEPRIORITY 0
42
43
44 /*
45 * Default parameter settings
46 */
47
48 #define MINPLUNGEDEPTH -1 /**< minimal plunging depth, before new best node may be selected (-1 for dynamic setting) */
49 #define MAXPLUNGEDEPTH -1 /**< maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting) */
50 #define MAXPLUNGEQUOT 0.25 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
51 * where plunging is performed */
52
53
54 /** node selector data for best first search node selection */
55 struct SCIP_NodeselData
56 {
57 SCIP_Real maxplungequot; /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
58 * where plunging is performed */
59 int minplungedepth; /**< minimal plunging depth, before new best node may be selected
60 * (-1 for dynamic setting) */
61 int maxplungedepth; /**< maximal plunging depth, before new best node is forced to be selected
62 * (-1 for dynamic setting) */
63 };
64
65
66 /*
67 * Callback methods
68 */
69
70 /** copy method for node selector plugins (called when SCIP copies plugins) */
71 static
SCIP_DECL_NODESELCOPY(nodeselCopyBfs)72 SCIP_DECL_NODESELCOPY(nodeselCopyBfs)
73 { /*lint --e{715}*/
74 assert(scip != NULL);
75 assert(nodesel != NULL);
76 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
77
78 /* call inclusion method of node selector */
79 SCIP_CALL( SCIPincludeNodeselBfs(scip) );
80
81 return SCIP_OKAY;
82 }
83
84 /** destructor of node selector to free user data (called when SCIP is exiting) */
85 /**! [SnippetNodeselFreeBfs] */
86 static
SCIP_DECL_NODESELFREE(nodeselFreeBfs)87 SCIP_DECL_NODESELFREE(nodeselFreeBfs)
88 { /*lint --e{715}*/
89 SCIP_NODESELDATA* nodeseldata;
90
91 assert(nodesel != NULL);
92 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
93 assert(scip != NULL);
94
95 /* free user data of node selector */
96 nodeseldata = SCIPnodeselGetData(nodesel);
97 assert(nodeseldata != NULL);
98 SCIPfreeBlockMemory(scip, &nodeseldata);
99 SCIPnodeselSetData(nodesel, nodeseldata);
100
101 return SCIP_OKAY;
102 }
103 /**! [SnippetNodeselFreeBfs] */
104
105
106 /** node selection method of node selector */
107 static
SCIP_DECL_NODESELSELECT(nodeselSelectBfs)108 SCIP_DECL_NODESELSELECT(nodeselSelectBfs)
109 { /*lint --e{715}*/
110 SCIP_NODESELDATA* nodeseldata;
111 int minplungedepth;
112 int maxplungedepth;
113 int plungedepth;
114 SCIP_Real maxplungequot;
115
116 assert(nodesel != NULL);
117 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
118 assert(scip != NULL);
119 assert(selnode != NULL);
120
121 *selnode = NULL;
122
123 /* get node selector user data */
124 nodeseldata = SCIPnodeselGetData(nodesel);
125 assert(nodeseldata != NULL);
126
127 /* calculate minimal and maximal plunging depth */
128 minplungedepth = nodeseldata->minplungedepth;
129 maxplungedepth = nodeseldata->maxplungedepth;
130 maxplungequot = nodeseldata->maxplungequot;
131 if( minplungedepth == -1 )
132 {
133 minplungedepth = SCIPgetMaxDepth(scip)/10;
134 if( SCIPgetNStrongbranchLPIterations(scip) > 2*SCIPgetNNodeLPIterations(scip) )
135 minplungedepth += 10;
136 if( maxplungedepth >= 0 )
137 minplungedepth = MIN(minplungedepth, maxplungedepth);
138 }
139 if( maxplungedepth == -1 )
140 maxplungedepth = SCIPgetMaxDepth(scip)/2;
141 maxplungedepth = MAX(maxplungedepth, minplungedepth);
142
143 /* check, if we exceeded the maximal plunging depth */
144 plungedepth = SCIPgetPlungeDepth(scip);
145 if( plungedepth >= maxplungedepth )
146 {
147 /* we don't want to plunge again: select best node from the tree */
148 SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d -> abort plunging\n", minplungedepth, maxplungedepth, plungedepth);
149 *selnode = SCIPgetBestNode(scip);
150 SCIPdebugMsg(scip, " -> best node : lower=%g\n",
151 *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
152 }
153 else
154 {
155 SCIP_NODE* node;
156 SCIP_Real maxbound;
157
158 /* check, if plunging is forced at the current depth */
159 if( plungedepth < minplungedepth )
160 {
161 maxbound = SCIPinfinity(scip);
162 SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d => maxbound: infinity\n",
163 minplungedepth, maxplungedepth, plungedepth);
164 }
165 else
166 {
167 SCIP_Real lowerbound;
168 SCIP_Real cutoffbound;
169 /* get global lower and cutoff bound */
170 lowerbound = SCIPgetLowerbound(scip);
171 cutoffbound = SCIPgetCutoffbound(scip);
172
173 /* if we didn't find a solution yet, the cutoff bound is usually very bad:
174 * use only 20% of the gap as cutoff bound
175 */
176 if( SCIPgetNSolsFound(scip) == 0 )
177 cutoffbound = lowerbound + 0.2 * (cutoffbound - lowerbound);
178 /* calculate maximal plunging bound */
179 maxbound = lowerbound + maxplungequot * (cutoffbound - lowerbound);
180
181 SCIPdebugMsg(scip, "plungedepth: [%d,%d], cur: %d, bounds: [%g,%g], maxbound: %g\n",
182 minplungedepth, maxplungedepth, plungedepth, lowerbound, cutoffbound, maxbound);
183 }
184
185 /* we want to plunge again: prefer children over siblings, and siblings over leaves,
186 * but only select a child or sibling, if its dual bound is small enough;
187 * prefer using nodes with higher node selection priority assigned by the branching rule
188 */
189 node = SCIPgetPrioChild(scip);
190 if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
191 {
192 *selnode = node;
193 SCIPdebugMsg(scip, " -> selected prio child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
194 }
195 else
196 {
197 node = SCIPgetBestChild(scip);
198 if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
199 {
200 *selnode = node;
201 SCIPdebugMsg(scip, " -> selected best child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
202 }
203 else
204 {
205 node = SCIPgetPrioSibling(scip);
206 if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
207 {
208 *selnode = node;
209 SCIPdebugMsg(scip, " -> selected prio sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
210 }
211 else
212 {
213 node = SCIPgetBestSibling(scip);
214 if( node != NULL && SCIPnodeGetLowerbound(node) < maxbound )
215 {
216 *selnode = node;
217 SCIPdebugMsg(scip, " -> selected best sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
218 }
219 else
220 {
221 *selnode = SCIPgetBestNode(scip);
222 SCIPdebugMsg(scip, " -> selected best leaf: lower=%g\n",
223 *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
224 }
225 }
226 }
227 }
228 }
229
230 return SCIP_OKAY;
231 }
232
233
234 /** node comparison method of node selector */
235 static
SCIP_DECL_NODESELCOMP(nodeselCompBfs)236 SCIP_DECL_NODESELCOMP(nodeselCompBfs)
237 { /*lint --e{715}*/
238 SCIP_Real lowerbound1;
239 SCIP_Real lowerbound2;
240
241 assert(nodesel != NULL);
242 assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
243 assert(scip != NULL);
244
245 lowerbound1 = SCIPnodeGetLowerbound(node1);
246 lowerbound2 = SCIPnodeGetLowerbound(node2);
247 if( SCIPisLT(scip, lowerbound1, lowerbound2) )
248 return -1;
249 else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
250 return +1;
251 else
252 {
253 SCIP_Real estimate1;
254 SCIP_Real estimate2;
255
256 estimate1 = SCIPnodeGetEstimate(node1);
257 estimate2 = SCIPnodeGetEstimate(node2);
258 if( (SCIPisInfinity(scip, estimate1) && SCIPisInfinity(scip, estimate2)) ||
259 (SCIPisInfinity(scip, -estimate1) && SCIPisInfinity(scip, -estimate2)) ||
260 SCIPisEQ(scip, estimate1, estimate2) )
261 {
262 SCIP_NODETYPE nodetype1;
263 SCIP_NODETYPE nodetype2;
264
265 nodetype1 = SCIPnodeGetType(node1);
266 nodetype2 = SCIPnodeGetType(node2);
267 if( nodetype1 == SCIP_NODETYPE_CHILD && nodetype2 != SCIP_NODETYPE_CHILD )
268 return -1;
269 else if( nodetype1 != SCIP_NODETYPE_CHILD && nodetype2 == SCIP_NODETYPE_CHILD )
270 return +1;
271 else if( nodetype1 == SCIP_NODETYPE_SIBLING && nodetype2 != SCIP_NODETYPE_SIBLING )
272 return -1;
273 else if( nodetype1 != SCIP_NODETYPE_SIBLING && nodetype2 == SCIP_NODETYPE_SIBLING )
274 return +1;
275 else
276 {
277 int depth1;
278 int depth2;
279
280 depth1 = SCIPnodeGetDepth(node1);
281 depth2 = SCIPnodeGetDepth(node2);
282 if( depth1 < depth2 )
283 return -1;
284 else if( depth1 > depth2 )
285 return +1;
286 else
287 return 0;
288 }
289 }
290
291 if( SCIPisLT(scip, estimate1, estimate2) )
292 return -1;
293
294 assert(SCIPisGT(scip, estimate1, estimate2));
295 return +1;
296 }
297 }
298
299
300 /*
301 * bfs specific interface methods
302 */
303
304 /** creates the node selector for best first search and includes it in SCIP */
SCIPincludeNodeselBfs(SCIP * scip)305 SCIP_RETCODE SCIPincludeNodeselBfs(
306 SCIP* scip /**< SCIP data structure */
307 )
308 {
309 SCIP_NODESELDATA* nodeseldata;
310 SCIP_NODESEL* nodesel;
311
312 /* allocate and initialize node selector data; this has to be freed in the destructor */
313 SCIP_CALL( SCIPallocBlockMemory(scip, &nodeseldata) );
314
315 /* include node selector */
316 SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY,
317 nodeselSelectBfs, nodeselCompBfs, nodeseldata) );
318
319 assert(nodesel != NULL);
320
321 SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyBfs) );
322 SCIP_CALL( SCIPsetNodeselFree(scip, nodesel, nodeselFreeBfs) );
323
324 /* add node selector parameters */
325 SCIP_CALL( SCIPaddIntParam(scip,
326 "nodeselection/bfs/minplungedepth",
327 "minimal plunging depth, before new best node may be selected (-1 for dynamic setting)",
328 &nodeseldata->minplungedepth, TRUE, MINPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
329 SCIP_CALL( SCIPaddIntParam(scip,
330 "nodeselection/bfs/maxplungedepth",
331 "maximal plunging depth, before new best node is forced to be selected (-1 for dynamic setting)",
332 &nodeseldata->maxplungedepth, TRUE, MAXPLUNGEDEPTH, -1, INT_MAX, NULL, NULL) );
333 SCIP_CALL( SCIPaddRealParam(scip,
334 "nodeselection/bfs/maxplungequot",
335 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where plunging is performed",
336 &nodeseldata->maxplungequot, TRUE, MAXPLUNGEQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
337
338 return SCIP_OKAY;
339 }
340
341