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 benderscut_int.c 26 * @ingroup OTHER_CFILES 27 * @brief Generates a Laporte and Louveaux Benders' decomposition integer cut 28 * @author Stephen J. Maher 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/benderscut_int.h" 34 #include "scip/cons_linear.h" 35 #include "scip/pub_benderscut.h" 36 #include "scip/pub_benders.h" 37 #include "scip/pub_lp.h" 38 #include "scip/pub_message.h" 39 #include "scip/pub_misc.h" 40 #include "scip/pub_paramset.h" 41 #include "scip/pub_var.h" 42 #include "scip/scip_benders.h" 43 #include "scip/scip_cons.h" 44 #include "scip/scip_cut.h" 45 #include "scip/scip_general.h" 46 #include "scip/scip_lp.h" 47 #include "scip/scip_mem.h" 48 #include "scip/scip_message.h" 49 #include "scip/scip_numerics.h" 50 #include "scip/scip_param.h" 51 #include "scip/scip_prob.h" 52 #include "scip/scip_sol.h" 53 #include <string.h> 54 55 #define BENDERSCUT_NAME "integer" 56 #define BENDERSCUT_DESC "Laporte and Louveaux Benders' decomposition integer cut" 57 #define BENDERSCUT_PRIORITY 0 58 #define BENDERSCUT_LPCUT FALSE 59 60 #define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */ 61 #define SCIP_DEFAULT_CUTCONSTANT -10000.0 62 63 /* 64 * Data structures 65 */ 66 67 /** Benders' decomposition cuts data */ 68 struct SCIP_BenderscutData 69 { 70 SCIP_BENDERS* benders; /**< the Benders' decomposition data structure */ 71 SCIP_Real cutconstant; /**< the constant for computing the integer cuts */ 72 SCIP_Real* subprobconstant; /**< the constant for each subproblem used for computing the integer cuts */ 73 SCIP_Bool addcuts; /**< should cuts be generated instead of constraints */ 74 SCIP_Bool* firstcut; /**< flag to indicate that the first cut needs to be generated. */ 75 int nsubproblems; /**< the number of subproblems for the Benders' decomposition */ 76 }; 77 78 /** method to call, when the priority of a Benders' decomposition was changed */ 79 static 80 SCIP_DECL_PARAMCHGD(paramChgdBenderscutintConstant) 81 { /*lint --e{715}*/ 82 SCIP_BENDERSCUTDATA* benderscutdata; 83 int i; 84 85 benderscutdata = (SCIP_BENDERSCUTDATA*)SCIPparamGetData(param); 86 assert(benderscutdata != NULL); 87 88 for( i = 0; i < benderscutdata->nsubproblems; i++ ) 89 benderscutdata->subprobconstant[i] = benderscutdata->cutconstant; 90 91 return SCIP_OKAY; 92 } 93 94 95 /** creates the Benders' decomposition cut data */ 96 static 97 SCIP_RETCODE createBenderscutData( 98 SCIP* scip, /**< the SCIP data structure */ 99 SCIP_BENDERSCUTDATA* benderscutdata /**< the Benders' cut data */ 100 ) 101 { 102 int i; 103 104 assert(scip != NULL); 105 assert(benderscutdata != NULL); 106 107 /* allocating the memory for the subproblem constants */ 108 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->subprobconstant, benderscutdata->nsubproblems) ); 109 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &benderscutdata->firstcut, benderscutdata->nsubproblems) ); 110 111 for( i = 0; i < benderscutdata->nsubproblems; i++ ) 112 { 113 benderscutdata->subprobconstant[i] = benderscutdata->cutconstant; 114 benderscutdata->firstcut[i] = TRUE; 115 } 116 117 return SCIP_OKAY; 118 } 119 120 /* 121 * Local methods 122 */ 123 124 /** updates the cut constant for the given subproblem based upon the global bounds of the associated auxiliary variable */ 125 static 126 void updateSubproblemCutConstant( 127 SCIP* masterprob, /**< the SCIP instance of the master problem */ 128 SCIP_BENDERS* benders, /**< the benders' decomposition structure */ 129 SCIP_BENDERSCUTDATA* benderscutdata, /**< the Benders' decomposition cut data */ 130 int probnumber /**< the index for the subproblem */ 131 ) 132 { 133 SCIP_VAR* auxiliaryvar; 134 135 assert(masterprob != NULL); 136 assert(benders != NULL); 137 assert(benderscutdata != NULL); 138 139 auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber); 140 141 /* checking if the subproblem lower bound has been updated. If it is has changed, then firstcut is set to TRUE. 142 * Otherwise, the constant remains the same. 143 */ 144 if( SCIPisGT(masterprob, SCIPbendersGetSubproblemLowerbound(benders, probnumber), 145 benderscutdata->subprobconstant[probnumber]) ) 146 { 147 benderscutdata->subprobconstant[probnumber] = SCIPbendersGetSubproblemLowerbound(benders, probnumber); 148 benderscutdata->firstcut[probnumber] = TRUE; 149 } 150 151 /* updating the cut constant if the auxiliary variable global lower bound is greater than the current constant */ 152 if( SCIPisGT(masterprob, SCIPvarGetLbGlobal(auxiliaryvar), benderscutdata->subprobconstant[probnumber]) ) 153 benderscutdata->subprobconstant[probnumber] = SCIPvarGetLbGlobal(auxiliaryvar); 154 } 155 156 /** computes a standard Benders' optimality cut from the dual solutions of the LP */ 157 static 158 SCIP_RETCODE computeStandardIntegerOptCut( 159 SCIP* masterprob, /**< the SCIP instance of the master problem */ 160 SCIP_BENDERS* benders, /**< the benders' decomposition structure */ 161 SCIP_SOL* sol, /**< primal CIP solution */ 162 SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */ 163 SCIP_ROW* row, /**< the row for the generated cut, can be NULL */ 164 SCIP_Real cutconstant, /**< the constant value in the integer optimality cut */ 165 int probnumber, /**< the number of the pricing problem */ 166 SCIP_Bool addcut, /**< indicates whether a cut is created instead of a constraint */ 167 SCIP_Bool* success /**< was the cut generation successful? */ 168 ) 169 { 170 SCIP_VAR** vars; 171 int nvars; 172 SCIP_Real subprobobj; /* the objective function value of the subproblem */ 173 SCIP_Real lhs; /* the left hand side of the cut */ 174 int i; 175 SCIPdebug( SCIP* subproblem; ) 176 177 #ifndef NDEBUG 178 SCIP_Real verifyobj = 0; 179 #endif 180 181 assert(masterprob != NULL); 182 assert(benders != NULL); 183 assert(cons != NULL || addcut); 184 assert(row != NULL || !addcut); 185 186 (*success) = FALSE; 187 188 /* getting the best solution from the subproblem */ 189 190 subprobobj = SCIPbendersGetSubproblemObjval(benders, probnumber); 191 192 SCIPdebug( subproblem = SCIPbendersSubproblem(benders, probnumber); ) 193 SCIPdebug( SCIPdebugMsg(masterprob, "Subproblem %d - Objective Value: Stored - %g Orig Obj - %g Cut constant - %g\n", 194 probnumber, SCIPbendersGetSubproblemObjval(benders, probnumber), SCIPgetSolOrigObj(subproblem, SCIPgetBestSol(subproblem))*(int)SCIPgetObjsense(subproblem), 195 cutconstant); ) 196 197 nvars = SCIPgetNVars(masterprob); 198 vars = SCIPgetVars(masterprob); 199 200 /* adding the subproblem objective function value to the lhs */ 201 if( addcut ) 202 lhs = SCIProwGetLhs(row); 203 else 204 lhs = SCIPgetLhsLinear(masterprob, cons); 205 206 /* looping over all master problem variables to update the coefficients in the computed cut. */ 207 for( i = 0; i < nvars; i++ ) 208 { 209 SCIP_VAR* subprobvar; 210 SCIP_Real coef; 211 212 SCIP_CALL( SCIPgetBendersSubproblemVar(masterprob, benders, vars[i], &subprobvar, probnumber) ); 213 214 /* if there is a corresponding subproblem variable, then the variable will not be NULL. */ 215 if( subprobvar != NULL ) 216 { 217 /* if the variable is on its upper bound, then the subproblem objective value is added to the cut */ 218 if( SCIPisFeasEQ(masterprob, SCIPgetSolVal(masterprob, sol, vars[i]), 1.0) ) 219 { 220 coef = -(subprobobj - cutconstant); 221 lhs -= (subprobobj - cutconstant); 222 } 223 else 224 coef = (subprobobj - cutconstant); 225 226 /* adding the variable to the cut. The coefficient is the subproblem objective value */ 227 if( addcut ) 228 { 229 SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[i], coef) ); 230 } 231 else 232 { 233 SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[i], coef) ); 234 } 235 } 236 } 237 238 lhs += subprobobj; 239 240 /* if the bound becomes infinite, then the cut generation terminates. */ 241 if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs) ) 242 { 243 (*success) = FALSE; 244 SCIPdebugMsg(masterprob, "Infinite bound when generating integer optimality cut.\n"); 245 return SCIP_OKAY; 246 } 247 248 /* Update the lhs of the cut */ 249 if( addcut ) 250 { 251 SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) ); 252 } 253 else 254 { 255 SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) ); 256 } 257 258 #ifndef NDEBUG 259 if( addcut ) 260 lhs = SCIProwGetLhs(row); 261 else 262 lhs = SCIPgetLhsLinear(masterprob, cons); 263 verifyobj += lhs; 264 265 if( addcut ) 266 verifyobj -= SCIPgetRowSolActivity(masterprob, row, sol); 267 else 268 verifyobj -= SCIPgetActivityLinear(masterprob, cons, sol); 269 #endif 270 271 assert(SCIPisFeasEQ(masterprob, verifyobj, subprobobj)); 272 273 (*success) = TRUE; 274 275 return SCIP_OKAY; 276 } 277 278 279 /** adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the 280 * auxiliary variable is first created and added to the master problem. 281 */ 282 static 283 SCIP_RETCODE addAuxiliaryVariableToCut( 284 SCIP* masterprob, /**< the SCIP instance of the master problem */ 285 SCIP_BENDERS* benders, /**< the benders' decomposition structure */ 286 SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */ 287 SCIP_ROW* row, /**< the row for the generated cut, can be NULL */ 288 int probnumber, /**< the number of the pricing problem */ 289 SCIP_Bool addcut /**< indicates whether a cut is created instead of a constraint */ 290 ) 291 { 292 SCIP_VAR* auxiliaryvar; 293 294 assert(masterprob != NULL); 295 assert(benders != NULL); 296 assert(cons != NULL || addcut); 297 assert(row != NULL || !addcut); 298 299 auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, probnumber); 300 301 /* adding the auxiliary variable to the generated cut */ 302 if( addcut ) 303 { 304 SCIP_CALL( SCIPaddVarToRow(masterprob, row, auxiliaryvar, 1.0) ); 305 } 306 else 307 { 308 SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, auxiliaryvar, 1.0) ); 309 } 310 311 return SCIP_OKAY; 312 } 313 314 315 /** generates and applies Benders' cuts */ 316 static 317 SCIP_RETCODE generateAndApplyBendersIntegerCuts( 318 SCIP* masterprob, /**< the SCIP instance of the master problem */ 319 SCIP_BENDERS* benders, /**< the benders' decomposition */ 320 SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */ 321 SCIP_SOL* sol, /**< primal CIP solution */ 322 int probnumber, /**< the number of the pricing problem */ 323 SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */ 324 SCIP_RESULT* result, /**< the result from solving the subproblems */ 325 SCIP_Bool initcons /**< is this function called to generate the initial constraint */ 326 ) 327 { 328 SCIP_BENDERSCUTDATA* benderscutdata; 329 SCIP_CONSHDLR* consbenders; 330 SCIP_CONS* cons; 331 SCIP_ROW* row; 332 char cutname[SCIP_MAXSTRLEN]; 333 SCIP_Bool optimal; 334 SCIP_Bool addcut; 335 SCIP_Bool success; 336 337 assert(masterprob != NULL); 338 assert(benders != NULL); 339 assert(benderscut != NULL); 340 assert(result != NULL); 341 342 row = NULL; 343 cons = NULL; 344 345 success = FALSE; 346 347 /* retrieving the Benders' cut data */ 348 benderscutdata = SCIPbenderscutGetData(benderscut); 349 350 /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be added 351 * to the master problem. 352 */ 353 if( SCIPgetStage(masterprob) < SCIP_STAGE_INITSOLVE ) 354 addcut = FALSE; 355 else 356 addcut = benderscutdata->addcuts; 357 358 /* retrieving the Benders' decomposition constraint handler */ 359 consbenders = SCIPfindConshdlr(masterprob, "benders"); 360 361 /* checking the optimality of the original problem with a comparison between the auxiliary variable and the 362 * objective value of the subproblem 363 */ 364 optimal = FALSE; 365 SCIP_CALL( SCIPcheckBendersSubproblemOptimality(masterprob, benders, sol, probnumber, &optimal) ); 366 367 if( optimal ) 368 { 369 (*result) = SCIP_FEASIBLE; 370 SCIPdebugMsg(masterprob, "No <%s> cut added. Current Master Problem Obj: %g\n", BENDERSCUT_NAME, 371 SCIPgetSolOrigObj(masterprob, NULL)*(int)SCIPgetObjsense(masterprob)); 372 return SCIP_OKAY; 373 } 374 375 /* checking whether the subproblem constant is less than the auxiliary variable global lower bound */ 376 updateSubproblemCutConstant(masterprob, benders, benderscutdata, probnumber); 377 378 /* if no integer cuts have been previously generated and the bound on the auxiliary variable is -infinity, 379 * then an initial lower bounding cut is added 380 */ 381 if( benderscutdata->firstcut[probnumber] 382 && SCIPisInfinity(masterprob, -SCIPvarGetLbGlobal(SCIPbendersGetAuxiliaryVar(benders, probnumber))) ) 383 { 384 benderscutdata->firstcut[probnumber] = FALSE; 385 SCIP_CALL( generateAndApplyBendersIntegerCuts(masterprob, benders, benderscut, sol, probnumber, type, result, 386 TRUE) ); 387 } 388 389 /* setting the name of the generated cut */ 390 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "integeroptcut_%d_%" SCIP_LONGINT_FORMAT, probnumber, 391 SCIPbenderscutGetNFound(benderscut) ); 392 393 /* creating an empty row or constraint for the Benders' cut */ 394 if( addcut ) 395 { 396 SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE, 397 FALSE, TRUE) ); 398 } 399 else 400 { 401 SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) ); 402 SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) ); 403 SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) ); 404 } 405 406 if( initcons ) 407 { 408 SCIP_Real lhs; 409 410 /* adding the subproblem objective function value to the lhs */ 411 if( addcut ) 412 lhs = SCIProwGetLhs(row); 413 else 414 lhs = SCIPgetLhsLinear(masterprob, cons); 415 416 lhs += benderscutdata->subprobconstant[probnumber]; 417 418 /* if the bound becomes infinite, then the cut generation terminates. */ 419 if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs) ) 420 { 421 success = FALSE; 422 SCIPdebugMsg(masterprob, "Infinite bound when generating integer optimality cut.\n"); 423 } 424 425 /* Update the lhs of the cut */ 426 if( addcut ) 427 { 428 SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) ); 429 } 430 else 431 { 432 SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) ); 433 } 434 } 435 else 436 { 437 /* computing the coefficients of the optimality cut */ 438 SCIP_CALL( computeStandardIntegerOptCut(masterprob, benders, sol, cons, row, 439 benderscutdata->subprobconstant[probnumber], probnumber, addcut, &success) ); 440 } 441 442 /* if success is FALSE, then there was an error in generating the integer optimality cut. No cut will be added to 443 * the master problem. Otherwise, the constraint is added to the master problem. 444 */ 445 if( !success ) 446 { 447 (*result) = SCIP_DIDNOTFIND; 448 SCIPdebugMsg(masterprob, "Error in generating Benders' integer optimality cut for problem %d.\n", probnumber); 449 } 450 else 451 { 452 /* adding the auxiliary variable to the optimality cut */ 453 SCIP_CALL( addAuxiliaryVariableToCut(masterprob, benders, cons, row, probnumber, addcut) ); 454 455 /* adding the constraint to the master problem */ 456 if( addcut ) 457 { 458 SCIP_Bool infeasible; 459 460 if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX ) 461 { 462 SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) ); 463 assert(!infeasible); 464 } 465 else 466 { 467 assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO); 468 SCIP_CALL( SCIPaddPoolCut(masterprob, row) ); 469 } 470 471 #ifdef SCIP_DEBUG 472 SCIP_CALL( SCIPprintRow(masterprob, row, NULL) ); 473 SCIPinfoMessage(masterprob, NULL, ";\n"); 474 #endif 475 476 (*result) = SCIP_SEPARATED; 477 } 478 else 479 { 480 SCIP_CALL( SCIPaddCons(masterprob, cons) ); 481 482 SCIPdebugPrintCons(masterprob, cons, NULL); 483 484 (*result) = SCIP_CONSADDED; 485 } 486 } 487 488 if( addcut ) 489 { 490 /* release the row */ 491 SCIP_CALL( SCIPreleaseRow(masterprob, &row) ); 492 } 493 else 494 { 495 /* release the constraint */ 496 SCIP_CALL( SCIPreleaseCons(masterprob, &cons) ); 497 } 498 499 return SCIP_OKAY; 500 } 501 502 /* 503 * Callback methods of Benders' decomposition cuts 504 */ 505 506 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */ 507 static 508 SCIP_DECL_BENDERSCUTFREE(benderscutFreeInt) 509 { /*lint --e{715}*/ 510 SCIP_BENDERSCUTDATA* benderscutdata; 511 512 assert( benderscut != NULL ); 513 assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 ); 514 515 /* free Benders' cut data */ 516 benderscutdata = SCIPbenderscutGetData(benderscut); 517 assert( benderscutdata != NULL ); 518 519 SCIPfreeBlockMemory(scip, &benderscutdata); 520 521 SCIPbenderscutSetData(benderscut, NULL); 522 523 return SCIP_OKAY; 524 } 525 526 527 /** initialization method of Benders' decomposition cuts (called after problem was transformed) */ 528 static 529 SCIP_DECL_BENDERSCUTINIT(benderscutInitInt) 530 { /*lint --e{715}*/ 531 SCIP_BENDERSCUTDATA* benderscutdata; 532 533 assert( benderscut != NULL ); 534 assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 ); 535 536 /* free Benders' cut data */ 537 benderscutdata = SCIPbenderscutGetData(benderscut); 538 assert( benderscutdata != NULL ); 539 540 benderscutdata->nsubproblems = SCIPbendersGetNSubproblems(benderscutdata->benders); 541 SCIP_CALL( createBenderscutData(scip, benderscutdata) ); 542 543 return SCIP_OKAY; 544 } 545 546 /** deinitialization method of Benders' decomposition cuts (called before transformed problem is freed) */ 547 static 548 SCIP_DECL_BENDERSCUTEXIT(benderscutExitInt) 549 { /*lint --e{715}*/ 550 SCIP_BENDERSCUTDATA* benderscutdata; 551 552 assert( benderscut != NULL ); 553 assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 ); 554 555 /* free Benders' cut data */ 556 benderscutdata = SCIPbenderscutGetData(benderscut); 557 assert( benderscutdata != NULL ); 558 559 SCIPfreeBlockMemoryArray(scip, &benderscutdata->firstcut, benderscutdata->nsubproblems); 560 SCIPfreeBlockMemoryArray(scip, &benderscutdata->subprobconstant, benderscutdata->nsubproblems); 561 562 return SCIP_OKAY; 563 } 564 565 /** execution method of Benders' decomposition cuts */ 566 static 567 SCIP_DECL_BENDERSCUTEXEC(benderscutExecInt) 568 { /*lint --e{715}*/ 569 SCIP* subproblem; 570 571 assert(scip != NULL); 572 assert(benders != NULL); 573 assert(benderscut != NULL); 574 assert(result != NULL); 575 576 subproblem = SCIPbendersSubproblem(benders, probnumber); 577 578 if( subproblem == NULL ) 579 { 580 SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n", 581 probnumber, BENDERSCUT_NAME); 582 583 (*result) = SCIP_DIDNOTRUN; 584 return SCIP_OKAY; 585 } 586 587 /* it is only possible to generate the Laporte and Louveaux cuts for pure binary master problems */ 588 if( SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders)) 589 && (!SCIPbendersMasterIsNonlinear(benders) 590 || SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders) - 1)) ) 591 { 592 SCIPinfoMessage(scip, NULL, "The integer optimality cuts can only be applied to problems with a " 593 "pure binary master problem. The integer optimality cuts will be disabled.\n"); 594 595 SCIPbenderscutSetEnabled(benderscut, FALSE); 596 597 return SCIP_OKAY; 598 } 599 600 /* the integer subproblem could terminate early if the auxiliary variable value is much greater than the optimal 601 * solution. As such, it is only necessary to generate a cut if the subproblem is OPTIMAL */ 602 if( SCIPgetStatus(subproblem) == SCIP_STATUS_OPTIMAL ) 603 { 604 /* generating a cut for a given subproblem */ 605 SCIP_CALL( generateAndApplyBendersIntegerCuts(scip, benders, benderscut, sol, probnumber, type, result, FALSE) ); 606 } 607 608 return SCIP_OKAY; 609 } 610 611 612 /* 613 * Benders' decomposition cuts specific interface methods 614 */ 615 616 /** creates the int Benders' decomposition cuts and includes it in SCIP */ 617 SCIP_RETCODE SCIPincludeBenderscutInt( 618 SCIP* scip, /**< SCIP data structure */ 619 SCIP_BENDERS* benders /**< Benders' decomposition */ 620 ) 621 { 622 SCIP_BENDERSCUTDATA* benderscutdata; 623 SCIP_BENDERSCUT* benderscut; 624 char paramname[SCIP_MAXSTRLEN]; 625 626 assert(benders != NULL); 627 628 /* create int Benders' decomposition cuts data */ 629 SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) ); 630 benderscutdata->benders = benders; 631 632 benderscut = NULL; 633 634 /* include Benders' decomposition cuts */ 635 SCIP_CALL( SCIPincludeBenderscutBasic(scip, benders, &benderscut, BENDERSCUT_NAME, BENDERSCUT_DESC, 636 BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecInt, benderscutdata) ); 637 638 assert(benderscut != NULL); 639 640 /* set non fundamental callbacks via setter functions */ 641 SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeInt) ); 642 SCIP_CALL( SCIPsetBenderscutInit(scip, benderscut, benderscutInitInt) ); 643 SCIP_CALL( SCIPsetBenderscutExit(scip, benderscut, benderscutExitInt) ); 644 645 /* add int Benders' decomposition cuts parameters */ 646 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/cutsconstant", 647 SCIPbendersGetName(benders), BENDERSCUT_NAME); 648 SCIP_CALL( SCIPaddRealParam(scip, paramname, 649 "the constant term of the integer Benders' cuts.", 650 &benderscutdata->cutconstant, FALSE, SCIP_DEFAULT_CUTCONSTANT, -SCIPinfinity(scip), SCIPinfinity(scip), 651 paramChgdBenderscutintConstant, (SCIP_PARAMDATA*)benderscutdata) ); 652 653 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts", 654 SCIPbendersGetName(benders), BENDERSCUT_NAME); 655 SCIP_CALL( SCIPaddBoolParam(scip, paramname, 656 "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.", 657 &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) ); 658 659 return SCIP_OKAY; 660 } 661