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_mostinf.c 26 * @ingroup DEFPLUGINS_BRANCH 27 * @brief most infeasible LP branching rule 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/branch_mostinf.h" 34 #include "scip/pub_branch.h" 35 #include "scip/pub_message.h" 36 #include "scip/pub_var.h" 37 #include "scip/scip_branch.h" 38 #include "scip/scip_message.h" 39 #include "scip/scip_numerics.h" 40 #include "scip/scip_var.h" 41 #include <string.h> 42 43 44 #define BRANCHRULE_NAME "mostinf" 45 #define BRANCHRULE_DESC "most infeasible branching" 46 #define BRANCHRULE_PRIORITY 100 47 #define BRANCHRULE_MAXDEPTH -1 48 #define BRANCHRULE_MAXBOUNDDIST 1.0 49 50 /* 51 * Local methods 52 */ 53 54 /** compares the so far best branching candidate with a new candidate and updates best candidate, if new candidate is better */ 55 static 56 void updateBestCandidate( 57 SCIP* scip, /**< SCIP data structure */ 58 SCIP_VAR** bestvar, /**< best branching candidate */ 59 SCIP_Real* bestscore, /**< score of best branching candidate */ 60 SCIP_Real* bestobj, /**< absolute objective value of best branching candidate */ 61 SCIP_Real* bestsol, /**< proposed branching point of best branching candidate */ 62 SCIP_VAR* cand, /**< branching candidate to consider */ 63 SCIP_Real candscore, /**< scoring of branching candidate */ 64 SCIP_Real candsol /**< proposed branching point of branching candidate */ 65 ) 66 { 67 SCIP_Real obj; 68 69 assert(scip != NULL); 70 assert(bestvar != NULL); 71 assert(bestscore != NULL); 72 assert(bestobj != NULL); 73 assert(*bestobj >= 0.0); 74 assert(cand != NULL); 75 76 /* a branching variable candidate should either be an active problem variable or a multi-aggregated variable */ 77 assert(SCIPvarIsActive(SCIPvarGetProbvar(cand)) || 78 SCIPvarGetStatus(SCIPvarGetProbvar(cand)) == SCIP_VARSTATUS_MULTAGGR); 79 80 if( SCIPvarGetStatus(SCIPvarGetProbvar(cand)) == SCIP_VARSTATUS_MULTAGGR ) 81 { 82 /* for a multi-aggregated variable, we call updateBestCandidate function recursively with all variables in the multi-aggregation */ 83 SCIP_VAR** multvars; 84 int nmultvars; 85 int i; 86 SCIP_Bool success; 87 SCIP_Real multvarlb; 88 SCIP_Real multvarub; 89 90 cand = SCIPvarGetProbvar(cand); 91 multvars = SCIPvarGetMultaggrVars(cand); 92 nmultvars = SCIPvarGetMultaggrNVars(cand); 93 94 /* if we have a candidate branching point, then first register only aggregation variables 95 * for which we can compute a corresponding branching point too (see also comments below) 96 * if this fails, then register all (unfixed) aggregation variables, thereby forgetting about candsol 97 */ 98 success = FALSE; 99 if( candsol != SCIP_INVALID ) /*lint !e777*/ 100 { 101 SCIP_Real* multscalars; 102 SCIP_Real minact; 103 SCIP_Real maxact; 104 SCIP_Real aggrvarsol; 105 SCIP_Real aggrvarsol1; 106 SCIP_Real aggrvarsol2; 107 108 multscalars = SCIPvarGetMultaggrScalars(cand); 109 110 /* for computing the branching point, we need the current bounds of the multi-aggregated variable */ 111 minact = SCIPcomputeVarLbLocal(scip, cand); 112 maxact = SCIPcomputeVarUbLocal(scip, cand); 113 114 for( i = 0; i < nmultvars; ++i ) 115 { 116 /* skip fixed variables */ 117 multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]); 118 multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]); 119 if( SCIPisEQ(scip, multvarlb, multvarub) ) 120 continue; 121 122 assert(multscalars != NULL); 123 assert(multscalars[i] != 0.0); 124 125 /* we cannot ensure that both the upper bound in the left node and the lower bound in the right node 126 * will be candsol by a clever choice for the branching point of multvars[i], 127 * but we can try to ensure that at least one of them will be at candsol 128 */ 129 if( multscalars[i] > 0.0 ) 130 { 131 /* cand >= candsol 132 * if multvars[i] >= (candsol - (maxact - multscalars[i] * ub(multvars[i]))) / multscalars[i] 133 * = (candsol - maxact) / multscalars[i] + ub(multvars[i]) 134 */ 135 aggrvarsol1 = (candsol - maxact) / multscalars[i] + multvarub; 136 137 /* cand <= candsol 138 * if multvars[i] <= (candsol - (minact - multscalar[i] * lb(multvars[i]))) / multscalars[i] 139 * = (candsol - minact) / multscalars[i] + lb(multvars[i]) 140 */ 141 aggrvarsol2 = (candsol - minact) / multscalars[i] + multvarlb; 142 } 143 else 144 { 145 /* cand >= candsol 146 * if multvars[i] <= (candsol - (maxact - multscalars[i] * lb(multvars[i]))) / multscalars[i] 147 * = (candsol - maxact) / multscalars[i] + lb(multvars[i]) 148 */ 149 aggrvarsol2 = (candsol - maxact) / multscalars[i] + multvarlb; 150 151 /* cand <= candsol 152 * if multvars[i] >= (candsol - (minact - multscalar[i] * ub(multvars[i]))) / multscalars[i] 153 * = (candsol - minact) / multscalars[i] + ub(multvars[i]) 154 */ 155 aggrvarsol1 = (candsol - minact) / multscalars[i] + multvarub; 156 } 157 158 /* by the above choice, aggrvarsol1 <= ub(multvars[i]) and aggrvarsol2 >= lb(multvars[i]) 159 * if aggrvarsol1 <= lb(multvars[i]) or aggrvarsol2 >= ub(multvars[i]), then choose the other one 160 * if both are out of bounds, then give up 161 * if both are inside bounds, then choose the one closer to 0.0 (someone has better idea???) 162 */ 163 if( SCIPisFeasLE(scip, aggrvarsol1, multvarlb) ) 164 { 165 if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) ) 166 continue; 167 else 168 aggrvarsol = aggrvarsol2; 169 } 170 else 171 { 172 if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) ) 173 aggrvarsol = aggrvarsol1; 174 else 175 aggrvarsol = REALABS(aggrvarsol1) < REALABS(aggrvarsol2) ? aggrvarsol1 : aggrvarsol2; 176 } 177 success = TRUE; 178 179 updateBestCandidate(scip, bestvar, bestscore, bestobj, bestsol, 180 multvars[i], candscore, aggrvarsol); 181 } 182 } 183 184 if( !success ) 185 for( i = 0; i < nmultvars; ++i ) 186 { 187 /* skip fixed variables */ 188 multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]); 189 multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]); 190 if( SCIPisEQ(scip, multvarlb, multvarub) ) 191 continue; 192 193 updateBestCandidate(scip, bestvar, bestscore, bestobj, bestsol, 194 multvars[i], candscore, SCIP_INVALID); 195 } 196 197 assert(*bestvar != NULL); /* if all variables were fixed, something is strange */ 198 199 return; 200 } 201 202 candscore *= SCIPvarGetBranchFactor(cand); 203 obj = SCIPvarGetObj(cand); 204 obj = REALABS(obj); 205 if( SCIPisInfinity(scip, candscore) 206 || (!SCIPisInfinity(scip, *bestscore) && 207 (SCIPisGT(scip, candscore, *bestscore) || (SCIPisGE(scip, candscore, *bestscore) && obj > *bestobj))) ) 208 { 209 *bestvar = cand; 210 *bestscore = candscore; 211 *bestobj = obj; 212 *bestsol = candsol; 213 } 214 } 215 216 /* 217 * Callback methods 218 */ 219 220 /** copy method for branchrule plugins (called when SCIP copies plugins) */ 221 static 222 SCIP_DECL_BRANCHCOPY(branchCopyMostinf) 223 { /*lint --e{715}*/ 224 assert(scip != NULL); 225 assert(branchrule != NULL); 226 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 227 228 /* call inclusion method of branchrule */ 229 SCIP_CALL( SCIPincludeBranchruleMostinf(scip) ); 230 231 return SCIP_OKAY; 232 } 233 234 235 /** branching execution method for fractional LP solutions */ 236 static 237 SCIP_DECL_BRANCHEXECLP(branchExeclpMostinf) 238 { /*lint --e{715}*/ 239 SCIP_VAR** lpcands; 240 SCIP_Real* lpcandsfrac; 241 int nlpcands; 242 SCIP_Real infeasibility; 243 SCIP_Real score; 244 SCIP_Real obj; 245 SCIP_Real bestscore; 246 SCIP_Real bestobj; 247 int bestcand; 248 int i; 249 250 assert(branchrule != NULL); 251 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 252 assert(scip != NULL); 253 assert(result != NULL); 254 255 SCIPdebugMsg(scip, "Execlp method of mostinf branching\n"); 256 257 /* get branching candidates */ 258 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, &lpcandsfrac, NULL, &nlpcands, NULL) ); 259 assert(nlpcands > 0); 260 261 /* search the most infeasible candidate */ 262 bestscore = SCIP_REAL_MIN; 263 bestobj = 0.0; 264 bestcand = -1; 265 for( i = 0; i < nlpcands; ++i ) 266 { 267 assert(lpcands[i] != NULL); 268 269 infeasibility = lpcandsfrac[i]; 270 infeasibility = MIN(infeasibility, 1.0-infeasibility); 271 score = infeasibility; 272 score *= SCIPvarGetBranchFactor(lpcands[i]); 273 obj = SCIPvarGetObj(lpcands[i]); 274 obj = REALABS(obj); 275 if( SCIPisGT(scip, score, bestscore) 276 || (SCIPisGE(scip, score, bestscore) && obj > bestobj) ) 277 { 278 bestscore = score; 279 bestobj = obj; 280 bestcand = i; 281 } 282 } 283 assert(bestcand >= 0); 284 285 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (frac=%g, obj=%g, factor=%g, score=%g)\n", 286 nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand]), lpcandsfrac[bestcand], bestobj, 287 SCIPvarGetBranchFactor(lpcands[bestcand]), bestscore); 288 289 /* perform the branching */ 290 SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) ); 291 *result = SCIP_BRANCHED; 292 293 return SCIP_OKAY; 294 } 295 296 /** branching execution method for external candidates */ 297 static 298 SCIP_DECL_BRANCHEXECEXT(branchExecextMostinf) 299 { /*lint --e{715}*/ 300 SCIP_VAR** externcands; 301 SCIP_Real* externcandssol; 302 SCIP_Real* externcandsscore; 303 int nexterncands; 304 SCIP_VAR* bestcand; 305 SCIP_Real bestscore; 306 SCIP_Real bestobj; 307 SCIP_Real bestsol; 308 SCIP_Real brpoint; 309 int i; 310 SCIP_NODE* downchild; 311 SCIP_NODE* eqchild; 312 SCIP_NODE* upchild; 313 314 assert(branchrule != NULL); 315 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 316 assert(scip != NULL); 317 assert(result != NULL); 318 319 SCIPdebugMsg(scip, "Execext method of mostinf branching\n"); 320 321 /* get branching candidates */ 322 SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nexterncands, NULL, NULL, NULL) ); 323 assert(nexterncands > 0); 324 325 /* search the most infeasible candidate */ 326 bestscore = SCIP_REAL_MIN; 327 bestobj = 0.0; 328 bestcand = NULL; 329 bestsol = SCIP_INVALID; 330 for( i = 0; i < nexterncands; ++i ) 331 { 332 updateBestCandidate(scip, &bestcand, &bestscore, &bestobj, &bestsol, externcands[i], externcandsscore[i], externcandssol[i]); 333 } 334 335 if( bestcand == NULL ) 336 { 337 SCIPerrorMessage("branchExecextMostinf failed to select a branching variable from %d candidates\n", nexterncands); 338 *result = SCIP_DIDNOTRUN; 339 return SCIP_OKAY; 340 } 341 342 brpoint = SCIPgetBranchingPoint(scip, bestcand, bestsol); 343 344 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s> (sol=%g, locdom=[%g,%g], obj=%g, factor=%g, score=%g), branching point=%g\n", 345 nexterncands, SCIPvarGetName(bestcand), bestsol, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand), bestobj, 346 SCIPvarGetBranchFactor(bestcand), bestscore, brpoint); 347 348 /* perform the branching */ 349 SCIP_CALL( SCIPbranchVarVal(scip, bestcand, brpoint, &downchild, &eqchild, &upchild) ); 350 351 if( downchild != NULL || eqchild != NULL || upchild != NULL ) 352 { 353 *result = SCIP_BRANCHED; 354 } 355 else 356 { 357 /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */ 358 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand))); 359 *result = SCIP_REDUCEDDOM; 360 } 361 362 return SCIP_OKAY; 363 } 364 365 366 /* 367 * branching specific interface methods 368 */ 369 370 /** creates the most infeasible LP branching rule and includes it in SCIP */ 371 SCIP_RETCODE SCIPincludeBranchruleMostinf( 372 SCIP* scip /**< SCIP data structure */ 373 ) 374 { 375 SCIP_BRANCHRULE* branchrule; 376 377 /* include branching rule */ 378 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, 379 BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, NULL) ); 380 381 assert(branchrule != NULL); 382 383 /* set non-fundamental callbacks via specific setter functions*/ 384 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyMostinf) ); 385 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpMostinf) ); 386 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextMostinf) ); 387 388 return SCIP_OKAY; 389 } 390