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_nogood.c 26 * @ingroup OTHER_CFILES 27 * @brief Generates a no good cut for integer solutions that are infeasible for the subproblems 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_nogood.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_var.h" 41 #include "scip/scip_benders.h" 42 #include "scip/scip_cons.h" 43 #include "scip/scip_cut.h" 44 #include "scip/scip_general.h" 45 #include "scip/scip_lp.h" 46 #include "scip/scip_mem.h" 47 #include "scip/scip_message.h" 48 #include "scip/scip_numerics.h" 49 #include "scip/scip_param.h" 50 #include "scip/scip_prob.h" 51 #include "scip/scip_sol.h" 52 #include <string.h> 53 54 #define BENDERSCUT_NAME "nogood" 55 #define BENDERSCUT_DESC "no good Benders' decomposition integer cut" 56 #define BENDERSCUT_PRIORITY 500 57 #define BENDERSCUT_LPCUT FALSE 58 59 60 61 #define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */ 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 int curriter; /**< the current Benders' decomposition subproblem solve iteration */ 72 SCIP_Bool addcuts; /**< should cuts be generated instead of constraints */ 73 SCIP_Bool cutadded; /**< has a cut been added in the current iteration. Only one cut per round */ 74 }; 75 76 77 /* 78 * Local methods 79 */ 80 81 /** compute no good cut */ 82 static 83 SCIP_RETCODE computeNogoodCut( 84 SCIP* masterprob, /**< the SCIP instance of the master problem */ 85 SCIP_BENDERS* benders, /**< the benders' decomposition structure */ 86 SCIP_SOL* sol, /**< primal CIP solution */ 87 SCIP_CONS* cons, /**< the constraint for the generated cut, can be NULL */ 88 SCIP_ROW* row, /**< the row for the generated cut, can be NULL */ 89 SCIP_Bool addcut /**< indicates whether a cut is created instead of a constraint */ 90 ) 91 { 92 SCIP_VAR** vars; 93 int nvars; 94 SCIP_Real lhs; 95 int i; 96 #ifndef NDEBUG 97 SCIP_Real verifycons; 98 #endif 99 100 assert(masterprob != NULL); 101 assert(benders != NULL); 102 assert(cons != NULL || addcut); 103 assert(row != NULL || !addcut); 104 105 nvars = SCIPgetNVars(masterprob); 106 vars = SCIPgetVars(masterprob); 107 108 /* adding the subproblem objective function value to the lhs */ 109 if( addcut ) 110 lhs = SCIProwGetLhs(row); 111 else 112 lhs = SCIPgetLhsLinear(masterprob, cons); 113 114 /* adding the violation to the lhs */ 115 lhs += 1.0; 116 117 /* looping over all master problem variables to update the coefficients in the computed cut. */ 118 for( i = 0; i < nvars; i++ ) 119 { 120 SCIP_Real coef; 121 122 if( !SCIPvarIsBinary(vars[i]) ) 123 continue; 124 125 /* if the variable is on its upper bound, then the subproblem objective value is added to the cut */ 126 if( SCIPisFeasEQ(masterprob, SCIPgetSolVal(masterprob, sol, vars[i]), 1.0) ) 127 { 128 coef = -1.0; 129 lhs -= 1.0; 130 } 131 else 132 coef = 1.0; 133 134 /* adding the variable to the cut. The coefficient is the subproblem objective value */ 135 if( addcut ) 136 { 137 SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[i], coef) ); 138 } 139 else 140 { 141 SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[i], coef) ); 142 } 143 } 144 145 /* Update the lhs of the cut */ 146 if( addcut ) 147 { 148 SCIP_CALL( SCIPchgRowLhs(masterprob, row, lhs) ); 149 } 150 else 151 { 152 SCIP_CALL( SCIPchgLhsLinear(masterprob, cons, lhs) ); 153 } 154 155 #ifndef NDEBUG 156 if( addcut ) 157 verifycons = SCIPgetRowSolActivity(masterprob, row, sol); 158 else 159 verifycons = SCIPgetActivityLinear(masterprob, cons, sol); 160 #endif 161 162 assert(SCIPisFeasEQ(masterprob, verifycons, lhs - 1)); 163 164 return SCIP_OKAY; 165 } 166 167 168 169 /** generates and applies Benders' cuts */ 170 static 171 SCIP_RETCODE generateAndApplyBendersNogoodCut( 172 SCIP* masterprob, /**< the SCIP instance of the master problem */ 173 SCIP_BENDERS* benders, /**< the benders' decomposition */ 174 SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */ 175 SCIP_SOL* sol, /**< primal CIP solution */ 176 SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */ 177 SCIP_RESULT* result /**< the result from solving the subproblems */ 178 ) 179 { 180 SCIP_BENDERSCUTDATA* benderscutdata; 181 SCIP_CONSHDLR* consbenders; 182 SCIP_CONS* cons; 183 SCIP_ROW* row; 184 char cutname[SCIP_MAXSTRLEN]; 185 SCIP_Bool addcut; 186 187 assert(masterprob != NULL); 188 assert(benders != NULL); 189 assert(benderscut != NULL); 190 assert(result != NULL); 191 192 row = NULL; 193 cons = NULL; 194 195 /* retrieving the Benders' cut data */ 196 benderscutdata = SCIPbenderscutGetData(benderscut); 197 198 /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be 199 * added to the master problem. 200 */ 201 if( SCIPgetStage(masterprob) < SCIP_STAGE_INITSOLVE ) 202 addcut = FALSE; 203 else 204 addcut = benderscutdata->addcuts; 205 206 /* retrieving the Benders' decomposition constraint handler */ 207 consbenders = SCIPfindConshdlr(masterprob, "benders"); 208 209 /* setting the name of the generated cut */ 210 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "nogoodcut_%" SCIP_LONGINT_FORMAT, SCIPbenderscutGetNFound(benderscut) ); 211 212 /* creating an empty row or constraint for the Benders' cut */ 213 if( addcut ) 214 { 215 SCIP_CALL( SCIPcreateEmptyRowConshdlr(masterprob, &row, consbenders, cutname, 0.0, SCIPinfinity(masterprob), FALSE, 216 FALSE, TRUE) ); 217 } 218 else 219 { 220 SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) ); 221 SCIP_CALL( SCIPsetConsDynamic(masterprob, cons, TRUE) ); 222 SCIP_CALL( SCIPsetConsRemovable(masterprob, cons, TRUE) ); 223 } 224 225 /* computing the coefficients of the optimality cut */ 226 SCIP_CALL( computeNogoodCut(masterprob, benders, sol, cons, row, addcut) ); 227 228 /* adding the constraint to the master problem */ 229 if( addcut ) 230 { 231 SCIP_Bool infeasible; 232 233 if( type == SCIP_BENDERSENFOTYPE_LP || type == SCIP_BENDERSENFOTYPE_RELAX ) 234 { 235 SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) ); 236 assert(!infeasible); 237 } 238 else 239 { 240 assert(type == SCIP_BENDERSENFOTYPE_CHECK || type == SCIP_BENDERSENFOTYPE_PSEUDO); 241 SCIP_CALL( SCIPaddPoolCut(masterprob, row) ); 242 } 243 244 #ifdef SCIP_DEBUG 245 SCIP_CALL( SCIPprintRow(masterprob, row, NULL) ); 246 SCIPinfoMessage(masterprob, NULL, ";\n"); 247 #endif 248 249 /* release the row */ 250 SCIP_CALL( SCIPreleaseRow(masterprob, &row) ); 251 252 (*result) = SCIP_SEPARATED; 253 } 254 else 255 { 256 SCIP_CALL( SCIPaddCons(masterprob, cons) ); 257 258 SCIPdebugPrintCons(masterprob, cons, NULL); 259 260 SCIP_CALL( SCIPreleaseCons(masterprob, &cons) ); 261 262 (*result) = SCIP_CONSADDED; 263 } 264 265 /* updating the cut added flag */ 266 benderscutdata->cutadded = TRUE; 267 268 return SCIP_OKAY; 269 } 270 271 /* 272 * Callback methods of Benders' decomposition cuts 273 */ 274 275 /** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */ 276 static 277 SCIP_DECL_BENDERSCUTFREE(benderscutFreeNogood) 278 { /*lint --e{715}*/ 279 SCIP_BENDERSCUTDATA* benderscutdata; 280 281 assert( benderscut != NULL ); 282 assert( strcmp(SCIPbenderscutGetName(benderscut), BENDERSCUT_NAME) == 0 ); 283 284 /* free Benders' cut data */ 285 benderscutdata = SCIPbenderscutGetData(benderscut); 286 assert( benderscutdata != NULL ); 287 288 SCIPfreeBlockMemory(scip, &benderscutdata); 289 290 SCIPbenderscutSetData(benderscut, NULL); 291 292 return SCIP_OKAY; 293 } 294 295 296 /** execution method of Benders' decomposition cuts */ 297 static 298 SCIP_DECL_BENDERSCUTEXEC(benderscutExecNogood) 299 { /*lint --e{715}*/ 300 SCIP* subproblem; 301 SCIP_BENDERSCUTDATA* benderscutdata; 302 303 assert(scip != NULL); 304 assert(benders != NULL); 305 assert(benderscut != NULL); 306 assert(result != NULL); 307 308 subproblem = SCIPbendersSubproblem(benders, probnumber); 309 310 if( subproblem == NULL ) 311 { 312 SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n", 313 probnumber, BENDERSCUT_NAME); 314 315 (*result) = SCIP_DIDNOTRUN; 316 return SCIP_OKAY; 317 } 318 319 benderscutdata = SCIPbenderscutGetData(benderscut); 320 assert(benderscutdata != NULL); 321 322 /* if the curriter is less than the number of Benders' decomposition calls, then we are in a new round. 323 * So the cutadded flag must be set to FALSE 324 */ 325 if( benderscutdata->curriter < SCIPbendersGetNCalls(benders) ) 326 { 327 benderscutdata->curriter = SCIPbendersGetNCalls(benders); 328 benderscutdata->cutadded = FALSE; 329 } 330 331 /* if a cut has been added in this Benders' decomposition call, then no more must be added */ 332 if( benderscutdata->cutadded ) 333 return SCIP_OKAY; 334 335 /* it is only possible to generate the no-good cut for pure binary master problems */ 336 if( SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders)) 337 && (!SCIPbendersMasterIsNonlinear(benders) 338 || SCIPgetNBinVars(scip) != (SCIPgetNVars(scip) - SCIPbendersGetNSubproblems(benders) - 1)) ) 339 { 340 SCIPinfoMessage(scip, NULL, "The no-good cuts can only be applied to problems with a pure binary master problem. " 341 "The no-good Benders' decomposition cuts will be disabled.\n"); 342 343 SCIPbenderscutSetEnabled(benderscut, FALSE); 344 345 return SCIP_OKAY; 346 } 347 348 /* We can not rely on complete recourse for the subproblems. As such, the subproblems may be feasible for the LP, but 349 * infeasible for the IP. As such, if one subproblem is infeasible, then a no good cut is generated. 350 */ 351 if( SCIPgetStatus(subproblem) == SCIP_STATUS_INFEASIBLE ) 352 { 353 /* generating a cut */ 354 SCIP_CALL( generateAndApplyBendersNogoodCut(scip, benders, benderscut, sol, type, result) ); 355 } 356 357 return SCIP_OKAY; 358 } 359 360 361 /* 362 * Benders' decomposition cuts specific interface methods 363 */ 364 365 /** creates the nogood Benders' decomposition cuts and includes it in SCIP */ 366 SCIP_RETCODE SCIPincludeBenderscutNogood( 367 SCIP* scip, /**< SCIP data structure */ 368 SCIP_BENDERS* benders /**< Benders' decomposition */ 369 ) 370 { 371 SCIP_BENDERSCUTDATA* benderscutdata; 372 SCIP_BENDERSCUT* benderscut; 373 char paramname[SCIP_MAXSTRLEN]; 374 375 assert(benders != NULL); 376 377 /* create nogood Benders' decomposition cuts data */ 378 SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) ); 379 benderscutdata->benders = benders; 380 benderscutdata->curriter = -1; 381 benderscutdata->cutadded = FALSE; 382 383 benderscut = NULL; 384 385 /* include Benders' decomposition cuts */ 386 SCIP_CALL( SCIPincludeBenderscutBasic(scip, benders, &benderscut, BENDERSCUT_NAME, BENDERSCUT_DESC, 387 BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecNogood, benderscutdata) ); 388 389 assert(benderscut != NULL); 390 391 /* set non fundamental callbacks via setter functions */ 392 SCIP_CALL( SCIPsetBenderscutFree(scip, benderscut, benderscutFreeNogood) ); 393 394 /* add nogood Benders' decomposition cuts parameters */ 395 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts", 396 SCIPbendersGetName(benders), BENDERSCUT_NAME); 397 SCIP_CALL( SCIPaddBoolParam(scip, paramname, 398 "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.", 399 &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) ); 400 401 return SCIP_OKAY; 402 } 403