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