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_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 33 #include "scip/nodesel_hybridestim.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 "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 */ 66 struct 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 */ 86 static 87 SCIP_Real getNodeselScore( 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) */ 101 static 102 SCIP_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 */ 109 SCIP_CALL( SCIPincludeNodeselHybridestim(scip) ); 110 111 return SCIP_OKAY; 112 } 113 114 /** destructor of node selector to free user data (called when SCIP is exiting) */ 115 static 116 SCIP_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 */ 135 static 136 SCIP_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; 163 if( SCIPgetNStrongbranchLPIterations(scip) > 2*SCIPgetNNodeLPIterations(scip) ) 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 */ 268 static 269 SCIP_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 */ 330 SCIP_RETCODE SCIPincludeNodeselHybridestim( 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 */ 341 SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY, 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 */ 350 SCIP_CALL( SCIPaddIntParam(scip, 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) ); 354 SCIP_CALL( SCIPaddIntParam(scip, 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) ); 358 SCIP_CALL( SCIPaddRealParam(scip, 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) ); 362 SCIP_CALL( SCIPaddIntParam(scip, 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) ); 366 SCIP_CALL( SCIPaddRealParam(scip, 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 374