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 branch_cloud.c 26 * @ingroup DEFPLUGINS_BRANCH 27 * @brief cloud branching rule 28 * @author Timo Berthold 29 * @author Domenico Salvagnin 30 * 31 * Branching rule based on muliple optimal solutions to the current LP relaxation. See@n 32 * Cloud Branching@n 33 * Timo Berthold and Domenico Salvagnin@n 34 * Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2013, LNCS 7874@n 35 * Preliminary version available as <a href="http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1730">ZIB-Report 13-01</a>. 36 */ 37 38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 39 40 #include "blockmemshell/memory.h" 41 #include "scip/branch_allfullstrong.h" 42 #include "scip/branch_cloud.h" 43 #include "scip/branch_fullstrong.h" 44 #include "scip/pub_branch.h" 45 #include "scip/pub_lp.h" 46 #include "scip/pub_message.h" 47 #include "scip/pub_tree.h" 48 #include "scip/pub_var.h" 49 #include "scip/scip_branch.h" 50 #include "scip/scip_general.h" 51 #include "scip/scip_lp.h" 52 #include "scip/scip_mem.h" 53 #include "scip/scip_message.h" 54 #include "scip/scip_numerics.h" 55 #include "scip/scip_param.h" 56 #include "scip/scip_prob.h" 57 #include "scip/scip_sol.h" 58 #include "scip/scip_solvingstats.h" 59 #include "scip/scip_timing.h" 60 #include "scip/scip_tree.h" 61 #include "scip/scip_var.h" 62 #include <string.h> 63 64 65 #define BRANCHRULE_NAME "cloud" 66 #define BRANCHRULE_DESC "branching rule that considers several alternative LP optima" 67 #define BRANCHRULE_PRIORITY 0 68 #define BRANCHRULE_MAXDEPTH -1 69 #define BRANCHRULE_MAXBOUNDDIST 1.0 70 71 #define DEFAULT_USECLOUD TRUE /**< should a cloud of points be used? */ 72 #define DEFAULT_USEUNION FALSE /**< should the union of candidates be used? */ 73 #define DEFAULT_MAXPOINTS -1 /**< maximum number of points for the cloud (-1 means no limit) */ 74 #define DEFAULT_MINSUCCESSRATE 0.0 /**< minimum success rate for the cloud */ 75 #define DEFAULT_MINSUCCESSUNION 0.0 /**< minimum success rate for the union */ 76 #define DEFAULT_MAXDEPTHUNION 65000 /**< maximum depth for the union */ 77 #define DEFAULT_ONLYF2 FALSE /**< should only F2 be used? */ 78 79 /* 80 * Data structures 81 */ 82 83 /** branching rule data */ 84 struct SCIP_BranchruleData 85 { 86 int lastcand; /**< last evaluated candidate of last branching rule execution */ 87 SCIP_Bool usecloud; /**< should a cloud of points be used? */ 88 SCIP_Bool useunion; /**< should the union of candidates be used? */ 89 SCIP_Bool onlyF2; /**< should only F2 be used? */ 90 int maxpoints; /**< maximum number of points for the cloud (-1 means no limit) */ 91 SCIP_Real minsuccessrate; /**< minimum success rate for the cloud */ 92 SCIP_Real minsuccessunion; /**< minimum success rate for the union */ 93 SCIP_CLOCK* cloudclock; /**< clock for cloud diving */ 94 SCIP_Bool* skipdown; /**< should down branch be skiped? */ 95 SCIP_Bool* skipup; /**< should up branch be skiped? */ 96 int ntried; /**< number of times the cloud was tried */ 97 int ntriedunions; /**< number of times the cloud was tried */ 98 int nuseful; /**< number of times the cloud was useful (at least one LP skipped) */ 99 int nusefulunions; /**< number of times the union was useful (took candidate from new list) */ 100 int ncloudpoints; /**< sum of cloud points taken over all nodes with at least two poitns in cloud */ 101 int nsavedlps; /**< sum of saved LPs taken over all nodes with at least two points in cloud */ 102 int maxdepthunion; /**< maximum depth for the union */ 103 int skipsize; /**< size of skipdown and skipup array */ 104 }; 105 106 /* 107 * Callback methods of branching rule 108 */ 109 110 /** destructor of branching rule to free user data (called when SCIP is exiting) */ 111 static 112 SCIP_DECL_BRANCHFREE(branchFreeCloud) 113 { /*lint --e{715}*/ 114 SCIP_BRANCHRULEDATA* branchruledata; 115 116 /* free branching rule data */ 117 branchruledata = SCIPbranchruleGetData(branchrule); 118 119 if( branchruledata->cloudclock != NULL) 120 { 121 SCIPstatistic( 122 int ntried; 123 int nuseful; 124 int ncloudpoints; 125 int nsavedlps; 126 127 ntried = branchruledata->ntried; 128 nuseful = branchruledata->nuseful; 129 ncloudpoints = branchruledata->ncloudpoints; 130 nsavedlps = branchruledata->nsavedlps; 131 132 SCIPstatisticMessage("time spent diving in cloud branching: %g\n", SCIPgetClockTime(scip, branchruledata->cloudclock)); 133 SCIPstatisticMessage("cloud branching tried: %6d found cloud: %6d \n", ntried, nuseful); 134 SCIPstatisticMessage("cloud used points: %6d saved LPs: %6d \n", ncloudpoints, nsavedlps); 135 SCIPstatisticMessage("cloud success rates useful/tried: %8.6g points/useful: %8.6g saved/useful: %8.6g \n", 136 ntried == 0 ? -1 : (SCIP_Real)nuseful / ntried, nuseful == 0 ? -1 : (SCIP_Real)ncloudpoints / nuseful, nuseful == 0 ? -1 : (SCIP_Real)nsavedlps / nuseful); 137 ) 138 139 SCIP_CALL( SCIPfreeClock(scip, &(branchruledata->cloudclock)) ); 140 } 141 142 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize); 143 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize); 144 145 SCIPfreeBlockMemory(scip, &branchruledata); 146 SCIPbranchruleSetData(branchrule, NULL); 147 148 return SCIP_OKAY; 149 } 150 151 152 /** initialization method of branching rule (called after problem was transformed) */ 153 static 154 SCIP_DECL_BRANCHINIT(branchInitCloud) 155 { /*lint --e{715}*/ 156 SCIP_BRANCHRULEDATA* branchruledata; 157 158 /* initialize branching rule data */ 159 branchruledata = SCIPbranchruleGetData(branchrule); 160 branchruledata->lastcand = 0; 161 branchruledata->nuseful = 0; 162 branchruledata->nusefulunions = 0; 163 branchruledata->ntried = 0; 164 branchruledata->ntriedunions = 0; 165 branchruledata->ncloudpoints = 0; 166 branchruledata->nsavedlps = 0; 167 168 if( branchruledata->cloudclock != NULL) 169 { 170 SCIP_CALL( SCIPresetClock(scip, branchruledata->cloudclock) ); 171 } 172 173 return SCIP_OKAY; 174 } 175 176 /** branching execution method for fractional LP solutions */ 177 static 178 SCIP_DECL_BRANCHEXECLP(branchExeclpCloud) 179 { /*lint --e{715}*/ 180 SCIP_BRANCHRULEDATA* branchruledata; 181 182 SCIP_VAR** lpcands; 183 SCIP_VAR** lpcandscopy; 184 185 SCIP_VAR** vars; 186 SCIP_ROW** lprows; 187 SCIP_Real* lpcandsfrac; 188 SCIP_Real* lpcandssol; 189 SCIP_Real* lpcandsfraccopy; 190 SCIP_Real* lpcandssolcopy; 191 SCIP_Real* lpcandsmin; 192 SCIP_Real* lpcandsmax; 193 SCIP_Real* newlpcandsmin; 194 SCIP_Real* newlpcandsmax; 195 196 SCIP_Real bestdown; 197 SCIP_Real bestup; 198 SCIP_Real bestscore; 199 SCIP_Real provedbound; 200 201 SCIP_Bool bestdownvalid; 202 SCIP_Bool bestupvalid; 203 SCIP_Bool newpoint; 204 SCIP_Bool lperror; 205 206 int nlpcands; 207 int npriolpcands; 208 int nvars; 209 int bestcand; 210 int nlprows; 211 int i; 212 int counter; 213 int ncomplete; 214 int ndiscvars; 215 216 assert(branchrule != NULL); 217 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 218 assert(scip != NULL); 219 assert(result != NULL); 220 221 if( !SCIPisLPSolBasic(scip) ) 222 return SCIP_OKAY; 223 224 SCIPdebugMsg(scip, "Execlp method of " BRANCHRULE_NAME " branching\n"); 225 226 /* get problem variables and LP row data */ 227 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 228 ndiscvars = SCIPgetNBinVars(scip)+SCIPgetNIntVars(scip); 229 nlprows = SCIPgetNLPRows(scip); 230 lprows = SCIPgetLPRows(scip); 231 232 /* get branching candidates */ 233 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, &npriolpcands, NULL) ); 234 nlpcands = SCIPgetNLPBranchCands(scip); 235 assert(nlpcands > 0); 236 237 /* get branching rule data */ 238 branchruledata = SCIPbranchruleGetData(branchrule); 239 assert(branchruledata != NULL); 240 241 /* allocate skipping arrays on first call */ 242 if( branchruledata->skipdown == NULL ) 243 { 244 assert(branchruledata->skipup == NULL); 245 246 branchruledata->skipsize = nvars; 247 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) ); 248 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) ); 249 } 250 251 /* reset skipping arrays to zero */ 252 BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize); 253 BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize); 254 255 /* allocate required data structures */ 256 SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsmin, nlpcands) ); 257 SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsmax, nlpcands) ); 258 SCIP_CALL( SCIPallocBufferArray(scip, &lpcandscopy, nlpcands) ); 259 SCIP_CALL( SCIPallocBufferArray(scip, &lpcandsfraccopy, nlpcands) ); 260 SCIP_CALL( SCIPallocBufferArray(scip, &lpcandssolcopy, nlpcands) ); 261 newlpcandsmin = NULL; 262 newlpcandsmax = NULL; 263 if( branchruledata->useunion && SCIPgetDepth(scip) < branchruledata->maxdepthunion && !branchruledata->onlyF2) 264 { 265 SCIP_CALL( SCIPallocBufferArray(scip, &newlpcandsmin, ndiscvars) ); 266 SCIP_CALL( SCIPallocBufferArray(scip, &newlpcandsmax, ndiscvars) ); 267 } 268 BMScopyMemoryArray(lpcandsmin, lpcandssol, nlpcands); 269 BMScopyMemoryArray(lpcandsmax, lpcandssol, nlpcands); 270 BMScopyMemoryArray(lpcandssolcopy, lpcandssol, nlpcands); 271 BMScopyMemoryArray(lpcandsfraccopy, lpcandsfrac, nlpcands); 272 BMScopyMemoryArray(lpcandscopy, lpcands, nlpcands); 273 274 SCIP_CALL( SCIPstartClock(scip, branchruledata->cloudclock) ); 275 branchruledata->ntried++; 276 277 /* start diving to calculate the solution cloud */ 278 SCIP_CALL( SCIPstartDive(scip) ); 279 280 /* fix variables with nonzero reduced costs to reduce LP to the optimal face */ 281 for( i = 0; i < nvars; ++i ) 282 { 283 SCIP_Real solval; 284 solval = SCIPgetSolVal(scip, NULL, vars[i]); 285 286 if( !SCIPisFeasZero(scip, SCIPgetVarRedcost(scip, vars[i])) ) 287 { 288 SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], solval) ); 289 SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], solval) ); 290 } 291 else if( SCIPvarGetType(vars[i]) == SCIP_VARTYPE_INTEGER && !SCIPisIntegral(scip, solval) ) 292 { 293 SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], SCIPfloor(scip, solval)) ); 294 SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], SCIPceil(scip, solval)) ); 295 } 296 297 SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], 0.0) ); 298 } 299 300 /* fix LP rows with nonzero dual solution to reduce LP to the optimal face */ 301 for( i = 0; i < nlprows; ++i ) 302 { 303 SCIP_Real dualsol; 304 dualsol = SCIProwGetDualsol(lprows[i]); 305 if( !SCIPisZero(scip, dualsol) ) 306 { 307 if( dualsol > 0 && SCIPisFeasEQ(scip, SCIProwGetLhs(lprows[i]), SCIPgetRowActivity(scip,lprows[i])) ) 308 { 309 SCIP_CALL( SCIPchgRowRhsDive(scip, lprows[i], SCIProwGetLhs(lprows[i])) ); 310 } 311 else if( dualsol < 0 && SCIPisFeasEQ(scip, SCIProwGetRhs(lprows[i]), SCIPgetRowActivity(scip,lprows[i])) ) 312 { 313 SCIP_CALL( SCIPchgRowLhsDive(scip, lprows[i], SCIProwGetRhs(lprows[i])) ); 314 } 315 } 316 } 317 318 newpoint = TRUE; 319 counter = 0; 320 321 if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion ) 322 { 323 /* update cloud intervals for candidates that have been integral in original LP, but have been fractional in previous cloud points */ 324 for( i = 0; i < ndiscvars; ++i) 325 { 326 SCIP_Real solval; 327 solval = SCIPgetSolVal(scip, NULL, vars[i]); 328 329 assert(newlpcandsmin != NULL); 330 assert(newlpcandsmax != NULL); 331 332 newlpcandsmin[i] = solval; 333 newlpcandsmax[i] = solval; 334 } 335 } 336 337 /* loop that generates new cloud point */ 338 while( newpoint && branchruledata->usecloud ) 339 { 340 #ifdef NDEBUG 341 SCIP_RETCODE retcode; 342 #endif 343 344 /* apply feasibility pump objective function to fractional variables */ 345 for( i = 0; i < nlpcands; ++i ) 346 { 347 SCIP_Real frac; 348 frac = SCIPfrac(scip, SCIPgetSolVal(scip, NULL, lpcandscopy[i])); 349 350 if( !SCIPisZero(scip, frac) && !SCIPisIntegral(scip, lpcandsmin[i]) && !SCIPisIntegral(scip, lpcandsmax[i]) ) 351 { 352 if( frac < 0.5 ) 353 { 354 SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], 1.0) ); 355 } 356 else 357 { 358 SCIP_CALL( SCIPchgVarObjDive(scip, vars[i], -1.0) ); 359 } 360 } 361 } 362 363 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic. 364 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 365 */ 366 #ifdef NDEBUG 367 retcode = SCIPsolveDiveLP(scip, -1, &lperror, NULL); 368 if( retcode != SCIP_OKAY ) 369 { 370 SCIPwarningMessage(scip, "Error while solving LP in " BRANCHRULE_NAME "; LP solve terminated with code <%d>\n",retcode); 371 } 372 #else 373 SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) ); 374 #endif 375 376 if( lperror || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 377 break; 378 379 /* check if a solution has been found */ 380 if( SCIPgetNLPBranchCands(scip) == 0 ) 381 { 382 SCIP_Bool success; 383 SCIP_SOL* sol; 384 385 /* create solution from diving LP */ 386 SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) ); 387 SCIP_CALL( SCIPlinkLPSol(scip, sol) ); 388 SCIPdebugMsg(scip, "cloud branching found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, sol)); 389 390 /* try to add solution to SCIP */ 391 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) ); 392 393 /* check, if solution was feasible and good enough */ 394 if( success ) 395 { 396 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n"); 397 SCIP_CALL( SCIPendDive(scip) ); 398 *result = SCIP_CUTOFF; 399 goto TERMINATE; 400 } 401 } 402 403 /* update cloud intervals for candidates that have been fractional in original LP */ 404 newpoint = FALSE; 405 for( i = 0; i < nlpcands; ++i) 406 { 407 SCIP_Real solval; 408 solval = SCIPgetSolVal(scip, NULL, lpcandscopy[i]); 409 410 if( SCIPisFeasIntegral(scip,solval) && !SCIPisFeasIntegral(scip, lpcandsmin[i]) && !SCIPisFeasIntegral(scip, lpcandsmax[i]) ) 411 newpoint = TRUE; 412 413 lpcandsmin[i] = MIN(lpcandsmin[i], solval); 414 lpcandsmax[i] = MAX(lpcandsmax[i], solval); 415 } 416 417 if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion ) 418 { 419 /* update cloud intervals for candidates that have been integral in original LP, but have been fractional in previous cloud points */ 420 for( i = 0; i < ndiscvars; ++i) 421 { 422 SCIP_Real solval; 423 solval = SCIPgetSolVal(scip, NULL, vars[i]); 424 425 assert(newlpcandsmin != NULL); 426 assert(newlpcandsmax != NULL); 427 428 newlpcandsmin[i] = MIN(newlpcandsmin[i], solval); 429 newlpcandsmax[i] = MAX(newlpcandsmax[i], solval); 430 } 431 } 432 433 if( newpoint ) 434 counter++; 435 436 if( branchruledata->maxpoints != -1 && counter >= branchruledata->maxpoints ) 437 break; 438 } 439 440 SCIPdebugMsg(scip, "considered %d additional points in the cloud\n",counter); 441 442 /* terminate the diving */ 443 SCIP_CALL( SCIPendDive(scip) ); 444 445 SCIP_CALL( SCIPstopClock(scip, branchruledata->cloudclock) ); 446 ncomplete = nlpcands; 447 448 if( counter > 0 ) 449 { 450 branchruledata->ncloudpoints += (counter+1); 451 branchruledata->nuseful++; 452 453 counter = 0; 454 455 /* sort all variables for which both bounds are fractional to the front */ 456 for( i = 0; i < nlpcands; ++i) 457 { 458 if( !SCIPisFeasIntegral(scip, lpcandsmin[i]) && !SCIPisFeasIntegral(scip, lpcandsmax[i]) ) 459 { 460 assert(counter <= i); 461 lpcandscopy[counter] = lpcandscopy[i]; 462 lpcandssolcopy[counter] = lpcandssolcopy[i]; 463 lpcandsfraccopy[counter] = lpcandsfraccopy[i]; 464 counter++; 465 } 466 } 467 468 /* should only be in that if condition when at least one bound could be made integral */ 469 assert(nlpcands - counter > 0); 470 471 ncomplete = counter; 472 473 /* filter all variables for which exactly one interval bound is fractional */ 474 for( i = 0; i < nlpcands && !branchruledata->onlyF2; ++i) 475 { 476 if( SCIPisFeasIntegral(scip, lpcandsmin[i]) != SCIPisFeasIntegral(scip, lpcandsmax[i]) ) 477 { 478 assert(counter < nlpcands); 479 lpcandscopy[counter] = lpcandscopy[i]; 480 lpcandssolcopy[counter] = lpcandssolcopy[i]; 481 lpcandsfraccopy[counter] = lpcandsfraccopy[i]; 482 483 if( SCIPisFeasIntegral(scip, lpcandsmin[i]) ) 484 branchruledata->skipdown[counter] = TRUE; 485 if( SCIPisFeasIntegral(scip, lpcandsmax[i]) ) 486 branchruledata->skipup[counter] = TRUE; 487 assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]); 488 489 counter++; 490 } 491 } 492 493 SCIPdebugMsg(scip, "can fully skip %d/%d strong branching candidates\n", nlpcands - counter, nlpcands); 494 SCIPdebugMsg(scip, "can half skip %d/%d strong branching candidates\n", counter - ncomplete, nlpcands); 495 } 496 else 497 counter = nlpcands; 498 499 /* if cloud sampling was not successful enough, disable it */ 500 if( branchruledata->usecloud && 501 branchruledata->ntried > 100 && 502 (SCIP_Real)branchruledata->nuseful / branchruledata->ntried < branchruledata->minsuccessrate ) 503 { 504 SCIPdebugMsg(scip, "Disabling cloud branching (not effective)\n"); 505 branchruledata->usecloud = FALSE; 506 } 507 508 if( branchruledata->onlyF2 ) 509 counter = MAX(counter,1); 510 511 /* the second counter should maybe be replaced at some point */ 512 SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcandscopy, lpcandssolcopy, lpcandsfraccopy, branchruledata->skipdown, 513 branchruledata->skipup, counter, counter, ncomplete, &branchruledata->lastcand, 0, FALSE, FALSE, 514 &bestcand, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) ); 515 516 if( branchruledata->lastcand <= ncomplete ) 517 { 518 SCIPdebugMsg(scip, "saved %d of %d LPs\n", 2*(nlpcands - ncomplete), 2*nlpcands); 519 branchruledata->nsavedlps += 2*(nlpcands - ncomplete); 520 } 521 else 522 { 523 SCIPdebugMsg(scip, "saved %d of %d LPs\n", 2*(nlpcands - counter)+counter - ncomplete, 2*nlpcands); 524 branchruledata->nsavedlps += 2*(nlpcands - counter)+counter - ncomplete; 525 } 526 527 /* perform the branching */ 528 if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED && counter > 0 ) 529 { 530 SCIP_NODE* downchild; 531 SCIP_NODE* upchild; 532 SCIP_VAR* var; 533 SCIP_Bool allcolsinlp; 534 SCIP_Bool exactsolve; 535 SCIP_Bool newselected; 536 537 assert(*result == SCIP_DIDNOTRUN); 538 assert(0 <= bestcand && bestcand < nlpcands); 539 assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip))); 540 541 var = lpcandscopy[bestcand]; 542 newselected = FALSE; 543 544 /* if there are new candidates variables, also try them */ 545 if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion && branchruledata->lastcand > ncomplete ) 546 { 547 SCIP_VAR** newlpcands; 548 549 counter = 0; 550 /* reset skipping arrays to zero */ 551 BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize); 552 BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize); 553 554 SCIP_CALL( SCIPallocBufferArray(scip, &newlpcands, ndiscvars) ); 555 556 /* get new LP candidates with one fractional bound */ 557 for( i = 0; i < ndiscvars; ++i) 558 { 559 if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, NULL, vars[i])) ) 560 continue; 561 562 assert(newlpcandsmin != NULL); 563 assert(newlpcandsmax != NULL); 564 565 if( SCIPisFeasIntegral(scip, newlpcandsmin[i]) != SCIPisFeasIntegral(scip, newlpcandsmax[i]) ) 566 { 567 newlpcands[counter] = vars[i]; 568 569 if( SCIPisFeasIntegral(scip, newlpcandsmin[i]) ) 570 branchruledata->skipdown[counter] = TRUE; 571 if( SCIPisFeasIntegral(scip, newlpcandsmax[i]) ) 572 branchruledata->skipup[counter] = TRUE; 573 assert(branchruledata->skipdown[counter] != branchruledata->skipup[counter]); 574 575 counter++; 576 } 577 } 578 579 /* when there are new candidates, also try these */ 580 if( counter > 0 ) 581 { 582 SCIP_Real newdown; 583 SCIP_Real newup; 584 SCIP_Real newscore; 585 int newcand; 586 SCIP_Bool newdownvalid; 587 SCIP_Bool newupvalid; 588 SCIP_Real newbound; 589 590 branchruledata->ntriedunions++; 591 newscore = -SCIPinfinity(scip); 592 SCIP_CALL( SCIPselectVarPseudoStrongBranching(scip, newlpcands, branchruledata->skipdown, branchruledata->skipup, counter, counter, 593 &newcand, &newdown, &newup, &newscore, &newdownvalid, &newupvalid, &newbound, result) ); 594 595 if( *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM || *result == SCIP_CONSADDED ) 596 { 597 SCIPfreeBufferArray(scip, &newlpcands); 598 goto TERMINATE; 599 } 600 601 if( newscore > bestscore ) 602 { 603 bestcand = newcand; 604 var = newlpcands[newcand]; 605 bestdown = newdown; 606 bestup = newup; 607 bestdownvalid = newdownvalid; 608 bestupvalid = newupvalid; 609 bestscore = newscore; 610 newselected = TRUE; 611 branchruledata->nusefulunions++; 612 } 613 } 614 /* free temporary array for new union candidates */ 615 SCIPfreeBufferArray(scip, &newlpcands); 616 } 617 618 /* perform the branching */ 619 if( !newselected ) 620 { 621 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n", 622 counter, bestcand, SCIPvarGetName(var), lpcandssolcopy[bestcand], bestdown, bestup, bestscore); 623 } 624 else 625 { 626 SCIPdebugMsg(scip, " -> selected from %d new candidates, candidate %d: variable <%s> (down=%g, up=%g, score=%g)\n", 627 counter, bestcand, SCIPvarGetName(var), bestdown, bestup, bestscore); 628 } 629 630 assert(!SCIPisFeasIntegral(scip, SCIPvarGetSol(lpcands[bestcand], TRUE))); 631 632 SCIP_CALL( SCIPbranchVar(scip, var, &downchild, NULL, &upchild) ); 633 assert(downchild != NULL); 634 assert(upchild != NULL); 635 636 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful 637 * for cutting off sub problems and improving lower bounds of children 638 */ 639 exactsolve = SCIPisExactSolve(scip); 640 641 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */ 642 allcolsinlp = SCIPallColsInLP(scip); 643 644 /* update the lower bounds in the children */ 645 if( allcolsinlp && !exactsolve ) 646 { 647 SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) ); 648 SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) ); 649 } 650 SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild)); 651 SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild)); 652 653 *result = SCIP_BRANCHED; 654 } 655 656 TERMINATE: 657 if( branchruledata->useunion && !branchruledata->onlyF2 && SCIPgetDepth(scip) < branchruledata->maxdepthunion ) 658 { 659 SCIPfreeBufferArray(scip, &newlpcandsmax); 660 SCIPfreeBufferArray(scip, &newlpcandsmin); 661 } 662 SCIPfreeBufferArray(scip, &lpcandscopy); 663 SCIPfreeBufferArray(scip, &lpcandssolcopy); 664 SCIPfreeBufferArray(scip, &lpcandsfraccopy); 665 SCIPfreeBufferArray(scip, &lpcandsmax); 666 SCIPfreeBufferArray(scip, &lpcandsmin); 667 668 /* if union usage was not successful enough, disable it */ 669 if( branchruledata->useunion && 670 branchruledata->ntriedunions > 10 && 671 (SCIP_Real)branchruledata->nusefulunions / branchruledata->ntriedunions < branchruledata->minsuccessunion ) 672 { 673 SCIPdebugMsg(scip, "Disabling union usage (not effective)\n"); 674 branchruledata->useunion = FALSE; 675 } 676 677 return SCIP_OKAY; /*lint !e438*/ 678 } 679 680 /* 681 * branching rule specific interface methods 682 */ 683 684 /** creates the cloud branching rule and includes it in SCIP */ 685 SCIP_RETCODE SCIPincludeBranchruleCloud( 686 SCIP* scip /**< SCIP data structure */ 687 ) 688 { 689 SCIP_BRANCHRULEDATA* branchruledata; 690 SCIP_BRANCHRULE* branchrule; 691 692 /* create cloud branching rule data */ 693 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) ); 694 branchruledata->lastcand = 0; 695 branchruledata->skipsize = 0; 696 branchruledata->skipup = NULL; 697 branchruledata->skipdown = NULL; 698 SCIP_CALL( SCIPcreateClock(scip, &(branchruledata->cloudclock)) ); 699 700 /* include branching rule */ 701 branchrule = NULL; 702 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, 703 BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) ); 704 assert(branchrule != NULL); 705 706 /* set non-fundamental callbacks via setter functions */ 707 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeCloud) ); 708 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitCloud) ); 709 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpCloud) ); 710 711 /* add cloud branching rule parameters */ 712 SCIP_CALL( SCIPaddBoolParam(scip, 713 "branching/" BRANCHRULE_NAME "/usecloud", 714 "should a cloud of points be used?", 715 &branchruledata->usecloud, FALSE, DEFAULT_USECLOUD, NULL, NULL) ); 716 SCIP_CALL( SCIPaddBoolParam(scip, 717 "branching/" BRANCHRULE_NAME "/onlyF2", 718 "should only F2 be used?", 719 &branchruledata->onlyF2, FALSE, DEFAULT_ONLYF2, NULL, NULL) ); 720 SCIP_CALL( SCIPaddBoolParam(scip, 721 "branching/" BRANCHRULE_NAME "/useunion", 722 "should the union of candidates be used?", 723 &branchruledata->useunion, FALSE, DEFAULT_USEUNION, NULL, NULL) ); 724 SCIP_CALL( SCIPaddIntParam(scip, 725 "branching/" BRANCHRULE_NAME "/maxpoints", 726 "maximum number of points for the cloud (-1 means no limit)", 727 &branchruledata->maxpoints, FALSE, DEFAULT_MAXPOINTS, -1, INT_MAX, NULL, NULL) ); 728 SCIP_CALL( SCIPaddRealParam(scip, 729 "branching/" BRANCHRULE_NAME "/minsuccessrate", 730 "minimum success rate for the cloud", 731 &branchruledata->minsuccessrate, FALSE, DEFAULT_MINSUCCESSRATE, 0.0, 1.0, NULL, NULL) ); 732 SCIP_CALL( SCIPaddRealParam(scip, 733 "branching/" BRANCHRULE_NAME "/minsuccessunion", 734 "minimum success rate for the union", 735 &branchruledata->minsuccessunion, FALSE, DEFAULT_MINSUCCESSUNION, 0.0, 1.0, NULL, NULL) ); 736 SCIP_CALL( SCIPaddIntParam(scip, 737 "branching/" BRANCHRULE_NAME "/maxdepthunion", 738 "maximum depth for the union", 739 &branchruledata->maxdepthunion, FALSE, DEFAULT_MAXDEPTHUNION, 0, 65000, NULL, NULL) ); 740 741 return SCIP_OKAY; 742 } 743