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 /**@file branch_multaggr.c 25 * @ingroup DEFPLUGINS_BRANCH 26 * @brief fullstrong branching on fractional and multi-aggregated variables 27 * @author Anna Melchiori 28 * @author Gerald Gamrath 29 * 30 * This branching rule uses all fractional binary and integer variables as candidates, 31 * as well as fractional multiaggregated binary and integer variables. Although not 32 * directly contained in the presolved problem anymore, the multi-aggregation provides 33 * an affine linear sum of integer variables, on which branching can be performed. 34 * 35 * For more details, see 36 * G.Gamrath, A.Melchiori, T.Berthold, A.M.Gleixner, D.Salvagnin: Branching on Multi-aggregated Variables 37 * (http://dx.doi.org/10.1007/978-3-319-18008-3_10) 38 */ 39 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 40 41 #include "blockmemshell/memory.h" 42 #include "scip/branch_fullstrong.h" 43 #include "scip/branch_multaggr.h" 44 #include "scip/cons_linear.h" 45 #include "scip/pub_branch.h" 46 #include "scip/pub_cons.h" 47 #include "scip/pub_message.h" 48 #include "scip/pub_tree.h" 49 #include "scip/pub_var.h" 50 #include "scip/scip_branch.h" 51 #include "scip/scip_cons.h" 52 #include "scip/scip_general.h" 53 #include "scip/scip_lp.h" 54 #include "scip/scip_mem.h" 55 #include "scip/scip_message.h" 56 #include "scip/scip_numerics.h" 57 #include "scip/scip_param.h" 58 #include "scip/scip_prob.h" 59 #include "scip/scip_probing.h" 60 #include "scip/scip_solvingstats.h" 61 #include "scip/scip_timing.h" 62 #include "scip/scip_tree.h" 63 #include "scip/scip_var.h" 64 #include "scip/set.h" 65 #include "scip/struct_scip.h" 66 #include "scip/var.h" 67 #include <string.h> 68 69 #define BRANCHRULE_NAME "multaggr" 70 #define BRANCHRULE_DESC "fullstrong branching on fractional and multi-aggregated variables" 71 #define BRANCHRULE_PRIORITY 0 72 #define BRANCHRULE_MAXDEPTH -1 73 #define BRANCHRULE_MAXBOUNDDIST 1.0 74 75 76 #define DEFAULT_REEVALAGE 0LL /**< number of intermediate LPs solved to trigger reevaluation of strong branching 77 * value for a variable that was already evaluated at the current node */ 78 #define DEFAULT_MAXPROPROUNDS 0 /**< maximum number of propagation rounds to be performed during multaggr branching 79 * before solving the LP (-1: no limit, -2: parameter settings) */ 80 #define DEFAULT_PROBINGBOUNDS TRUE /**< should valid bounds be identified in a probing-like fashion during multi-aggr 81 * branching (only with propagation)? */ 82 83 /* 84 * Data structures 85 */ 86 87 /** branching rule data */ 88 struct SCIP_BranchruleData 89 { 90 SCIP_Longint reevalage; /**< number of intermediate LPs solved to trigger reevaluation of strong branching 91 * value for a variable that was already evaluated at the current node */ 92 SCIP_Bool probingbounds; /**< should valid bounds be identified in a probing-like fashion during strong 93 * branching (only with propagation)? */ 94 int lastcand; /**< last evaluated candidate of last branching rule execution */ 95 int maxproprounds; /**< maximum number of propagation rounds to be performed during strong branching 96 * before solving the LP (-1: no limit, -2: parameter settings) */ 97 int skipsize; /**< size of skipdown and skipup array */ 98 SCIP_Bool* skipdown; /**< should be branching on down child be skipped? */ 99 SCIP_Bool* skipup; /**< should be branching on up child be skipped? */ 100 #ifdef SCIP_STATISTIC 101 SCIP_CLOCK* clckstrongbr; /**< clock to store the time spent inside the strong branching function on fractional variables */ 102 SCIP_CLOCK* clckmultaggrbr; /**< clock to store the time spent inside the strong branching function on multi-aggragated variables */ 103 SCIP_Real* ratioggain; /**< for each occurence of a branching on a multi-aggregated variable we store the ratio of the gain that 104 * we would have obtained branching on the best fractional variable over the gain obtained 105 * branching on the current multi-aggregated variable */ 106 SCIP_Real ameanratio; /**< arithmetic mean of the ratioggain array */ 107 SCIP_Bool noupdate; /**< pointer to store if the probing LP has not been solved so we do not want to 108 * update statistics */ 109 int firstmultaggrdepth; /**< depth of the first branching on a multi-aggregated variable */ 110 int rundepth; /**< the run of the first multi-aggregated branching */ 111 int nmultaggrbranch; /**< number of branchings on multi-aggregated variables */ 112 int nfracbranch; /**< number of branchings on fractional variables */ 113 int nEscore; /**< number of times that the bestscore over all multi-aggregated variables is equal to the best 114 * fractional variables score and thus we do not branch on the multi-aggregate variable */ 115 int nmultaggrcutoff; /**< number of cutoffs detected during the probing mode on multi-aggregated variables */ 116 int nmultaggrconsadd; /**< number of times that a probing constraint of a multi-aggregated variable has been 117 * added to the original problem */ 118 int nfractcutoff; /**< number of cutoffs detected during strong branching on fractional variables */ 119 int nfractconsadd; /**< number of times that during strong branching on fractional variables a constraint has been 120 * added to the original problem or a variables domain has been reduced */ 121 int nmultaggrvars; /**< number of multi-aggregated variables in the problem of the last run */ 122 int nrun; /**< number of restarts */ 123 int size; /**< size of the provided array to store the ratio gain */ 124 int nstrongbrcall; /**< number of times that the selectVarstrongBranching function has been called */ 125 int nmultaggrbrcall; /**< number of times that the selectVarMultAggrBranching function has been called */ 126 int totallpcands; /**< total number of observed lpcands over all selectVarstrongBranching function calls */ 127 int totalmultaggrcands; /**< total number of observed multi-aggregregated candidates over all selectVarMultAggrBranching 128 * function calls */ 129 #endif 130 }; 131 132 133 /* 134 * Local methods 135 */ 136 137 /* this function ensures that the allocated memory is enough to store statistics data */ 138 #ifdef SCIP_STATISTIC 139 static 140 SCIP_RETCODE ensureArraySize( 141 SCIP* scip, /**< original SCIP data structure */ 142 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */ 143 ) 144 { 145 assert(scip != NULL); 146 assert(branchruledata != NULL); 147 assert(branchruledata->ratioggain != NULL); 148 assert(branchruledata->nmultaggrbranch >= 0); 149 assert(branchruledata->size >= 0); 150 151 /* check whether the size of the array is big enough; reallocate memory if needed */ 152 if( branchruledata->nmultaggrbranch + 1 > branchruledata->size ) 153 { 154 int newsize = SCIPcalcMemGrowSize(scip, branchruledata->nmultaggrbranch + 1); 155 assert(newsize >= branchruledata->nmultaggrbranch + 1); 156 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->ratioggain, branchruledata->size, newsize) ); 157 branchruledata->size = newsize; 158 } 159 return SCIP_OKAY; 160 } 161 #endif 162 163 /* this function gives us the best candidate for branching among the multi-aggregated variables of the problem 164 * and the best fractional integer variable already selected by strong branching 165 */ 166 static 167 SCIP_RETCODE selectVarMultAggrBranching( 168 SCIP* scip, /**< original SCIP data structure */ 169 SCIP_VAR** bestcand, /**< the best candidate variable selected by strong branching */ 170 SCIP_Real* bestscore, /**< score of the best branching candidate */ 171 SCIP_Real* bestsol, /**< solution value of the best branching candidate */ 172 SCIP_Real* bestdown, /**< objective value of the down node when branching on bestcand */ 173 SCIP_Real* bestup, /**< objective value of the up node when branching on bestcand */ 174 SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */ 175 SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */ 176 SCIP_Real* provedbound, /**< proved dual bound for the current subtree */ 177 SCIP_Real* estimatedown, /**< pointer to store the down child nodes estimate */ 178 SCIP_Real* estimateup, /**< pointer to store the up child nodes estimate */ 179 #ifdef SCIP_STATISTIC 180 SCIP_Real* bestmultaggrscore, /**< pointer to store the multi aggregated score */ 181 #endif 182 SCIP_RESULT* result /**< pointer to store results of branching */ 183 ) 184 { 185 SCIP_VAR** fixvars; 186 SCIP_CONS* probingconsdown; 187 SCIP_CONS* probingconsup; 188 SCIP_NODE* node; 189 SCIP_Real* fixvarssols; 190 SCIP_Real fixvarssol; 191 SCIP_Real lpobjval; 192 SCIP_Bool exactsolve; 193 SCIP_Bool allcolsinlp; 194 SCIP_Bool downnodeinf = FALSE; 195 SCIP_Bool startprobing = TRUE; 196 SCIP_Bool endprobing = FALSE; 197 int nfixvars; 198 int i; 199 int j; 200 int k; 201 202 /* import branchrule data for statistics */ 203 #ifdef SCIP_STATISTIC 204 SCIP_BRANCHRULE* branchrule; 205 SCIP_BRANCHRULEDATA* branchruledata; 206 207 branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME); 208 assert(branchrule != NULL); 209 210 branchruledata = SCIPbranchruleGetData(branchrule); 211 assert(branchruledata != NULL); 212 #endif 213 214 assert(scip != NULL); 215 assert(bestcand != NULL); 216 assert(bestscore != NULL); 217 218 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful 219 * for cutting off sub problems and improving lower bounds of children 220 */ 221 exactsolve = SCIPisExactSolve(scip); 222 223 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */ 224 allcolsinlp = SCIPallColsInLP(scip); 225 226 /* get fixed variables */ 227 fixvars = SCIPgetFixedVars(scip); 228 nfixvars = SCIPgetNFixedVars(scip); 229 SCIPdebugMsg(scip, " fractional variable: <%s> with value: %f is selected by strong branching\n", SCIPvarGetName(*bestcand), *bestsol); 230 231 /* check if we would exceed the depth limit */ 232 if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) ) 233 { 234 SCIPdebugMsg(scip, "cannot perform probing in selectVarMultAggrBranching, depth limit reached.\n"); 235 *result = SCIP_DIDNOTRUN; 236 return SCIP_OKAY; 237 } 238 239 if( nfixvars != 0 ) 240 { 241 assert(fixvars != NULL); 242 243 SCIP_CALL( SCIPallocBufferArray(scip, &fixvarssols, nfixvars) ); 244 lpobjval = SCIPgetLPObjval(scip); 245 246 /* store the values of the fixed variables at the current optimal solution */ 247 for( i = 0; i < nfixvars; i++ ) 248 { 249 assert(fixvars[i] != NULL); 250 fixvarssols[i] = SCIPvarGetLPSol(fixvars[i]); 251 } 252 253 for( i = 0; i < nfixvars; i++ ) 254 { 255 assert(fixvars[i] != NULL); 256 257 /* only integer and binary multi-aggregated variables are potential branching candidates */ 258 if( SCIPvarGetStatus(fixvars[i]) == SCIP_VARSTATUS_MULTAGGR && (SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_INTEGER || 259 SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_BINARY) ) 260 { 261 fixvarssol = fixvarssols[i]; 262 263 /* start probing mode for the fractional multi-aggregated variable */ 264 if( !SCIPisFeasIntegral(scip, fixvarssol) ) 265 { 266 SCIP_VAR** downvars = NULL; 267 SCIP_VAR** upvars = NULL; 268 SCIP_Real* downvarssols = NULL; 269 SCIP_Real* upvarssols = NULL; 270 SCIP_LPSOLSTAT solstatdown; 271 SCIP_LPSOLSTAT solstatup; 272 SCIP_Real downobjval; 273 SCIP_Real upobjval; 274 SCIP_Real estimateprobdown = 0.0; 275 SCIP_Real estimateprobup = 0.0; 276 SCIP_Bool downinf; 277 SCIP_Bool upinf; 278 SCIP_Bool lperror; 279 int ndownvars; 280 int nupvars; 281 282 /* start the probing mode if this is the first entrance */ 283 if( startprobing ) 284 { 285 SCIP_CALL( SCIPstartProbing(scip) ); 286 startprobing = FALSE; 287 endprobing = TRUE; 288 289 SCIPdebugMsg(scip, "PROBING MODE:\n"); 290 } 291 292 SCIPdebugMsg(scip, " multi-aggregated variable: <%s> with value: %f\n", SCIPvarGetName(fixvars[i]), fixvarssol); 293 294 SCIPstatistic(branchruledata->totalmultaggrcands += 1); 295 296 /* create the multi-aggregated rounded down constraint */ 297 SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsdown, "probingconsdown", SCIPvarGetMultaggrNVars(fixvars[i]), 298 SCIPvarGetMultaggrVars(fixvars[i]), SCIPvarGetMultaggrScalars(fixvars[i]), -SCIPinfinity(scip), 299 SCIPfeasFloor(scip, fixvarssol) - SCIPvarGetMultaggrConstant(fixvars[i]), TRUE, TRUE, FALSE, FALSE, 300 TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) ); 301 assert(probingconsdown != NULL); 302 303 /* create the down child probing node */ 304 SCIP_CALL( SCIPnewProbingNode(scip) ); 305 node = SCIPgetCurrentNode(scip); 306 assert(node != NULL); 307 308 SCIP_CALL( SCIPaddConsNode(scip, node, probingconsdown, NULL) ); 309 SCIP_CALL( SCIPreleaseCons(scip, &probingconsdown) ); 310 311 #ifdef PRINTNODECONS 312 SCIPdebugMsg(scip, " created down probing node with constraint:\n"); 313 SCIP_CALL( SCIPprintCons(scip, probingconsdown, NULL) ); 314 SCIPinfoMessage(scip, NULL, "\n"); 315 #endif 316 317 /* solve the down child probing node */ 318 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &downinf) ); 319 solstatdown = SCIPgetLPSolstat(scip); 320 lperror = lperror || (solstatdown == SCIP_LPSOLSTAT_NOTSOLVED && downinf == 0) || (solstatdown == SCIP_LPSOLSTAT_ITERLIMIT) || 321 (solstatdown == SCIP_LPSOLSTAT_TIMELIMIT); 322 assert(solstatdown != SCIP_LPSOLSTAT_UNBOUNDEDRAY); 323 324 /* break the branching rule if an error occurred, problem was not solved, iteration or time limit was reached */ 325 if( lperror ) 326 { 327 SCIPdebugMsg(scip, "error solving down node probing LP: status=%d\n", solstatdown); 328 SCIPstatistic(branchruledata->noupdate = TRUE); 329 break; 330 } 331 332 downobjval = SCIPgetLPObjval(scip); 333 downinf = downinf || SCIPisGE(scip, downobjval, SCIPgetCutoffbound(scip)); 334 assert(((solstatdown != SCIP_LPSOLSTAT_INFEASIBLE) && (solstatdown != SCIP_LPSOLSTAT_OBJLIMIT)) || downinf); 335 336 if( !downinf ) 337 { 338 /* when an optimal solution has been found calculate down child's estimate based on pseudo costs */ 339 /* estimate = lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) */ 340 estimateprobdown = SCIPnodeGetLowerbound(node); 341 SCIP_CALL( SCIPgetLPBranchCands(scip, &downvars, &downvarssols, NULL, &ndownvars, NULL, NULL) ); 342 343 for( j = 0 ; j < ndownvars; j++ ) 344 { 345 SCIP_Real estimateincr; 346 SCIP_Real pscdown; 347 SCIP_Real pscup; 348 349 assert(downvars != NULL); 350 assert(downvars[j] != NULL); 351 352 pscdown = SCIPvarGetPseudocost(downvars[j], scip->stat, SCIPsetFeasFloor(scip->set, downvarssols[j]) - downvarssols[j]); 353 pscup = SCIPvarGetPseudocost(downvars[j], scip->stat, SCIPsetFeasCeil(scip->set, downvarssols[j]) - downvarssols[j]); 354 estimateincr = MIN(pscdown, pscup); 355 356 estimateprobdown += estimateincr; 357 } 358 } 359 SCIP_CALL( SCIPbacktrackProbing(scip, 0) ); 360 361 /* create the multi-aggregated rounded up constraint */ 362 SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsup, "probingconsup", SCIPvarGetMultaggrNVars(fixvars[i]), SCIPvarGetMultaggrVars(fixvars[i]), 363 SCIPvarGetMultaggrScalars(fixvars[i]), SCIPfeasCeil(scip, fixvarssol) - SCIPvarGetMultaggrConstant(fixvars[i]), SCIPinfinity(scip), 364 TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) ); 365 assert(probingconsup != NULL); 366 367 /* create the up child probing node */ 368 SCIP_CALL( SCIPnewProbingNode(scip) ); 369 node = SCIPgetCurrentNode(scip); 370 371 SCIP_CALL( SCIPaddConsNode(scip, node, probingconsup, NULL) ); 372 SCIP_CALL( SCIPreleaseCons(scip, &probingconsup) ); 373 374 #ifdef PRINTNODECONS 375 SCIPdebugMsg(scip, " created up probing node with constraint:\n"); 376 SCIP_CALL( SCIPprintCons(scip, probingconsup, NULL) ); 377 SCIPinfoMessage(scip, NULL, "\n"); 378 #endif 379 /* solve the up child probing node */ 380 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, &upinf) ); 381 solstatup = SCIPgetLPSolstat(scip); 382 lperror = lperror || (solstatup == SCIP_LPSOLSTAT_NOTSOLVED && upinf == 0) || (solstatup == SCIP_LPSOLSTAT_ITERLIMIT) || 383 (solstatup == SCIP_LPSOLSTAT_TIMELIMIT); 384 assert(solstatup != SCIP_LPSOLSTAT_UNBOUNDEDRAY); 385 386 /* break the branching rule if an error occurred, problem was not solved, iteration or time limit was reached */ 387 if( lperror ) 388 { 389 SCIPdebugMsg(scip, "error solving up node probing LP: status=%d\n", solstatup); 390 SCIPstatistic(branchruledata->noupdate = TRUE); 391 break; 392 } 393 394 upobjval = SCIPgetLPObjval(scip); 395 upinf = upinf || SCIPisGE(scip, upobjval, SCIPgetCutoffbound(scip)); 396 assert(((solstatup != SCIP_LPSOLSTAT_INFEASIBLE) && (solstatup != SCIP_LPSOLSTAT_OBJLIMIT)) || upinf); 397 398 SCIPdebugMsg(scip, " down node objval: %g up node objval: %g\n", downobjval, upobjval); 399 400 if( !upinf ) 401 { 402 /* when an optimal solution has been found calculate up child's estimate based on pseudo costs */ 403 /* estimate = lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) */ 404 estimateprobup = SCIPnodeGetLowerbound(node); 405 SCIP_CALL( SCIPgetLPBranchCands(scip, &upvars, &upvarssols, NULL, &nupvars, NULL, NULL) ); 406 407 for( k = 0 ; k < nupvars; k++ ) 408 { 409 SCIP_Real estimateincr; 410 SCIP_Real pscdown; 411 SCIP_Real pscup; 412 413 assert(upvars != NULL); 414 assert(upvars[k] != NULL); 415 416 pscdown = SCIPvarGetPseudocost(upvars[k], scip->stat, SCIPsetFeasFloor(scip->set, upvarssols[k]) - upvarssols[k]); 417 pscup = SCIPvarGetPseudocost(upvars[k], scip->stat, SCIPsetFeasCeil(scip->set, upvarssols[k]) - upvarssols[k]); 418 estimateincr = MIN(pscdown, pscup); 419 estimateprobup += estimateincr; 420 } 421 } 422 SCIP_CALL( SCIPbacktrackProbing(scip, 0) ); 423 424 /* check whether the children nodes are solved to optimality and give a valid new lower bound or not */ 425 if( downinf || upinf ) 426 { 427 /* check if the LP is a valid relaxation and we can then collect new information */ 428 if( allcolsinlp ) 429 { 430 /* cut off the node either when both children are infeasible or the objective limit was reached; 431 * if only one child is feasible with LP value smaller than objective limit, add the corresponding 432 * constraint to the problem and break the branching rule in order to solve the updated LP 433 */ 434 if( downinf && upinf ) 435 { 436 SCIPdebugMsg(scip, "node can be cut off due to strong branching on multi-aggregated variable <%s>\n", 437 SCIPvarGetName(fixvars[i])); 438 SCIPstatistic(branchruledata->nmultaggrcutoff += 1); 439 440 *result = SCIP_CUTOFF; 441 break; 442 } 443 else 444 { 445 assert(!lperror); 446 447 if( downinf ) 448 downnodeinf = TRUE; 449 450 SCIPdebugMsg(scip, "%s child of multi-aggregated variable <%s> is infeasible\n", 451 downinf ? "down" : "up", SCIPvarGetName(fixvars[i]) ); 452 SCIPstatistic(branchruledata->nmultaggrconsadd += 1); 453 454 *result = SCIP_CONSADDED; 455 break; 456 } 457 } 458 } 459 else 460 { 461 /* if both children are solved to optimality and they both give a new valid bound, calculate the score of the 462 * multi-aggregated variable 463 */ 464 SCIP_Real downgain; 465 SCIP_Real upgain; 466 SCIP_Real down; 467 SCIP_Real up; 468 SCIP_Real score; 469 SCIP_Real minbound; 470 471 assert(!downinf); 472 assert(!upinf); 473 assert(!lperror); 474 475 SCIPdebugMsg(scip, " both probing nodes are valid while branching on multi-aggregated variable: <%s>\n ", SCIPvarGetName(fixvars[i])); 476 477 down = MAX(downobjval, lpobjval); 478 up = MAX(upobjval, lpobjval); 479 downgain = down - lpobjval; 480 upgain = up - lpobjval; 481 score = SCIPgetBranchScore(scip, NULL, downgain, upgain); 482 483 if( allcolsinlp && !exactsolve ) 484 { 485 /* the minimal lower bound of both children is a proved lower bound of the current subtree */ 486 minbound = MIN(downobjval, upobjval); 487 *provedbound = MAX(*provedbound, minbound); 488 } 489 490 SCIPstatistic( 491 if( score > *bestmultaggrscore ) 492 *bestmultaggrscore = score; 493 ); 494 495 /* update the best branching candidate and all its values if a strictly greater score has been found */ 496 if( score > *bestscore ) 497 { 498 SCIPstatistic( 499 if( branchruledata->nmultaggrbranch == 0 ) 500 { 501 branchruledata->rundepth = SCIPgetNRuns(scip); 502 branchruledata->firstmultaggrdepth = SCIPgetFocusDepth(scip); 503 } 504 ) 505 506 SCIPdebugMsg(scip, " <%s> is a better candidate for branching\n", SCIPvarGetName(fixvars[i])); 507 508 *bestscore = MAX(score, *bestscore); 509 *bestcand = fixvars[i]; 510 *bestsol = fixvarssol; 511 *bestdown = downobjval; 512 *bestup = upobjval; 513 *bestdownvalid = TRUE; 514 *bestupvalid = TRUE; 515 *estimatedown = estimateprobdown; 516 *estimateup = estimateprobup; 517 } 518 assert(bestscore != NULL); 519 assert(bestcand != NULL); 520 assert(bestup != NULL); 521 assert(bestdown != NULL); 522 } 523 } 524 } 525 } 526 527 /* end probing mode */ 528 if( endprobing ) 529 { 530 SCIP_CALL( SCIPendProbing(scip) ); 531 } 532 533 SCIPdebugMsg(scip, "\n"); 534 535 /* one of the child nodes was infeasible, add the other constraint to the current node */ 536 if( *result == SCIP_CONSADDED ) 537 { 538 node = SCIPgetCurrentNode(scip); 539 if( downnodeinf ) 540 { 541 SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsup, "infconsup", SCIPvarGetMultaggrNVars(fixvars[i]), 542 SCIPvarGetMultaggrVars(fixvars[i]), SCIPvarGetMultaggrScalars(fixvars[i]), 543 SCIPfeasCeil(scip, fixvarssols[i]) - SCIPvarGetMultaggrConstant(fixvars[i]), SCIPinfinity(scip), 544 TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) ); 545 assert(probingconsup != NULL); 546 SCIP_CALL( SCIPaddConsNode(scip, node, probingconsup, NULL) ); 547 SCIPdebugMsg(scip, " <%s> new valid constraint has been added to the original problem\n", SCIPconsGetName(probingconsup)); 548 SCIP_CALL( SCIPreleaseCons(scip, &probingconsup) ); 549 } 550 else 551 { 552 SCIP_CALL( SCIPcreateConsLinear(scip, &probingconsdown, "infconsdown", SCIPvarGetMultaggrNVars(fixvars[i]), 553 SCIPvarGetMultaggrVars(fixvars[i]), SCIPvarGetMultaggrScalars(fixvars[i]), - SCIPinfinity(scip), 554 SCIPfeasFloor(scip, fixvarssols[i]) - SCIPvarGetMultaggrConstant(fixvars[i]), TRUE, TRUE, FALSE, FALSE, 555 TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) ); 556 assert(probingconsdown != NULL); 557 SCIP_CALL( SCIPaddConsNode(scip, node, probingconsdown, NULL) ); 558 SCIPdebugMsg(scip, " <%s> new valid constraint has been added to the original problem\n", SCIPconsGetName(probingconsdown)); 559 SCIP_CALL( SCIPreleaseCons(scip, &probingconsdown) ); 560 } 561 } 562 SCIPfreeBufferArray(scip, &fixvarssols); 563 } 564 return SCIP_OKAY; 565 } 566 567 568 /* 569 * Callback methods of branching rule 570 */ 571 572 /** copy method for branchrule plugins (called when SCIP copies plugins) */ 573 static 574 SCIP_DECL_BRANCHCOPY(branchCopyMultAggr) 575 { /*lint --e{715}*/ 576 assert(scip != NULL); 577 assert(branchrule != NULL); 578 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 579 580 /* call inclusion method of branchrule */ 581 SCIP_CALL( SCIPincludeBranchruleMultAggr(scip) ) ; 582 583 return SCIP_OKAY; 584 } 585 586 /** destructor of branching rule to free user data (called when SCIP is exiting) */ 587 static 588 SCIP_DECL_BRANCHFREE(branchFreeMultAggr) 589 { /*lint --e{715}*/ 590 SCIP_BRANCHRULEDATA* branchruledata; 591 592 /* free branching rule data */ 593 branchruledata = SCIPbranchruleGetData(branchrule); 594 assert(branchruledata != NULL); 595 596 SCIPstatistic(SCIPfreeBlockMemoryArrayNull(scip , &branchruledata->ratioggain, branchruledata->size)); 597 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize); 598 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize); 599 600 SCIPfreeBlockMemory(scip, &branchruledata); 601 SCIPbranchruleSetData(branchrule, NULL); 602 603 return SCIP_OKAY; 604 } 605 606 /** initialization method of branching rule (called after problem was transformed) */ 607 static 608 SCIP_DECL_BRANCHINIT(branchInitMultAggr) 609 { /*lint --e{715}*/ 610 SCIP_BRANCHRULEDATA* branchruledata; 611 612 branchruledata = SCIPbranchruleGetData(branchrule); 613 assert(branchruledata != NULL); 614 615 branchruledata->lastcand = 0; 616 SCIPstatistic( 617 branchruledata->firstmultaggrdepth = 0; 618 branchruledata->nmultaggrbranch = 0; 619 branchruledata->nfracbranch = 0; 620 branchruledata->nEscore = 0; 621 branchruledata->nmultaggrcutoff = 0; 622 branchruledata->nmultaggrconsadd = 0; 623 branchruledata->nfractcutoff = 0; 624 branchruledata->nfractconsadd = 0; 625 branchruledata->nrun = 0; 626 branchruledata->size = 100; 627 branchruledata->ameanratio = 0.0; 628 branchruledata->noupdate = FALSE; 629 branchruledata->clckstrongbr = NULL; 630 branchruledata->clckmultaggrbr = NULL; 631 branchruledata->nstrongbrcall = 0; 632 branchruledata->nmultaggrbrcall = 0; 633 branchruledata->totalmultaggrcands = 0; 634 branchruledata->totallpcands = 0; 635 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->ratioggain, branchruledata->size) ); 636 BMSclearMemoryArray(branchruledata->ratioggain, branchruledata->size); 637 SCIP_CALL( SCIPcreateClock(scip, &branchruledata->clckstrongbr) ); 638 SCIP_CALL( SCIPcreateClock(scip, &branchruledata->clckmultaggrbr) ); 639 ) 640 return SCIP_OKAY; 641 } 642 643 /** deinitialization method of branching rule (called before transformed problem is freed) */ 644 static 645 SCIP_DECL_BRANCHEXIT(branchExitMultAggr) 646 { /*lint --e{715}*/ 647 SCIP_BRANCHRULEDATA* branchruledata; 648 SCIPstatistic(int j = 0); 649 650 /* initialize branching rule data */ 651 branchruledata = SCIPbranchruleGetData(branchrule); 652 assert(branchruledata != NULL); 653 assert((branchruledata->skipdown != NULL) == (branchruledata->skipup != NULL)); 654 655 /* print statistics */ 656 SCIPstatistic( 657 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n"); 658 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Multi-aggregated branching stats : \n"); 659 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrvars : %d (last run)\n", 660 branchruledata->nmultaggrvars); 661 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " firstmultaggrbranchdepth : %d (in run %d)\n", 662 branchruledata->firstmultaggrdepth, 663 branchruledata->rundepth); 664 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrbranch : %d (tot %d)\n", 665 branchruledata->nmultaggrbranch, branchruledata->nmultaggrbranch + branchruledata->nfracbranch); 666 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrcutoff : %d\n", branchruledata->nmultaggrcutoff); 667 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrconsadd : %d\n", branchruledata->nmultaggrconsadd); 668 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nfractcutoff : %d\n", branchruledata->nfractcutoff); 669 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nfractconsadd : %d\n", branchruledata->nfractconsadd); 670 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nEscore : %d\n", branchruledata->nEscore); 671 672 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Branching Time : \n"); 673 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nstrongbrcall : %d\n", branchruledata->nstrongbrcall); 674 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " totalstrongbrtime : %g\n", 675 SCIPgetClockTime(scip, branchruledata->clckstrongbr)); 676 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " totallpcands : %d\n", branchruledata->totallpcands); 677 678 if( branchruledata->totallpcands != 0 ) 679 { 680 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " averagetimestrongbr : %g\n", 681 SCIPgetClockTime(scip, branchruledata->clckstrongbr) / branchruledata->totallpcands); 682 } 683 else 684 { 685 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " averagetimestrongbr : %s\n", "--"); 686 } 687 688 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " nmultaggrbrcall : %d\n", branchruledata->nmultaggrbrcall); 689 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " totalmultaggrbrtime : %g\n", 690 SCIPgetClockTime(scip, branchruledata->clckmultaggrbr)); 691 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " totalmultaggrcands : %d\n", branchruledata->totalmultaggrcands); 692 693 if( branchruledata->totalmultaggrcands != 0 ) 694 { 695 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " averagetimemultaggrbr : %g\n", 696 SCIPgetClockTime(scip, branchruledata->clckmultaggrbr) / branchruledata->totalmultaggrcands); 697 } 698 else 699 { 700 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " averagetimemultaggrbr : %s\n", "--"); 701 } 702 703 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Ratioggain :\n"); 704 if( branchruledata->nmultaggrbranch != 0 ) 705 { 706 for( j = 0; j < branchruledata->nmultaggrbranch; j++ ) 707 { 708 branchruledata->ameanratio += branchruledata->ratioggain[j]; 709 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " %g", branchruledata->ratioggain[j]); 710 } 711 712 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n"); 713 branchruledata->ameanratio = branchruledata->ameanratio / branchruledata->nmultaggrbranch; 714 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n"); 715 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " ameanratio : %4.2f\n", branchruledata->ameanratio); 716 } 717 else 718 { 719 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " ameanratio : %s\n", "--"); 720 } 721 722 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n"); 723 724 /* free arrays */ 725 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->ratioggain, branchruledata->size); 726 SCIP_CALL( SCIPfreeClock(scip, &branchruledata->clckstrongbr) ); 727 SCIP_CALL( SCIPfreeClock(scip, &branchruledata->clckmultaggrbr) ); 728 ) 729 if( branchruledata->skipdown != NULL ) 730 { 731 SCIPfreeBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize); 732 SCIPfreeBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize); 733 branchruledata->skipdown = NULL; 734 branchruledata->skipup = NULL; 735 branchruledata->skipsize = 0; 736 } 737 return SCIP_OKAY; 738 } 739 740 /** branching execution method for fractional LP solutions */ 741 static 742 SCIP_DECL_BRANCHEXECLP(branchExeclpMultAggr) 743 { /*lint --e{715}*/ 744 SCIP_BRANCHRULEDATA* branchruledata; 745 SCIP_VAR** lpcands; 746 SCIP_VAR** tmplpcands; 747 SCIP_Real* lpcandssol; 748 SCIP_Real* lpcandsfrac; 749 SCIP_Real* tmplpcandssol; 750 SCIP_Real* tmplpcandsfrac; 751 SCIP_NODE* downchild; 752 SCIP_NODE* upchild; 753 SCIP_Real bestup; 754 SCIP_Real bestdown; 755 SCIP_Real bestscore; 756 SCIP_Real provedbound; 757 SCIP_Real estimatedown = 0.0; 758 SCIP_Real estimateup = 0.0; 759 SCIP_Bool bestdownvalid; 760 SCIP_Bool bestupvalid; 761 SCIP_Longint oldreevalage; 762 int bestcandpos; 763 int nlpcands; 764 int npriolpcands; 765 SCIPstatistic( 766 SCIP_Real lpobjval; 767 SCIP_Bool reoptimize; 768 ) 769 770 assert(branchrule != NULL); 771 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 772 assert(scip != NULL); 773 assert(result != NULL); 774 775 SCIPdebugMsg(scip, "Execlp method of mult-aggreg branching\n "); 776 *result = SCIP_DIDNOTRUN; 777 778 /* get branching rule data */ 779 branchruledata = SCIPbranchruleGetData(branchrule); 780 assert(branchruledata != NULL); 781 782 SCIP_CALL( SCIPgetLongintParam(scip, "branching/fullstrong/reevalage", &oldreevalage) ); 783 SCIP_CALL( SCIPsetLongintParam(scip, "branching/fullstrong/reevalage", branchruledata->reevalage) ); 784 785 /* get the lpobjval and the number of multi aggregated variables of the problem as a statistic counter */ 786 SCIPstatistic( 787 reoptimize = FALSE; 788 lpobjval = SCIPgetLPObjval(scip); 789 790 if( SCIPgetNRuns(scip) != branchruledata->nrun ) 791 { 792 SCIP_VAR** fixvars; 793 int nfixvars; 794 int i; 795 796 branchruledata->nmultaggrvars = 0; 797 fixvars = SCIPgetFixedVars(scip); 798 nfixvars = SCIPgetNFixedVars(scip); 799 800 if( nfixvars != 0 ) 801 { 802 for( i = 0; i < nfixvars; i++ ) 803 { 804 if( SCIPvarGetStatus(fixvars[i]) == SCIP_VARSTATUS_MULTAGGR && (SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_INTEGER || 805 SCIPvarGetType(fixvars[i]) == SCIP_VARTYPE_BINARY) ) 806 { 807 branchruledata->nmultaggrvars += 1; 808 } 809 } 810 } 811 branchruledata->nrun = SCIPgetNRuns(scip); 812 } 813 ) 814 815 /* get all branching candidates */ 816 SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, &nlpcands, &npriolpcands, NULL) ); 817 assert(nlpcands > 0); 818 assert(npriolpcands > 0); 819 820 /* copy LP branching candidates and solution values, because they will be updated w.r.t. the strong branching LP 821 * solution 822 */ 823 SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) ); 824 SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) ); 825 SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) ); 826 827 if( branchruledata->skipdown == NULL ) 828 { 829 assert(branchruledata->skipup == NULL); 830 831 branchruledata->skipsize = SCIPgetNVars(scip); 832 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) ); 833 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) ); 834 BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize); 835 BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize); 836 } 837 838 /* start the clock to get the time spent inside the function */ 839 SCIPstatistic( 840 SCIP_CALL( SCIPstartClock(scip, branchruledata->clckstrongbr) ); 841 ); 842 843 /* compute strong branching among the array of fractional variables in order to get the best one */ 844 SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcands, lpcandssol, lpcandsfrac, branchruledata->skipdown, 845 branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand, 846 branchruledata->maxproprounds, branchruledata->probingbounds, TRUE, 847 &bestcandpos, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) ); 848 849 SCIPstatistic( 850 SCIP_CALL( SCIPstopClock(scip, branchruledata->clckstrongbr) ); 851 branchruledata->totallpcands += SCIPgetNLPBranchCands(scip); 852 branchruledata->nstrongbrcall += 1; 853 ) 854 855 if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED ) 856 { 857 SCIP_VAR* bestcand = lpcands[bestcandpos]; 858 SCIP_Real bestsol = lpcandssol[bestcandpos]; 859 SCIPstatistic( SCIP_Real bestmultaggrscore = -SCIPinfinity(scip); ) 860 861 SCIPstatistic( 862 SCIP_Real fdowngain = 0.0; 863 SCIP_Real fupgain = 0.0; 864 865 /* reoptimize is set to true if strong branching on fractional variables did not explicitly evaluate the objective 866 * values of the probing child nodes and thus we do not have updated information 867 */ 868 if( SCIPisLT(scip, SCIPgetVarStrongbranchLPAge(scip, bestcand), branchruledata->reevalage) 869 || branchruledata->maxproprounds != 0 ) 870 reoptimize = TRUE; 871 872 /* store values needed for the ratioggain statistic */ 873 if( !reoptimize ) 874 { 875 SCIP_Real fdown; 876 SCIP_Real fup; 877 878 fdown = MAX(bestdown, lpobjval); 879 fup = MAX(bestup, lpobjval); 880 fdowngain = fdown - lpobjval; 881 fupgain = fup - lpobjval; 882 } 883 884 /* start and then stop the clock to get the time spent inside the function */ 885 SCIP_CALL( SCIPstartClock(scip, branchruledata->clckmultaggrbr) ); 886 ) 887 888 /* compute strong branching among the multi-aggregated variables and the best fractional variable */ 889 #ifdef SCIP_STATISTIC 890 SCIP_CALL( selectVarMultAggrBranching(scip, &bestcand, &bestscore, &bestsol, &bestdown, &bestup, &bestdownvalid, &bestupvalid, &provedbound, 891 &estimatedown, &estimateup, &bestmultaggrscore, result) ); 892 #else 893 SCIP_CALL( selectVarMultAggrBranching(scip, &bestcand, &bestscore, &bestsol, &bestdown, &bestup, &bestdownvalid, &bestupvalid, &provedbound, 894 &estimatedown, &estimateup, result) ); 895 #endif 896 SCIPstatistic( 897 SCIP_CALL( SCIPstopClock(scip, branchruledata->clckmultaggrbr) ); 898 branchruledata->nmultaggrbrcall += 1; 899 ) 900 901 if( *result != SCIP_CUTOFF && *result != SCIP_CONSADDED ) 902 { 903 SCIPstatistic( 904 if( !(branchruledata->noupdate) ) 905 { 906 if( SCIPisEQ(scip, bestmultaggrscore, bestscore) ) 907 branchruledata->nEscore += 1; 908 } 909 ) 910 911 assert(bestcand != NULL); 912 SCIPdebugMsg(scip, "BRANCHING MODE:\n"); 913 914 /* perform branching on the best found candidate */ 915 if( SCIPvarGetStatus(bestcand) == SCIP_VARSTATUS_MULTAGGR ) 916 { 917 SCIP_CONS* multaggrconsdown; 918 SCIP_CONS* multaggrconsup; 919 920 SCIPstatistic( 921 if( !(branchruledata->noupdate) ) 922 { 923 branchruledata->nmultaggrbranch += 1; 924 925 if( !reoptimize ) 926 { 927 SCIP_Real gfractbranch; 928 SCIP_Real gmultaggrbranch; 929 SCIP_Real downgain; 930 SCIP_Real upgain; 931 SCIP_Real down; 932 SCIP_Real up; 933 int nmultaggrbranch; 934 935 down = MAX(bestdown, lpobjval); 936 up = MAX(bestup, lpobjval); 937 downgain = down - lpobjval; 938 upgain = up - lpobjval; 939 940 SCIP_CALL( ensureArraySize(scip, branchruledata) ); 941 942 gfractbranch= SQRT(MAX(fdowngain,1e-06) * MAX(fupgain,1e-06)); 943 gmultaggrbranch = SQRT(MAX(downgain,1e-06) * MAX(upgain,1e-06)); 944 945 nmultaggrbranch = branchruledata->nmultaggrbranch; 946 947 if( gmultaggrbranch == 0.0 ) 948 { 949 branchruledata->ratioggain[nmultaggrbranch - 1] = 1; 950 } 951 else 952 { 953 branchruledata->ratioggain[nmultaggrbranch - 1] = gfractbranch / gmultaggrbranch; 954 } 955 } 956 } 957 ) 958 959 /* create the multi-aggregated constraints rounded up and down */ 960 SCIP_CALL( SCIPcreateConsLinear(scip, &multaggrconsdown, "consdown", SCIPvarGetMultaggrNVars(bestcand), 961 SCIPvarGetMultaggrVars(bestcand), SCIPvarGetMultaggrScalars(bestcand), - SCIPinfinity(scip), 962 SCIPfeasFloor(scip, bestsol) - SCIPvarGetMultaggrConstant(bestcand), 963 TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) ); 964 965 SCIP_CALL( SCIPcreateConsLinear(scip, &multaggrconsup, "consup", SCIPvarGetMultaggrNVars(bestcand), 966 SCIPvarGetMultaggrVars(bestcand), SCIPvarGetMultaggrScalars(bestcand), 967 SCIPfeasCeil(scip, bestsol) - SCIPvarGetMultaggrConstant(bestcand), SCIPinfinity(scip), 968 TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) ); 969 970 /* create the child nodes */ 971 SCIP_CALL( SCIPcreateChild(scip, &downchild, 1.0, estimatedown) ); 972 SCIPdebugMsg(scip, " down node: lowerbound %f estimate %f\n", SCIPnodeGetLowerbound(downchild), SCIPnodeGetEstimate(downchild)); 973 974 SCIP_CALL( SCIPcreateChild(scip, &upchild, 1.0, estimateup) ); 975 SCIPdebugMsg(scip, " up node: lowerbound %f estimate %f\n", SCIPnodeGetLowerbound(upchild), SCIPnodeGetEstimate(upchild)); 976 977 assert(downchild != NULL); 978 assert(upchild != NULL); 979 980 SCIP_CALL( SCIPaddConsNode(scip, downchild, multaggrconsdown, NULL) ); 981 SCIP_CALL( SCIPaddConsNode(scip, upchild, multaggrconsup, NULL) ); 982 983 #ifdef PRINTNODECONS 984 SCIPdebugMsg(scip, "branching at node %lld\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip))); 985 986 SCIPdebugMsg(scip, "created child node %lld with constraint:\n", SCIPnodeGetNumber(downchild)); 987 SCIP_CALL( SCIPprintCons(scip, multaggrconsdown, NULL) ); 988 SCIPinfoMessage(scip, NULL, "\n"); 989 990 SCIPdebugMsg(scip, "created child node %lld with constraint:\n", SCIPnodeGetNumber(upchild)); 991 SCIP_CALL( SCIPprintCons(scip, multaggrconsup, NULL) ); 992 SCIPinfoMessage(scip, NULL, "\n"); 993 #endif 994 995 /* relase constraints */ 996 SCIP_CALL( SCIPreleaseCons(scip, &multaggrconsdown) ); 997 SCIP_CALL( SCIPreleaseCons(scip, &multaggrconsup) ); 998 999 SCIPdebugMsg(scip, "BRANCHED on multi-aggregated variable <%s>\n", SCIPvarGetName(bestcand)); 1000 1001 *result = SCIP_BRANCHED; 1002 } 1003 else 1004 { 1005 SCIPstatistic( 1006 if( !(branchruledata->noupdate) ) 1007 branchruledata->nfracbranch += 1 1008 ); 1009 1010 assert(*result == SCIP_DIDNOTRUN); 1011 assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip))); 1012 1013 SCIP_CALL( SCIPbranchVarVal(scip, bestcand, bestsol, &downchild, NULL, &upchild) ); 1014 1015 assert(downchild != NULL); 1016 assert(upchild != NULL); 1017 1018 SCIPdebugMsg(scip, "BRANCHED on fractional variable <%s>\n", SCIPvarGetName(bestcand)); 1019 1020 *result = SCIP_BRANCHED; 1021 } 1022 1023 /* update the lower bounds in the children; we must not do this if columns are missing in the LP 1024 * (e.g., because we are doing branch-and-price) or the problem should be solved exactly 1025 */ 1026 if( SCIPallColsInLP(scip) && !SCIPisExactSolve(scip) ) 1027 { 1028 SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) ); 1029 SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) ); 1030 } 1031 SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild)); 1032 SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild)); 1033 } 1034 } 1035 else 1036 { 1037 SCIPdebugMsg(scip, "strong branching breaks\n" ); 1038 1039 SCIPstatistic( 1040 if( *result == SCIP_CUTOFF ) 1041 { 1042 branchruledata->nfractcutoff += 1; 1043 } 1044 else 1045 { 1046 branchruledata->nfractconsadd += 1; 1047 } 1048 ) 1049 } 1050 1051 SCIPfreeBufferArray(scip, &lpcandsfrac); 1052 SCIPfreeBufferArray(scip, &lpcandssol); 1053 SCIPfreeBufferArray(scip, &lpcands); 1054 1055 SCIP_CALL( SCIPsetLongintParam(scip, "branching/fullstrong/reevalage", oldreevalage) ); 1056 1057 return SCIP_OKAY; 1058 } 1059 1060 /* 1061 * branching rule specific interface methods 1062 */ 1063 1064 /** creates the multi-aggregated branching rule and includes it in SCIP */ 1065 SCIP_RETCODE SCIPincludeBranchruleMultAggr( 1066 SCIP* scip /**< SCIP data structure */ 1067 ) 1068 { 1069 SCIP_BRANCHRULEDATA* branchruledata; 1070 SCIP_BRANCHRULE* branchrule; 1071 1072 /* create multaggr branching rule data */ 1073 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) ); 1074 branchruledata->lastcand = 0; 1075 branchruledata->skipsize = 0; 1076 branchruledata->skipup = NULL; 1077 branchruledata->skipdown = NULL; 1078 SCIPstatistic(branchruledata->ratioggain = NULL); 1079 1080 /* include branching rule */ 1081 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, 1082 BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) ); 1083 1084 assert(branchrule != NULL); 1085 1086 /* set non fundamental callbacks via setter functions */ 1087 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyMultAggr) ); 1088 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeMultAggr) ); 1089 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitMultAggr) ); 1090 SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitMultAggr) ); 1091 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpMultAggr) ); 1092 1093 /* multi-aggregated branching rule parameters */ 1094 SCIP_CALL( SCIPaddLongintParam(scip, 1095 "branching/multaggr/reevalage", 1096 "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node", 1097 &branchruledata->reevalage, TRUE, DEFAULT_REEVALAGE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1098 SCIP_CALL( SCIPaddIntParam(scip, 1099 "branching/multaggr/maxproprounds", 1100 "maximum number of propagation rounds to be performed during multaggr branching before solving the LP (-1: no limit, -2: parameter settings)", 1101 &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) ); 1102 SCIP_CALL( SCIPaddBoolParam(scip, 1103 "branching/multaggr/probingbounds", 1104 "should valid bounds be identified in a probing-like fashion during multaggr branching (only with propagation)?", 1105 &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) ); 1106 1107 return SCIP_OKAY; 1108 } 1109