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 cons_benders.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for Benders' decomposition 28 * @author Stephen J. Maher 29 * 30 * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a 31 * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation 32 * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with 33 * respect to the subproblem constraints. 34 * 35 * This constraint handler has an enforcement priority that is less than the integer constraint handler. This means that 36 * only integer feasible solutions from the LP solver are enforced by this constraint handler. This is the traditional 37 * behaviour of the branch-and-check approach to Benders' decomposition. Additionally, the check priority is set low, 38 * such that this expensive constraint handler is only called as a final check on primal feasible solutions. 39 * 40 * This constraint handler in the standard constraint handler that should be added when using Benders' decomposition. 41 * Additionally, there is a flag in SCIPincludeConshdlrBenders that permits the addition of the LP constraint handler, 42 * cons_benderslp. The use of both cons_benders and cons_benderslp allows the user to perform a multiphase Benders' 43 * decomposition algorithm. 44 */ 45 46 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 47 48 #include <assert.h> 49 #include <string.h> 50 51 #include "scip/scip.h" 52 #include "scip/cons_benders.h" 53 #include "scip/heur_trysol.h" 54 #include "scip/heuristics.h" 55 56 57 /* fundamental constraint handler properties */ 58 #define CONSHDLR_NAME "benders" 59 #define CONSHDLR_DESC "constraint handler to execute Benders' Decomposition" 60 #define CONSHDLR_ENFOPRIORITY -100 /**< priority of the constraint handler for constraint enforcing */ 61 #define CONSHDLR_CHECKPRIORITY -5000000 /**< priority of the constraint handler for checking feasibility */ 62 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, 63 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 64 #define CONSHDLR_MAXPREROUNDS 0 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */ 65 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */ 66 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */ 67 68 69 #define DEFAULT_CHECKEDSOLSSIZE 20 /**< initial size of the checked sols array */ 70 #define DEFAULT_ACTIVE FALSE /**< is the constraint handler active? */ 71 72 /* 73 * Data structures 74 */ 75 76 /** constraint handler data */ 77 struct SCIP_ConshdlrData 78 { 79 int* checkedsols; /**< an array of solutions that this constraint has already checked */ 80 int ncheckedsols; /**< the number of checked solutions */ 81 int checkedsolssize; /**< the size of the checked solutions array */ 82 SCIP_Bool active; /**< is the constraint handler active? */ 83 }; 84 85 /* 86 * Local methods 87 */ 88 89 /** constructs a new solution based upon the solutions to the Benders' decomposition subproblems */ 90 static 91 SCIP_RETCODE constructValidSolution( 92 SCIP* scip, /**< the SCIP instance */ 93 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 94 SCIP_SOL* sol, /**< primal CIP solution */ 95 SCIP_BENDERSENFOTYPE type /**< the type of solution being enforced */ 96 ) 97 { 98 SCIP_CONSHDLRDATA* conshdlrdata; 99 SCIP_SOL* newsol; 100 SCIP_HEUR* heurtrysol; 101 SCIP_BENDERS** benders; 102 SCIP_VAR** auxiliaryvars; 103 int nactivebenders; 104 int nsubproblems; 105 int i; 106 int j; 107 SCIP_Bool success = TRUE; 108 109 /* don't propose new solutions if not in presolve or solving */ 110 if( SCIPgetStage(scip) < SCIP_STAGE_INITPRESOLVE || SCIPgetStage(scip) >= SCIP_STAGE_SOLVED ) 111 return SCIP_OKAY; 112 113 conshdlrdata = SCIPconshdlrGetData(conshdlr); 114 assert(conshdlrdata != NULL); 115 116 benders = SCIPgetBenders(scip); 117 nactivebenders = SCIPgetNActiveBenders(scip); 118 119 /* if the solution is NULL, then we create the solution from the LP sol */ 120 if( sol != NULL ) 121 { 122 assert(type == SCIP_BENDERSENFOTYPE_CHECK); 123 SCIP_CALL( SCIPcreateSolCopy(scip, &newsol, sol) ); 124 } 125 else 126 { 127 switch( type ) 128 { 129 case SCIP_BENDERSENFOTYPE_LP: 130 SCIP_CALL( SCIPcreateLPSol(scip, &newsol, NULL) ); 131 break; 132 case SCIP_BENDERSENFOTYPE_PSEUDO: 133 SCIP_CALL( SCIPcreatePseudoSol(scip, &newsol, NULL) ); 134 break; 135 case SCIP_BENDERSENFOTYPE_RELAX: 136 SCIP_CALL( SCIPcreateRelaxSol(scip, &newsol, NULL) ); 137 break; 138 default: 139 SCIP_CALL( SCIPcreateLPSol(scip, &newsol, NULL) ); 140 break; 141 } /*lint !e788*/ 142 } 143 SCIP_CALL( SCIPunlinkSol(scip, newsol) ); 144 145 /* looping through all Benders' decompositions to construct the new solution */ 146 for( i = 0; i < nactivebenders; i++ ) 147 { 148 /* getting the auxiliary variables and the number of subproblems from the Benders' decomposition structure */ 149 auxiliaryvars = SCIPbendersGetAuxiliaryVars(benders[i]); 150 nsubproblems = SCIPbendersGetNSubproblems(benders[i]); 151 152 /* setting the auxiliary variable in the new solution */ 153 for( j = 0; j < nsubproblems; j++ ) 154 { 155 SCIP_Real objval; 156 157 objval = SCIPbendersGetSubproblemObjval(benders[i], j); 158 159 if( SCIPvarGetStatus(auxiliaryvars[j]) == SCIP_VARSTATUS_FIXED 160 && !SCIPisEQ(scip, SCIPgetSolVal(scip, newsol, auxiliaryvars[j]), objval) ) 161 { 162 success = FALSE; 163 break; 164 } 165 else if( SCIPisLT(scip, SCIPgetSolVal(scip, newsol, auxiliaryvars[j]), objval) ) 166 { 167 SCIP_CALL( SCIPsetSolVal(scip, newsol, auxiliaryvars[j], objval) ); 168 } 169 } 170 171 if( !success ) 172 break; 173 } 174 175 /* if setting the variable values was successful, then we try to add the solution */ 176 if( success ) /*lint !e774*/ 177 { 178 /* checking the size of the checkedsols array and extending it is there is not enough memory */ 179 assert(conshdlrdata->ncheckedsols <= conshdlrdata->checkedsolssize); 180 if( conshdlrdata->ncheckedsols + 1 > conshdlrdata->checkedsolssize ) 181 { 182 int newsize; 183 184 newsize = SCIPcalcMemGrowSize(scip, conshdlrdata->ncheckedsols + 1); 185 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize, newsize) ); 186 conshdlrdata->checkedsolssize = newsize; 187 } 188 assert(conshdlrdata->ncheckedsols + 1 <= conshdlrdata->checkedsolssize); 189 190 /* recording the solution number to avoid checking the solution again */ 191 conshdlrdata->checkedsols[conshdlrdata->ncheckedsols] = SCIPsolGetIndex(newsol); 192 conshdlrdata->ncheckedsols++; 193 194 /* getting the try solution heuristic */ 195 heurtrysol = SCIPfindHeur(scip, "trysol"); 196 197 /* passing the new solution to the trysol heuristic */ 198 SCIP_CALL( SCIPcheckSol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) ); 199 if ( success ) 200 { 201 SCIP_CALL( SCIPheurPassSolAddSol(scip, heurtrysol, newsol) ); 202 SCIPdebugMsg(scip, "Creating solution was successful.\n"); 203 } 204 else 205 { 206 /* the solution might not be feasible, because of additional constraints */ 207 SCIPdebugMsg(scip, "Creating solution was not successful.\n"); 208 } 209 } 210 211 SCIP_CALL( SCIPfreeSol(scip, &newsol) ); 212 213 return SCIP_OKAY; 214 } 215 216 /** checks the Benders' decomposition auxiliary variables for unboundedness. */ 217 static 218 SCIP_Bool unboundedAuxiliaryVariables( 219 SCIP* scip, /**< the SCIP data structure */ 220 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */ 221 SCIP_SOL* sol /**< the primal solution to enforce, or NULL for the current LP/pseudo sol */ 222 ) 223 { 224 int nsubproblems; 225 SCIP_Bool unbounded = FALSE; 226 int i; 227 228 assert(scip != NULL); 229 assert(benders != NULL); 230 231 nsubproblems = SCIPbendersGetNSubproblems(benders); 232 233 /* checking the auxiliary variable values for unboundedness */ 234 for( i = 0; i < nsubproblems; i++ ) 235 { 236 if( SCIPisInfinity(scip, SCIPgetBendersAuxiliaryVarVal(scip, benders, sol, i)) 237 || SCIPisInfinity(scip, -SCIPgetBendersAuxiliaryVarVal(scip, benders, sol, i)) ) 238 { 239 unbounded = TRUE; 240 break; 241 } 242 } 243 244 return unbounded; 245 } 246 247 /** enforces Benders' constraints for given solution 248 * 249 * This method is called from cons_benderslp and cons_benders. If the method is called from cons_benderslp, then the 250 * solutions are not guaranteed to be integer feasible. This is because the default priority is set greater than the 251 * integer constraint handler. If this method is called from cons_benders, then, because the default enforcement 252 * priority is set less than that of the integer constraint handler, then it can be assumed that the solutions are 253 * integer feasible. 254 * 255 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint == 256 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e. 257 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check 258 * solution feasibility. 259 */ 260 SCIP_RETCODE SCIPconsBendersEnforceSolution( 261 SCIP* scip, /**< the SCIP instance */ 262 SCIP_SOL* sol, /**< the primal solution to enforce, or NULL for the current LP/pseudo sol */ 263 SCIP_CONSHDLR* conshdlr, /**< the constraint handler */ 264 SCIP_RESULT* result, /**< the result of the enforcement */ 265 SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */ 266 SCIP_Bool checkint /**< should integrality be considered when checking the subproblems */ 267 ) 268 { 269 SCIP_BENDERS** benders; 270 SCIP_Bool infeasible; 271 SCIP_Bool auxviol; 272 int nactivebenders; 273 int i; 274 275 assert(scip != NULL); 276 assert(conshdlr != NULL); 277 assert(result != NULL); 278 279 (*result) = SCIP_FEASIBLE; 280 infeasible = FALSE; 281 auxviol = FALSE; 282 283 benders = SCIPgetBenders(scip); 284 nactivebenders = SCIPgetNActiveBenders(scip); 285 286 for( i = 0; i < nactivebenders; i++ ) 287 { 288 switch( type ) 289 { 290 case SCIP_BENDERSENFOTYPE_LP: 291 if( SCIPbendersCutLP(benders[i]) ) 292 { 293 SCIP_Bool unbounded = FALSE; 294 295 /* if the solution is unbounded, then it may not be possible to generate any Benders' decomposition 296 * cuts. If the unboundedness is from the auxiliary variables, then cuts are required. Otherwise, if 297 * the unboundedness comes from original variables, then the unboundedness needs to be handled by other 298 * constraint handlers or the problem is reported as unbounded 299 * */ 300 if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 301 { 302 if( !unboundedAuxiliaryVariables(scip, benders[i], NULL) ) 303 { 304 (*result) = SCIP_FEASIBLE; 305 auxviol = FALSE; 306 unbounded = TRUE; 307 } 308 } 309 310 if( !unbounded ) 311 { 312 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) ); 313 } 314 } 315 break; 316 case SCIP_BENDERSENFOTYPE_RELAX: 317 if( SCIPbendersCutRelaxation(benders[i]) ) 318 { 319 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol, type, checkint) ); 320 } 321 break; 322 case SCIP_BENDERSENFOTYPE_PSEUDO: 323 if( SCIPbendersCutPseudo(benders[i]) ) 324 { 325 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) ); 326 } 327 break; 328 case SCIP_BENDERSENFOTYPE_CHECK: 329 SCIPwarningMessage(scip, "The conscheck callback is not supported\n"); 330 break; 331 default: 332 break; 333 } /*lint !e788*/ 334 335 /* The decompositions are checked until one is found that is not feasible. Not being feasible could mean that 336 * infeasibility of the original problem has been proven or a constraint has been added. If the result 337 * SCIP_DIDNOTRUN is returned, then the next decomposition is checked */ 338 if( (*result) != SCIP_FEASIBLE && (*result) != SCIP_DIDNOTRUN ) 339 break; 340 } 341 342 /* if the constraint handler was called with an integer feasible solution, then a feasible solution can be proposed */ 343 if( checkint ) 344 { 345 /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables 346 * still need to be updated. This is done by constructing a valid solution. */ 347 if( (*result) == SCIP_FEASIBLE && auxviol ) 348 { 349 SCIP_CALL( constructValidSolution(scip, conshdlr, sol, type) ); 350 351 (*result) = SCIP_INFEASIBLE; 352 } 353 } 354 355 /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result 356 * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this 357 * solution is feasible. 358 */ 359 if( (*result) == SCIP_DIDNOTRUN ) 360 (*result) = SCIP_FEASIBLE; 361 362 return SCIP_OKAY; 363 } 364 365 /* 366 * Callback methods of constraint handler 367 */ 368 369 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 370 static 371 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders) 372 { /*lint --e{715}*/ 373 assert(scip != NULL); 374 375 SCIP_CALL( SCIPincludeConshdlrBenders(scip) ); 376 377 *valid = TRUE; 378 379 return SCIP_OKAY; 380 } 381 382 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 383 static 384 SCIP_DECL_CONSFREE(consFreeBenders) 385 { /*lint --e{715}*/ 386 SCIP_CONSHDLRDATA* conshdlrdata; 387 388 assert(scip != NULL); 389 assert(conshdlr != NULL); 390 391 conshdlrdata = SCIPconshdlrGetData(conshdlr); 392 assert(conshdlrdata != NULL); 393 394 /* freeing the constraint handler data */ 395 SCIPfreeMemory(scip, &conshdlrdata); 396 397 return SCIP_OKAY; 398 } 399 400 401 /** initialization method of constraint handler (called after problem was transformed) */ 402 static 403 SCIP_DECL_CONSINIT(consInitBenders) 404 { /*lint --e{715}*/ 405 SCIP_CONSHDLRDATA* conshdlrdata; 406 407 assert(scip != NULL); 408 assert(conshdlr != NULL); 409 410 conshdlrdata = SCIPconshdlrGetData(conshdlr); 411 412 conshdlrdata->checkedsolssize = DEFAULT_CHECKEDSOLSSIZE; 413 conshdlrdata->ncheckedsols = 0; 414 415 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize) ); 416 417 return SCIP_OKAY; 418 } 419 420 421 /** deinitialization method of constraint handler (called before transformed problem is freed) */ 422 static 423 SCIP_DECL_CONSEXIT(consExitBenders) 424 { /*lint --e{715}*/ 425 SCIP_CONSHDLRDATA* conshdlrdata; 426 427 assert(scip != NULL); 428 assert(conshdlr != NULL); 429 430 conshdlrdata = SCIPconshdlrGetData(conshdlr); 431 assert(conshdlrdata != NULL); 432 433 /* freeing the checked sols array */ 434 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize); 435 436 return SCIP_OKAY; 437 } 438 439 440 441 /** constraint enforcing method of constraint handler for LP solutions */ 442 static 443 SCIP_DECL_CONSENFOLP(consEnfolpBenders) 444 { /*lint --e{715}*/ 445 SCIP_CONSHDLRDATA* conshdlrdata; 446 447 assert(scip != NULL); 448 assert(conshdlr != NULL); 449 450 conshdlrdata = SCIPconshdlrGetData(conshdlr); 451 assert(conshdlrdata != NULL); 452 453 if( conshdlrdata->active ) 454 { 455 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_LP, TRUE) ); 456 } 457 else 458 (*result) = SCIP_FEASIBLE; 459 460 return SCIP_OKAY; 461 } 462 463 464 /** constraint enforcing method of constraint handler for relaxation solutions */ 465 static 466 SCIP_DECL_CONSENFORELAX(consEnforelaxBenders) 467 { /*lint --e{715}*/ 468 SCIP_CONSHDLRDATA* conshdlrdata; 469 470 assert(scip != NULL); 471 assert(conshdlr != NULL); 472 473 conshdlrdata = SCIPconshdlrGetData(conshdlr); 474 assert(conshdlrdata != NULL); 475 476 if( conshdlrdata->active ) 477 { 478 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, sol, conshdlr, result, SCIP_BENDERSENFOTYPE_RELAX, TRUE) ); 479 } 480 else 481 (*result) = SCIP_FEASIBLE; 482 483 return SCIP_OKAY; 484 } 485 486 487 /** constraint enforcing method of constraint handler for pseudo solutions */ 488 static 489 SCIP_DECL_CONSENFOPS(consEnfopsBenders) 490 { /*lint --e{715}*/ 491 SCIP_CONSHDLRDATA* conshdlrdata; 492 493 assert(scip != NULL); 494 assert(conshdlr != NULL); 495 496 conshdlrdata = SCIPconshdlrGetData(conshdlr); 497 assert(conshdlrdata != NULL); 498 499 if( conshdlrdata->active ) 500 { 501 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_PSEUDO, TRUE) ); 502 } 503 else 504 (*result) = SCIP_FEASIBLE; 505 506 return SCIP_OKAY; 507 } 508 509 510 /** feasibility check method of constraint handler for integral solutions 511 * 512 * This function checks the feasibility of the Benders' decomposition master problem. In the case that the problem is 513 * feasible, then the auxiliary variables must be updated with the subproblem objective function values. It is not 514 * possible to simply update the auxiliary variable values, so a new solution is created. 515 */ 516 static 517 SCIP_DECL_CONSCHECK(consCheckBenders) 518 { /*lint --e{715}*/ 519 SCIP_CONSHDLRDATA* conshdlrdata; 520 SCIP_BENDERS** benders; 521 int nactivebenders; 522 int solindex; 523 int i; 524 SCIP_Bool performcheck; 525 SCIP_Bool infeasible; 526 SCIP_Bool auxviol; 527 528 assert(scip != NULL); 529 assert(conshdlr != NULL); 530 assert(result != NULL); 531 532 (*result) = SCIP_FEASIBLE; 533 performcheck = TRUE; 534 infeasible = FALSE; 535 auxviol = FALSE; 536 537 conshdlrdata = SCIPconshdlrGetData(conshdlr); 538 539 /* if the constraint handler is active, then the check must be performed. */ 540 if( conshdlrdata->active ) 541 { 542 benders = SCIPgetBenders(scip); 543 nactivebenders = SCIPgetNActiveBenders(scip); 544 545 /* checking if the solution was constructed by this constraint handler */ 546 solindex = SCIPsolGetIndex(sol); 547 for( i = 0; i < conshdlrdata->ncheckedsols; i++ ) 548 { 549 if( conshdlrdata->checkedsols[i] == solindex ) 550 { 551 conshdlrdata->checkedsols[0] = conshdlrdata->checkedsols[conshdlrdata->ncheckedsols - 1]; 552 conshdlrdata->ncheckedsols--; 553 554 performcheck = FALSE; 555 break; 556 } 557 } 558 559 /* if the solution has not been checked before, then we must perform the check */ 560 if( performcheck && nactivebenders > 0 ) 561 { 562 for( i = 0; i < nactivebenders; i++ ) 563 { 564 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol, 565 SCIP_BENDERSENFOTYPE_CHECK, TRUE) ); 566 567 /* in the case of multiple Benders' decompositions, the subproblems are solved until a constriant is added or 568 * infeasibility is proven. So if the result is not SCIP_FEASIBLE, then the loop is exited */ 569 if( (*result) != SCIP_FEASIBLE ) 570 break; 571 } 572 573 /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables 574 * still need to be updated. This is done by constructing a valid solution. */ 575 if( (*result) == SCIP_FEASIBLE ) 576 { 577 if( auxviol ) 578 { 579 if( !SCIPsolIsOriginal(sol) ) 580 { 581 SCIP_CALL( constructValidSolution(scip, conshdlr, sol, SCIP_BENDERSENFOTYPE_CHECK) ); 582 } 583 584 if( printreason ) 585 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "all subproblems are feasible but there is a violation in the auxiliary variables\n"); 586 587 (*result) = SCIP_INFEASIBLE; 588 } 589 } 590 591 /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result 592 * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this 593 * solution is feasible. 594 */ 595 if( (*result) == SCIP_DIDNOTRUN ) 596 (*result) = SCIP_FEASIBLE; 597 } 598 } 599 600 return SCIP_OKAY; 601 } 602 603 604 /** the presolving method for the Benders' decomposition constraint handler 605 * 606 * This method is used to update the lower bounds of the auxiliary problem and to identify infeasibility before the 607 * subproblems are solved. When SCIP is copied, the Benders' decomposition subproblems from the source SCIP are 608 * transferred to the target SCIP. So there is no need to perform this presolving step in the copied SCIP, since the 609 * computed bounds would be identical. 610 */ 611 static 612 SCIP_DECL_CONSPRESOL(consPresolBenders) 613 { /*lint --e{715}*/ 614 SCIP_CONSHDLRDATA* conshdlrdata; 615 SCIP_BENDERS** benders; 616 int nactivebenders; 617 int nsubproblems; 618 int i; 619 int j; 620 621 assert(scip != NULL); 622 assert(conshdlr != NULL); 623 624 (*result) = SCIP_DIDNOTFIND; 625 626 /* this presolving step is only valid for the main SCIP instance. If the SCIP instance is copied, then the presolving 627 * step is not performed. 628 */ 629 if( SCIPgetSubscipDepth(scip) > 0 ) 630 { 631 (*result) = SCIP_DIDNOTRUN; 632 return SCIP_OKAY; 633 } 634 635 conshdlrdata = SCIPconshdlrGetData(conshdlr); 636 assert(conshdlrdata != NULL); 637 638 /* it is only possible to compute the lower bound of the subproblems if the constraint handler is active */ 639 if( conshdlrdata->active ) 640 { 641 benders = SCIPgetBenders(scip); 642 nactivebenders = SCIPgetNActiveBenders(scip); 643 644 /* need to compute the lower bound for all active Benders' decompositions */ 645 for( i = 0; i < nactivebenders; i++ ) 646 { 647 nsubproblems = SCIPbendersGetNSubproblems(benders[i]); 648 649 for( j = 0; j < nsubproblems; j++ ) 650 { 651 SCIP_VAR* auxiliaryvar; 652 SCIP_Real lowerbound; 653 SCIP_Bool infeasible; 654 655 infeasible = FALSE; 656 657 /* computing the lower bound of the subproblem by solving it without any variable fixings */ 658 SCIP_CALL( SCIPcomputeBendersSubproblemLowerbound(scip, benders[i], j, &lowerbound, &infeasible) ); 659 660 if( infeasible ) 661 { 662 (*result) = SCIP_CUTOFF; 663 break; 664 } 665 666 /* retrieving the auxiliary variable */ 667 auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders[i], j); 668 669 /* only update the lower bound if it is greater than the current lower bound */ 670 if( SCIPisGT(scip, lowerbound, SCIPvarGetLbLocal(auxiliaryvar)) ) 671 { 672 SCIPdebugMsg(scip, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound); 673 /* updating the lower bound of the auxiliary variable */ 674 SCIP_CALL( SCIPchgVarLb(scip, auxiliaryvar, lowerbound) ); 675 676 (*nchgbds)++; 677 (*result) = SCIP_SUCCESS; 678 } 679 680 /* stores the lower bound for the subproblem */ 681 SCIPbendersUpdateSubproblemLowerbound(benders[i], j, lowerbound); 682 } 683 684 if( (*result) == SCIP_CUTOFF ) 685 break; 686 } 687 } 688 689 return SCIP_OKAY; 690 } 691 692 /** variable rounding lock method of constraint handler 693 * The auxiliary variables and the master problem variables need to lock added by the Benders' decomposition 694 * constraint. The auxiliary variables require a down lock. The master problem variable need both up and down lock. 695 * The master problem variables require locks in both directions because the coefficients in all potential Benders' 696 * cuts are not known in general. 697 */ 698 static 699 SCIP_DECL_CONSLOCK(consLockBenders) 700 { /*lint --e{715}*/ 701 SCIP_CONSHDLRDATA* conshdlrdata; 702 SCIP_BENDERS** benders; 703 SCIP_VAR** vars; 704 int nactivebenders; 705 int nsubproblems; 706 int nvars; 707 int i; 708 int j; 709 710 assert(scip != NULL); 711 assert(conshdlr != NULL); 712 assert(locktype == SCIP_LOCKTYPE_MODEL); 713 714 conshdlrdata = SCIPconshdlrGetData(conshdlr); 715 assert(conshdlrdata != NULL); 716 717 /* the locks should only be added if the Benders' decomposition constraint handler has been activated */ 718 if( conshdlrdata->active ) 719 { 720 benders = SCIPgetBenders(scip); 721 nactivebenders = SCIPgetNActiveBenders(scip); 722 723 /* retrieving the master problem variables */ 724 SCIP_CALL( SCIPgetOrigVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 725 726 /* need to compute the lower bound for all active Benders' decompositions */ 727 for( i = 0; i < nactivebenders; i++ ) 728 { 729 nsubproblems = SCIPbendersGetNSubproblems(benders[i]); 730 731 /* if the auxiliary variable exists, then we need to add a down lock. Initially, a down lock is added to all 732 * auxiliary variables during creating. This is because the creation of auxiliary variable occurs after 733 * CONS_LOCK is called. The inclusion of the auxiliary variables in this function is to cover the case if locks 734 * are added or removed after presolving. 735 */ 736 for( j = 0; j < nsubproblems; j++ ) 737 { 738 SCIP_VAR* auxvar; 739 740 auxvar = SCIPbendersGetAuxiliaryVar(benders[i], j); 741 742 if( auxvar != NULL ) 743 { 744 SCIP_CALL( SCIPaddVarLocksType(scip, auxvar, locktype, nlockspos, nlocksneg) ); 745 } 746 } 747 748 /* adding up and down locks for all master problem variables. Since the locks for all constraint handlers 749 * without constraints, no auxiliary variables have been added. As such, all variables are master variables. 750 */ 751 for( j = 0; j < nvars; j++ ) 752 { 753 SCIP_CALL( SCIPaddVarLocksType(scip, vars[j], locktype, (nlockspos + nlocksneg)*nsubproblems, 754 (nlockspos + nlocksneg)*nsubproblems) ); 755 } 756 } 757 } 758 759 return SCIP_OKAY; 760 } 761 762 763 /* 764 * constraint specific interface methods 765 */ 766 767 /** creates the handler for Benders' decomposition and includes it in SCIP */ 768 SCIP_RETCODE SCIPincludeConshdlrBenders( 769 SCIP* scip /**< SCIP data structure */ 770 ) 771 { 772 SCIP_CONSHDLRDATA* conshdlrdata; 773 SCIP_CONSHDLR* conshdlr; 774 775 /* create benders constraint handler data */ 776 conshdlrdata = NULL; 777 778 SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) ); 779 780 conshdlr = NULL; 781 782 /* include constraint handler */ 783 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 784 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 785 consEnfolpBenders, consEnfopsBenders, consCheckBenders, consLockBenders, 786 conshdlrdata) ); 787 assert(conshdlr != NULL); 788 789 /* set non-fundamental callbacks via specific setter functions */ 790 SCIP_CALL( SCIPsetConshdlrInit(scip, conshdlr, consInitBenders) ); 791 SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitBenders) ); 792 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBenders, NULL) ); 793 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBenders) ); 794 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBenders) ); 795 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBenders, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 796 797 /* add Benders' decomposition constraint handler parameters */ 798 SCIP_CALL( SCIPaddBoolParam(scip, 799 "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition constraint handler active?", 800 &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL)); 801 802 return SCIP_OKAY; 803 } 804