1 2 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 3 /* */ 4 /* This file is part of the program and library */ 5 /* SCIP --- Solving Constraint Integer Programs */ 6 /* */ 7 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 8 /* */ 9 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 10 /* you may not use this file except in compliance with the License. */ 11 /* You may obtain a copy of the License at */ 12 /* */ 13 /* http://www.apache.org/licenses/LICENSE-2.0 */ 14 /* */ 15 /* Unless required by applicable law or agreed to in writing, software */ 16 /* distributed under the License is distributed on an "AS IS" BASIS, */ 17 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 18 /* See the License for the specific language governing permissions and */ 19 /* limitations under the License. */ 20 /* */ 21 /* You should have received a copy of the Apache-2.0 license */ 22 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 23 /* */ 24 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 25 26 /**@file branch_random.c 27 * @ingroup DEFPLUGINS_BRANCH 28 * @brief random variable branching rule 29 * @author Tobias Achterberg 30 * @author Stefan Vigerske 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #include "scip/branch_random.h" 36 #include "scip/pub_branch.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_misc.h" 39 #include "scip/pub_var.h" 40 #include "scip/scip_branch.h" 41 #include "scip/scip_message.h" 42 #include "scip/scip_mem.h" 43 #include "scip/scip_numerics.h" 44 #include "scip/scip_param.h" 45 #include "scip/scip_randnumgen.h" 46 #include "scip/scip_tree.h" 47 #include <string.h> 48 49 50 #define BRANCHRULE_NAME "random" 51 #define BRANCHRULE_DESC "random variable branching" 52 #define BRANCHRULE_PRIORITY -100000 53 #define BRANCHRULE_MAXDEPTH -1 54 #define BRANCHRULE_MAXBOUNDDIST 1.0 55 56 #define DEFAULT_INITSEED 41 /**< initial random seed */ 57 58 /** branching rule data */ 59 struct SCIP_BranchruleData 60 { 61 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 62 int initseed; /**< initial random seed value */ 63 }; 64 65 /* 66 * Local methods 67 */ 68 69 /** selects a random active variable from a given list of variables */ 70 static 71 void getRandomVariable( 72 SCIP* scip, /**< SCIP data structure */ 73 SCIP_BRANCHRULEDATA* branchruledata, /**< branchrule data */ 74 SCIP_VAR** cands, /**< array of branching candidates */ 75 SCIP_Real* candssol, /**< relaxation solution values of branching candidates, or NULL */ 76 int ncands, /**< number of branching candidates */ 77 SCIP_VAR** bestcand, /**< buffer to store pointer to best candidate */ 78 SCIP_Real* bestcandsol /**< buffer to store solution value of best candidate */ 79 ) 80 { 81 int idx; 82 int firstidx; 83 84 assert(scip != NULL); 85 assert(cands != NULL); 86 assert(ncands > 0); 87 assert(bestcand != NULL); 88 assert(bestcandsol != NULL); 89 90 idx = SCIPrandomGetInt(branchruledata->randnumgen, 0, ncands-1); 91 assert(idx >= 0); 92 93 /* handle case where cands[idx] is fixed by selecting next idx with unfixed var 94 * this may happen if we are inside a multi-aggregation */ 95 firstidx = idx; 96 while( SCIPisEQ(scip, SCIPvarGetLbLocal(cands[idx]), SCIPvarGetUbLocal(cands[idx])) ) 97 { 98 ++idx; 99 if( idx == ncands ) 100 idx = 0; 101 if( idx == firstidx ) 102 { 103 /* odd: all variables seem to be fixed */ 104 SCIPdebugMsg(scip, "Warning: all branching candidates seem to be fixed\n"); 105 return; 106 } 107 } 108 109 /* a branching variable candidate should either be an active problem variable or a multi-aggregated variable */ 110 assert(SCIPvarIsActive(SCIPvarGetProbvar(cands[idx])) || 111 SCIPvarGetStatus(SCIPvarGetProbvar(cands[idx])) == SCIP_VARSTATUS_MULTAGGR); 112 113 if( SCIPvarGetStatus(SCIPvarGetProbvar(cands[idx])) == SCIP_VARSTATUS_MULTAGGR ) 114 { 115 /* for a multi-aggregated variable, we call the getRandomVariable function recursively with all variables in the multi-aggregation */ 116 SCIP_VAR* cand; 117 118 cand = SCIPvarGetProbvar(cands[idx]); 119 120 getRandomVariable(scip, branchruledata, SCIPvarGetMultaggrVars(cand), NULL, SCIPvarGetMultaggrNVars(cand), 121 bestcand, bestcandsol); 122 return; 123 } 124 125 assert(idx >= 0 && idx < ncands); 126 127 *bestcand = cands[idx]; 128 assert(*bestcand != NULL); 129 130 if( candssol != NULL ) 131 *bestcandsol = candssol[idx]; 132 } 133 134 /* 135 * Callback methods 136 */ 137 138 /** copy method for branchrule plugins (called when SCIP copies plugins) */ 139 static 140 SCIP_DECL_BRANCHCOPY(branchCopyRandom) 141 { /*lint --e{715}*/ 142 assert(scip != NULL); 143 assert(branchrule != NULL); 144 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 145 146 /* call inclusion method of branchrule */ 147 SCIP_CALL( SCIPincludeBranchruleRandom(scip) ); 148 149 return SCIP_OKAY; 150 } 151 152 /** destructor of branching rule to free user data (called when SCIP is exiting) */ 153 /**! [SnippetBranchFreeRandom] */ 154 static 155 SCIP_DECL_BRANCHFREE(branchFreeRandom) 156 { /*lint --e{715}*/ 157 SCIP_BRANCHRULEDATA* branchruledata; 158 159 /* get branching rule data */ 160 branchruledata = SCIPbranchruleGetData(branchrule); 161 assert(branchruledata != NULL); 162 163 /* free branching rule data */ 164 SCIPfreeBlockMemory(scip, &branchruledata); 165 SCIPbranchruleSetData(branchrule, NULL); 166 167 return SCIP_OKAY; 168 } 169 /**! [SnippetBranchFreeRandom] */ 170 171 172 /** initialization method of branching rule (called after problem was transformed) */ 173 static 174 SCIP_DECL_BRANCHINIT(branchInitRandom) 175 { /*lint --e{715}*/ 176 SCIP_BRANCHRULEDATA* branchruledata; 177 178 branchruledata = SCIPbranchruleGetData(branchrule); 179 assert(branchruledata != NULL); 180 assert(branchruledata->initseed >= 0); 181 182 /* create a random number generator */ 183 SCIP_CALL( SCIPcreateRandom(scip, &branchruledata->randnumgen, 184 (unsigned int)branchruledata->initseed, TRUE) ); 185 186 return SCIP_OKAY; 187 } 188 189 /** deinitialization method of branching rule */ 190 static 191 SCIP_DECL_BRANCHEXIT(branchExitRandom) 192 { /*lint --e{715}*/ 193 SCIP_BRANCHRULEDATA* branchruledata; 194 195 /* get branching rule data */ 196 branchruledata = SCIPbranchruleGetData(branchrule); 197 assert(branchruledata != NULL); 198 199 /* free random number generator */ 200 SCIPfreeRandom(scip, &branchruledata->randnumgen); 201 202 return SCIP_OKAY; 203 } 204 205 /** branching execution method for fractional LP solutions */ 206 static 207 SCIP_DECL_BRANCHEXECLP(branchExeclpRandom) 208 { /*lint --e{715}*/ 209 SCIP_BRANCHRULEDATA* branchruledata; 210 SCIP_VAR** lpcands; 211 int nlpcands; 212 int bestcand; 213 214 assert(branchrule != NULL); 215 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 216 assert(scip != NULL); 217 assert(result != NULL); 218 219 SCIPdebugMsg(scip, "Execlp method of random branching in depth %d\n", SCIPgetDepth(scip)); 220 221 branchruledata = SCIPbranchruleGetData(branchrule); 222 assert(branchruledata != NULL); 223 224 /* get branching candidates */ 225 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, NULL, NULL, &nlpcands, NULL) ); 226 assert(nlpcands > 0); 227 228 /* get random branching candidate */ 229 bestcand = SCIPrandomGetInt(branchruledata->randnumgen, 0, nlpcands-1); 230 assert(bestcand >= 0); 231 232 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s>\n", 233 nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand])); 234 235 /* perform the branching */ 236 SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) ); 237 *result = SCIP_BRANCHED; 238 239 return SCIP_OKAY; 240 } 241 242 243 /** branching execution method for external candidates */ 244 static 245 SCIP_DECL_BRANCHEXECEXT(branchExecextRandom) 246 { /*lint --e{715}*/ 247 SCIP_BRANCHRULEDATA* branchruledata; 248 SCIP_VAR** externcands; 249 SCIP_Real* externcandssol; 250 int nprioexterncands; 251 SCIP_VAR* bestcand; 252 SCIP_Real bestcandsol; 253 SCIP_Real brpoint; 254 SCIP_NODE* downchild; 255 SCIP_NODE* eqchild; 256 SCIP_NODE* upchild; 257 258 assert(branchrule != NULL); 259 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 260 assert(scip != NULL); 261 assert(result != NULL); 262 263 SCIPdebugMsg(scip, "Execrel method of random branching\n"); 264 265 branchruledata = SCIPbranchruleGetData(branchrule); 266 assert(branchruledata != NULL); 267 268 bestcand = NULL; 269 bestcandsol = 0.0; 270 271 /* get branching candidates */ 272 SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, NULL, NULL, &nprioexterncands, NULL, NULL, NULL) ); 273 assert(nprioexterncands > 0); 274 275 /* get random branching candidate 276 * 277 * since variables can occur several times in the list of candidates, variables that have been added more often have 278 * a higher probability to be chosen for branching 279 */ 280 getRandomVariable(scip, branchruledata, externcands, externcandssol, nprioexterncands, &bestcand, &bestcandsol); 281 282 if( bestcand == NULL ) 283 { 284 SCIPerrorMessage("branchExecrelRandom failed to select a branching variable from %d candidates\n", nprioexterncands); 285 *result = SCIP_DIDNOTRUN; 286 return SCIP_OKAY; 287 } 288 289 brpoint = SCIPgetBranchingPoint(scip, bestcand, bestcandsol); 290 291 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s> with solution value %g, branching point=%g\n", 292 nprioexterncands, SCIPvarGetName(bestcand), bestcandsol, brpoint); 293 294 SCIP_CALL( SCIPbranchVarVal(scip, bestcand, brpoint, &downchild, &eqchild, &upchild) ); 295 296 if( downchild != NULL || eqchild != NULL || upchild != NULL ) 297 { 298 *result = SCIP_BRANCHED; 299 } 300 else 301 { 302 /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */ 303 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand))); 304 *result = SCIP_REDUCEDDOM; 305 } 306 307 return SCIP_OKAY; 308 } 309 310 /** branching execution method for not completely fixed pseudo solutions */ 311 static 312 SCIP_DECL_BRANCHEXECPS(branchExecpsRandom) 313 { /*lint --e{715}*/ 314 SCIP_BRANCHRULEDATA* branchruledata; 315 SCIP_VAR** pseudocands; 316 int npseudocands; 317 int bestcand; 318 319 assert(branchrule != NULL); 320 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 321 assert(scip != NULL); 322 assert(result != NULL); 323 324 SCIPdebugMsg(scip, "Execps method of random branching\n"); 325 326 branchruledata = SCIPbranchruleGetData(branchrule); 327 assert(branchruledata != NULL); 328 329 /* get branching candidates */ 330 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, NULL, &npseudocands) ); 331 assert(npseudocands > 0); 332 333 /* get random branching candidate */ 334 bestcand = SCIPrandomGetInt(branchruledata->randnumgen, 0, npseudocands-1); 335 assert(bestcand >= 0); 336 337 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s>\n", 338 npseudocands, bestcand, SCIPvarGetName(pseudocands[bestcand])); 339 340 /* perform the branching */ 341 SCIP_CALL( SCIPbranchVar(scip, pseudocands[bestcand], NULL, NULL, NULL) ); 342 *result = SCIP_BRANCHED; 343 344 return SCIP_OKAY; 345 } 346 347 348 /* 349 * branching specific interface methods 350 */ 351 352 /** creates the random branching rule and includes it in SCIP */ 353 SCIP_RETCODE SCIPincludeBranchruleRandom( 354 SCIP* scip /**< SCIP data structure */ 355 ) 356 { 357 SCIP_BRANCHRULEDATA* branchruledata; 358 SCIP_BRANCHRULE* branchrule; 359 360 /* create random branching rule data */ 361 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) ); 362 363 /* include allfullstrong branching rule */ 364 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, 365 BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) ); 366 367 assert(branchrule != NULL); 368 369 /* set non-fundamental callbacks via specific setter functions*/ 370 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyRandom) ); 371 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeRandom) ); 372 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitRandom) ); 373 SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitRandom) ); 374 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpRandom) ); 375 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextRandom) ); 376 SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsRandom) ); 377 378 SCIP_CALL( SCIPaddIntParam(scip, "branching/" BRANCHRULE_NAME "/seed", "initial random seed value", 379 &branchruledata->initseed, FALSE, DEFAULT_INITSEED, 0, INT_MAX, NULL, NULL) ); 380 381 return SCIP_OKAY; 382 } 383