1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 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 33 #include "scip/nodesel_estimate.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" 42 #include "scip/scip_solvingstats.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 */ 66 struct 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) */ 86 static 87 SCIP_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 */ 94 SCIP_CALL( SCIPincludeNodeselEstimate(scip) ); 95 96 return SCIP_OKAY; 97 } 98 99 /** destructor of node selector to free user data (called when SCIP is exiting) */ 100 static 101 SCIP_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 */ 120 static 121 SCIP_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; 190 if( SCIPgetNStrongbranchLPIterations(scip) > 2*SCIPgetNNodeLPIterations(scip) ) 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 */ 294 static 295 SCIP_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 */ 364 SCIP_RETCODE SCIPincludeNodeselEstimate( 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 */ 375 SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY, 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 */ 384 SCIP_CALL( SCIPaddIntParam(scip, 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) ); 388 SCIP_CALL( SCIPaddIntParam(scip, 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) ); 392 SCIP_CALL( SCIPaddRealParam(scip, 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) ); 396 SCIP_CALL( SCIPaddIntParam(scip, 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) ); 400 SCIP_CALL( SCIPaddIntParam(scip, 401 "nodeselection/estimate/breadthfirstdepth", 402 "depth until breadth-first search is applied", 403 &nodeseldata->breadthfirstdepth, FALSE, DEFAULT_BREADTHFIRSTDEPTH, -1, INT_MAX, NULL, NULL) ); 404 SCIP_CALL( SCIPaddIntParam(scip, 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 412