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 scip_benders.c 26 * @ingroup OTHER_CFILES 27 * @brief public methods for Benders decomposition 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Gerald Gamrath 31 * @author Leona Gottwald 32 * @author Stefan Heinz 33 * @author Gregor Hendel 34 * @author Thorsten Koch 35 * @author Alexander Martin 36 * @author Marc Pfetsch 37 * @author Michael Winkler 38 * @author Kati Wolter 39 * 40 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #include "scip/benderscut.h" 46 #include "scip/benders.h" 47 #include "scip/cons_linear.h" 48 #include "scip/debug.h" 49 #include "scip/dcmp.h" 50 #include "scip/pub_benders.h" 51 #include "scip/pub_message.h" 52 #include "scip/pub_misc.h" 53 #include "scip/scip.h" 54 #include "scip/scip_message.h" 55 #include "scip/set.h" 56 #include "scip/struct_mem.h" 57 #include "scip/struct_scip.h" 58 #include "scip/struct_set.h" 59 60 /** creates a Benders' decomposition and includes it in SCIP 61 * 62 * To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders(). 63 * This should be done during the problem creation stage. 64 * 65 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 66 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 67 * 68 * @pre This method can be called if SCIP is in one of the following stages: 69 * - \ref SCIP_STAGE_INIT 70 * - \ref SCIP_STAGE_PROBLEM 71 * 72 * @note method has all Benders' decomposition callbacks as arguments and is thus changed every time a new callback is 73 * added in future releases; consider using SCIPincludeBendersBasic() and setter functions 74 * if you seek for a method which is less likely to change in future releases 75 */ 76 SCIP_RETCODE SCIPincludeBenders( 77 SCIP* scip, /**< SCIP data structure */ 78 const char* name, /**< name of Benders' decomposition */ 79 const char* desc, /**< description of Benders' decomposition */ 80 int priority, /**< priority of the Benders' decomposition */ 81 SCIP_Bool cutlp, /**< should Benders' cuts be generated for LP solutions */ 82 SCIP_Bool cutpseudo, /**< should Benders' cuts be generated for pseudo solutions */ 83 SCIP_Bool cutrelax, /**< should Benders' cuts be generated for relaxation solutions */ 84 SCIP_Bool shareauxvars, /**< should this Benders' use the highest priority Benders aux vars */ 85 SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */ 86 SCIP_DECL_BENDERSFREE ((*bendersfree)), /**< destructor of Benders' decomposition */ 87 SCIP_DECL_BENDERSINIT ((*bendersinit)), /**< initialize Benders' decomposition */ 88 SCIP_DECL_BENDERSEXIT ((*bendersexit)), /**< deinitialize Benders' decomposition */ 89 SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */ 90 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */ 91 SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */ 92 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */ 93 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */ 94 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */ 95 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< the execution method of the Benders' decomposition algorithm */ 96 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */ 97 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */ 98 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */ 99 SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */ 100 SCIP_BENDERSDATA* bendersdata /**< Benders' decomposition data */ 101 ) 102 { 103 SCIP_BENDERS* benders; 104 105 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBenders", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 106 107 /* check whether pricer is already present */ 108 if( SCIPfindBenders(scip, name) != NULL ) 109 { 110 SCIPerrorMessage("benders <%s> already included.\n", name); 111 return SCIP_INVALIDDATA; 112 } 113 114 /* Checking whether the benderssolvesub and the bendersfreesub are both implemented or both are not implemented */ 115 if( (benderssolvesubconvex == NULL && benderssolvesub == NULL && bendersfreesub != NULL) 116 || ((benderssolvesubconvex != NULL || benderssolvesub != NULL) && bendersfreesub == NULL) ) 117 { 118 SCIPerrorMessage("Benders' decomposition <%s> requires that if bendersFreesub%s is " 119 "implemented at least one of bendersSolvesubconvex%s or bendersSolvesub%s are implemented, " 120 "or if bendersFreesub%s is not implemented, then none are implented.\n", name, name, name, name, name); 121 return SCIP_INVALIDCALL; 122 } 123 124 SCIP_CALL( SCIPbendersCreate(&benders, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, 125 cutlp, cutpseudo, cutrelax, shareauxvars, benderscopy, bendersfree, bendersinit, bendersexit, bendersinitpre, 126 bendersexitpre, bendersinitsol, bendersexitsol, bendersgetvar, benderscreatesub, benderspresubsolve, 127 benderssolvesubconvex, benderssolvesub, benderspostsolve, bendersfreesub, bendersdata) ); 128 SCIP_CALL( SCIPsetIncludeBenders(scip->set, benders) ); 129 130 return SCIP_OKAY; 131 } 132 133 /** creates a Benders' decomposition and includes it in SCIP with all non-fundamental callbacks set to NULL 134 * 135 * If needed, the non-fundamental callbacks can be added afterwards via setter functions SCIPsetBendersCopy(), 136 * SCIPsetBendersFree(), SCIPsetBendersInity(), SCIPsetBendersExit(), SCIPsetBendersInitsol(), SCIPsetBendersExitsol(), 137 * SCIPsetBendersFarkas(). 138 * 139 * To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders(). 140 * This should be done during the problem creation stage. 141 * 142 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 143 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 144 * 145 * @pre This method can be called if SCIP is in one of the following stages: 146 * - \ref SCIP_STAGE_INIT 147 * - \ref SCIP_STAGE_PROBLEM 148 * 149 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBenders() instead 150 */ 151 SCIP_RETCODE SCIPincludeBendersBasic( 152 SCIP* scip, /**< SCIP data structure */ 153 SCIP_BENDERS** bendersptr, /**< reference to a benders, or NULL */ 154 const char* name, /**< name of Benders' decomposition */ 155 const char* desc, /**< description of Benders' decomposition */ 156 int priority, /**< priority of the Benders' decomposition */ 157 SCIP_Bool cutlp, /**< should Benders' cuts be generated for LP solutions */ 158 SCIP_Bool cutpseudo, /**< should Benders' cuts be generated for pseudo solutions */ 159 SCIP_Bool cutrelax, /**< should Benders' cuts be generated for relaxation solutions */ 160 SCIP_Bool shareauxvars, /**< should this Benders' use the highest priority Benders aux vars */ 161 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */ 162 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */ 163 SCIP_BENDERSDATA* bendersdata /**< Benders' decomposition data */ 164 ) 165 { 166 SCIP_BENDERS* benders; 167 168 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBendersBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 169 170 /* check whether Benders' decomposition is already present */ 171 if( SCIPfindBenders(scip, name) != NULL ) 172 { 173 SCIPerrorMessage("benders <%s> already included.\n", name); 174 return SCIP_INVALIDDATA; 175 } 176 177 SCIP_CALL( SCIPbendersCreate(&benders, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, 178 cutlp, cutpseudo, cutrelax, shareauxvars, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, bendersgetvar, 179 benderscreatesub, NULL, NULL, NULL, NULL, NULL, bendersdata) ); 180 SCIP_CALL( SCIPsetIncludeBenders(scip->set, benders) ); 181 182 if( bendersptr != NULL ) 183 *bendersptr = benders; 184 185 return SCIP_OKAY; 186 } 187 188 /** sets copy method of benders 189 * 190 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 191 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 192 * 193 * @pre This method can be called if SCIP is in one of the following stages: 194 * - \ref SCIP_STAGE_INIT 195 * - \ref SCIP_STAGE_PROBLEM 196 */ 197 SCIP_RETCODE SCIPsetBendersCopy( 198 SCIP* scip, /**< SCIP data structure */ 199 SCIP_BENDERS* benders, /**< Benders' decomposition */ 200 SCIP_DECL_BENDERSCOPY((*benderscopy)) /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */ 201 ) 202 { 203 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 204 205 assert(benders != NULL); 206 207 SCIPbendersSetCopy(benders, benderscopy); 208 209 return SCIP_OKAY; 210 } 211 212 /** sets destructor method of benders 213 * 214 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 215 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 216 * 217 * @pre This method can be called if SCIP is in one of the following stages: 218 * - \ref SCIP_STAGE_INIT 219 * - \ref SCIP_STAGE_PROBLEM 220 */ 221 SCIP_RETCODE SCIPsetBendersFree( 222 SCIP* scip, /**< SCIP data structure */ 223 SCIP_BENDERS* benders, /**< Benders' decomposition */ 224 SCIP_DECL_BENDERSFREE((*bendersfree)) /**< destructor of Benders' decomposition */ 225 ) 226 { 227 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 228 229 assert(benders != NULL); 230 231 SCIPbendersSetFree(benders, bendersfree); 232 233 return SCIP_OKAY; 234 } 235 236 /** sets initialization method of benders 237 * 238 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 239 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 240 * 241 * @pre This method can be called if SCIP is in one of the following stages: 242 * - \ref SCIP_STAGE_INIT 243 * - \ref SCIP_STAGE_PROBLEM 244 */ 245 SCIP_RETCODE SCIPsetBendersInit( 246 SCIP* scip, /**< SCIP data structure */ 247 SCIP_BENDERS* benders, /**< Benders' decomposition */ 248 SCIP_DECL_BENDERSINIT ((*bendersinit)) /**< initialize Benders' decomposition */ 249 ) 250 { 251 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 252 253 assert(benders != NULL); 254 255 SCIPbendersSetInit(benders, bendersinit); 256 257 return SCIP_OKAY; 258 } 259 260 /** sets deinitialization method of benders 261 * 262 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 263 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 264 * 265 * @pre This method can be called if SCIP is in one of the following stages: 266 * - \ref SCIP_STAGE_INIT 267 * - \ref SCIP_STAGE_PROBLEM 268 */ 269 SCIP_RETCODE SCIPsetBendersExit( 270 SCIP* scip, /**< SCIP data structure */ 271 SCIP_BENDERS* benders, /**< Benders' decomposition */ 272 SCIP_DECL_BENDERSEXIT ((*bendersexit)) /**< deinitialize Benders' decomposition */ 273 ) 274 { 275 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 276 277 assert(benders != NULL); 278 279 SCIPbendersSetExit(benders, bendersexit); 280 281 return SCIP_OKAY; 282 } 283 284 /** sets presolving initialization method of benders 285 * 286 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 287 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 288 * 289 * @pre This method can be called if SCIP is in one of the following stages: 290 * - \ref SCIP_STAGE_INIT 291 * - \ref SCIP_STAGE_PROBLEM 292 */ 293 SCIP_RETCODE SCIPsetBendersInitpre( 294 SCIP* scip, /**< SCIP data structure */ 295 SCIP_BENDERS* benders, /**< Benders' decomposition */ 296 SCIP_DECL_BENDERSINITPRE((*bendersinitpre))/**< presolving initialization method of Benders' decomposition */ 297 ) 298 { 299 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersInitpre", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 300 301 assert(benders != NULL); 302 303 SCIPbendersSetInitpre(benders, bendersinitpre); 304 305 return SCIP_OKAY; 306 } 307 308 /** sets presolving deinitialization method of benders 309 * 310 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 311 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 312 * 313 * @pre This method can be called if SCIP is in one of the following stages: 314 * - \ref SCIP_STAGE_INIT 315 * - \ref SCIP_STAGE_PROBLEM 316 */ 317 SCIP_RETCODE SCIPsetBendersExitpre( 318 SCIP* scip, /**< SCIP data structure */ 319 SCIP_BENDERS* benders, /**< Benders' decomposition */ 320 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))/**< presolving deinitialization method of Benders' decomposition */ 321 ) 322 { 323 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersExitpre", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 324 325 assert(benders != NULL); 326 327 SCIPbendersSetExitpre(benders, bendersexitpre); 328 329 return SCIP_OKAY; 330 } 331 332 /** sets solving process initialization method of benders 333 * 334 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 335 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 336 * 337 * @pre This method can be called if SCIP is in one of the following stages: 338 * - \ref SCIP_STAGE_INIT 339 * - \ref SCIP_STAGE_PROBLEM 340 */ 341 SCIP_RETCODE SCIPsetBendersInitsol( 342 SCIP* scip, /**< SCIP data structure */ 343 SCIP_BENDERS* benders, /**< Benders' decomposition */ 344 SCIP_DECL_BENDERSINITSOL((*bendersinitsol))/**< solving process initialization method of Benders' decomposition */ 345 ) 346 { 347 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 348 349 assert(benders != NULL); 350 351 SCIPbendersSetInitsol(benders, bendersinitsol); 352 353 return SCIP_OKAY; 354 } 355 356 /** sets solving process deinitialization method of benders 357 * 358 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 359 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 360 * 361 * @pre This method can be called if SCIP is in one of the following stages: 362 * - \ref SCIP_STAGE_INIT 363 * - \ref SCIP_STAGE_PROBLEM 364 */ 365 SCIP_RETCODE SCIPsetBendersExitsol( 366 SCIP* scip, /**< SCIP data structure */ 367 SCIP_BENDERS* benders, /**< Benders' decomposition */ 368 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))/**< solving process deinitialization method of Benders' decomposition */ 369 ) 370 { 371 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 372 373 assert(benders != NULL); 374 375 SCIPbendersSetExitsol(benders, bendersexitsol); 376 377 return SCIP_OKAY; 378 } 379 380 /** sets the method called prior to solving the subproblems for benders 381 * 382 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 383 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 384 * 385 * @pre This method can be called if SCIP is in one of the following stages: 386 * - \ref SCIP_STAGE_INIT 387 * - \ref SCIP_STAGE_PROBLEM 388 */ 389 SCIP_RETCODE SCIPsetBendersPresubsolve( 390 SCIP* scip, /**< SCIP data structure */ 391 SCIP_BENDERS* benders, /**< Benders' decomposition */ 392 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))/**< method called prior to solving the subproblems */ 393 ) 394 { 395 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersPresubsolve", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 396 397 assert(benders != NULL); 398 399 SCIPbendersSetPresubsolve(benders, benderspresubsolve); 400 401 return SCIP_OKAY; 402 } 403 404 /** sets the subproblem solving and freeing methods for Benders' decomposition 405 * 406 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 407 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 408 * 409 * @pre This method can be called if SCIP is in one of the following stages: 410 * - \ref SCIP_STAGE_INIT 411 * - \ref SCIP_STAGE_PROBLEM 412 */ 413 SCIP_RETCODE SCIPsetBendersSolveAndFreesub( 414 SCIP* scip, /**< SCIP data structure */ 415 SCIP_BENDERS* benders, /**< Benders' decomposition */ 416 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */ 417 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< solving method for a Benders' decomposition subproblem */ 418 SCIP_DECL_BENDERSFREESUB((*bendersfreesub))/**< the subproblem freeing method for Benders' decomposition */ 419 ) 420 { 421 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersSolveAndFreesub", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 422 423 assert(benders != NULL); 424 425 /* Checking whether the benderssolvesub and the bendersfreesub are both implemented or both are not implemented */ 426 if( (benderssolvesubconvex == NULL && benderssolvesub == NULL && bendersfreesub != NULL) 427 || ((benderssolvesubconvex != NULL || benderssolvesub != NULL) && bendersfreesub == NULL) ) 428 { 429 SCIPerrorMessage("Benders' decomposition <%s> requires that if bendersFreesub%s is " 430 "implemented at least one of bendersSolvesubconvex%s or bendersSolvesub%s are implemented, " 431 "or if bendersFreesub%s is not implemented, then none are implented.\n", SCIPbendersGetName(benders), 432 SCIPbendersGetName(benders), SCIPbendersGetName(benders), SCIPbendersGetName(benders), 433 SCIPbendersGetName(benders)); 434 return SCIP_INVALIDCALL; 435 } 436 437 SCIPbendersSetSolvesubconvex(benders, benderssolvesubconvex); 438 SCIPbendersSetSolvesub(benders, benderssolvesub); 439 SCIPbendersSetFreesub(benders, bendersfreesub); 440 441 return SCIP_OKAY; 442 } 443 444 /** sets the post solving methods for benders 445 * 446 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 447 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 448 * 449 * @pre This method can be called if SCIP is in one of the following stages: 450 * - \ref SCIP_STAGE_INIT 451 * - \ref SCIP_STAGE_PROBLEM 452 */ 453 SCIP_RETCODE SCIPsetBendersPostsolve( 454 SCIP* scip, /**< SCIP data structure */ 455 SCIP_BENDERS* benders, /**< Benders' decomposition */ 456 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))/**< solving process deinitialization method of Benders' decomposition */ 457 ) 458 { 459 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersPostsolve", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 460 461 assert(benders != NULL); 462 463 SCIPbendersSetPostsolve(benders, benderspostsolve); 464 465 return SCIP_OKAY; 466 } 467 468 /** sets the subproblem comparison method for determining the solving order in Benders' decomposition 469 * 470 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 471 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 472 * 473 * @pre This method can be called if SCIP is in one of the following stages: 474 * - \ref SCIP_STAGE_INIT 475 * - \ref SCIP_STAGE_PROBLEM 476 */ 477 SCIP_RETCODE SCIPsetBendersSubproblemComp( 478 SCIP* scip, /**< SCIP data structure */ 479 SCIP_BENDERS* benders, /**< Benders' decomposition */ 480 SCIP_DECL_SORTPTRCOMP((*benderssubcomp)) /**< a comparator for defining the solving order of the subproblems */ 481 ) 482 { 483 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBendersSubproblemComp", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 484 485 assert(benders != NULL); 486 487 SCIPbendersSetSubproblemComp(benders, benderssubcomp); 488 489 return SCIP_OKAY; 490 } 491 492 /** returns the Benders' decomposition of the given name, or NULL if not existing */ 493 SCIP_BENDERS* SCIPfindBenders( 494 SCIP* scip, /**< SCIP data structure */ 495 const char* name /**< name of Benders' decomposition */ 496 ) 497 { 498 assert(scip != NULL); 499 assert(scip->set != NULL); 500 assert(name != NULL); 501 502 return SCIPsetFindBenders(scip->set, name); 503 } 504 505 /** returns the array of currently available Benders' decomposition; active Benders' decomposition are in the first 506 * slots of the array 507 */ 508 SCIP_BENDERS** SCIPgetBenders( 509 SCIP* scip /**< SCIP data structure */ 510 ) 511 { 512 assert(scip != NULL); 513 assert(scip->set != NULL); 514 515 SCIPsetSortBenders(scip->set); 516 517 return scip->set->benders; 518 } 519 520 /** returns the number of currently available Benders' decomposition */ 521 int SCIPgetNBenders( 522 SCIP* scip /**< SCIP data structure */ 523 ) 524 { 525 assert(scip != NULL); 526 assert(scip->set != NULL); 527 528 return scip->set->nbenders; 529 } 530 531 /** returns the number of currently active Benders' decomposition */ 532 int SCIPgetNActiveBenders( 533 SCIP* scip /**< SCIP data structure */ 534 ) 535 { 536 assert(scip != NULL); 537 assert(scip->set != NULL); 538 539 return scip->set->nactivebenders; 540 } 541 542 /** activates the Benders' decomposition to be used for the current problem 543 * 544 * This method should be called during the problem creation stage for all pricers that are necessary to solve 545 * the problem model. 546 * 547 * @note The Benders' decompositions are automatically deactivated when the problem is freed. 548 * 549 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 550 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 551 * 552 * @pre This method can be called if SCIP is in one of the following stages: 553 * - \ref SCIP_STAGE_PROBLEM 554 */ 555 SCIP_RETCODE SCIPactivateBenders( 556 SCIP* scip, /**< SCIP data structure */ 557 SCIP_BENDERS* benders, /**< the Benders' decomposition structure */ 558 int nsubproblems /**< the number of subproblems in the Benders' decomposition */ 559 ) 560 { 561 SCIP_CALL( SCIPcheckStage(scip, "SCIPactivateBenders", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 562 563 SCIP_CALL( SCIPbendersActivate(benders, scip->set, nsubproblems) ); 564 565 return SCIP_OKAY; 566 } 567 568 /** deactivates the Benders' decomposition 569 * 570 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 571 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 572 * 573 * @pre This method can be called if SCIP is in one of the following stages: 574 * - \ref SCIP_STAGE_PROBLEM 575 * - \ref SCIP_STAGE_EXITSOLVE 576 */ 577 SCIP_RETCODE SCIPdeactivateBenders( 578 SCIP* scip, /**< SCIP data structure */ 579 SCIP_BENDERS* benders /**< the Benders' decomposition structure */ 580 ) 581 { 582 SCIP_CALL( SCIPcheckStage(scip, "SCIPdeactivateBenders", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE) ); 583 584 SCIP_CALL( SCIPbendersDeactivate(benders, scip->set) ); 585 586 return SCIP_OKAY; 587 } 588 589 /** sets the priority of a Benders' decomposition */ 590 void SCIPsetBendersPriority( 591 SCIP* scip, /**< SCIP data structure */ 592 SCIP_BENDERS* benders, /**< Benders' decomposition */ 593 int priority /**< new priority of the Benders' decomposition */ 594 ) 595 { 596 assert(scip != NULL); 597 assert(scip->set != NULL); 598 assert(benders != NULL); 599 600 SCIPbendersSetPriority(benders, scip->set, priority); 601 } 602 603 /** calls the exec method of Benders' decomposition to solve the subproblems 604 * 605 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint == 606 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e. 607 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check 608 * solution feasibility. 609 * 610 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 611 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 612 * 613 * @pre This method can be called if SCIP is in one of the following stages: 614 * - \ref SCIP_STAGE_INITPRESOLVE 615 * - \ref SCIP_STAGE_PRESOLVING 616 * - \ref SCIP_STAGE_EXITPRESOLVE 617 * - \ref SCIP_STAGE_PRESOLVED 618 * - \ref SCIP_STAGE_INITSOLVE 619 * - \ref SCIP_STAGE_SOLVING 620 * - \ref SCIP_STAGE_SOLVED 621 */ 622 SCIP_RETCODE SCIPsolveBendersSubproblems( 623 SCIP* scip, /**< SCIP data structure */ 624 SCIP_BENDERS* benders, /**< Benders' decomposition */ 625 SCIP_SOL* sol, /**< primal CIP solution, can be NULL */ 626 SCIP_RESULT* result, /**< result of the pricing process */ 627 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */ 628 SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */ 629 SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */ 630 SCIP_Bool checkint /**< should the integer solution be checked by the subproblems */ 631 ) 632 { 633 assert(scip != NULL); 634 assert(scip->set != NULL); 635 assert(benders != NULL); 636 637 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveBendersSubproblems", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 638 639 SCIP_CALL( SCIPbendersExec(benders, scip->set, sol, result, infeasible, auxviol, type, checkint) ); 640 641 return SCIP_OKAY; 642 } 643 644 /** returns the master problem variable for the given subproblem variable 645 * 646 * This function is used as part of the cut generation process. 647 * 648 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 649 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 650 * 651 * @pre This method can be called if SCIP is in one of the following stages: 652 * - \ref SCIP_STAGE_INITPRESOLVE 653 * - \ref SCIP_STAGE_PRESOLVING 654 * - \ref SCIP_STAGE_EXITPRESOLVE 655 * - \ref SCIP_STAGE_PRESOLVED 656 * - \ref SCIP_STAGE_INITSOLVE 657 * - \ref SCIP_STAGE_SOLVING 658 * - \ref SCIP_STAGE_SOLVED 659 */ 660 SCIP_RETCODE SCIPgetBendersMasterVar( 661 SCIP* scip, /**< SCIP data structure */ 662 SCIP_BENDERS* benders, /**< Benders' decomposition */ 663 SCIP_VAR* var, /**< the subproblem variable */ 664 SCIP_VAR** mappedvar /**< pointer to store the master variable that var is mapped to */ 665 ) 666 { 667 assert(scip != NULL); 668 assert(scip->set != NULL); 669 assert(benders != NULL); 670 assert(var != NULL); 671 assert(mappedvar != NULL); 672 673 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetBendersMasterVar", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 674 675 SCIP_CALL( SCIPbendersGetVar(benders, scip->set, var, mappedvar, -1) ); 676 677 return SCIP_OKAY; 678 } 679 680 /** returns the subproblem problem variable for the given master variable 681 * 682 * This function is used as part of the cut generation process. 683 * 684 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 685 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 686 * 687 * @pre This method can be called if SCIP is in one of the following stages: 688 * - \ref SCIP_STAGE_INITPRESOLVE 689 * - \ref SCIP_STAGE_PRESOLVING 690 * - \ref SCIP_STAGE_EXITPRESOLVE 691 * - \ref SCIP_STAGE_PRESOLVED 692 * - \ref SCIP_STAGE_INITSOLVE 693 * - \ref SCIP_STAGE_SOLVING 694 * - \ref SCIP_STAGE_SOLVED 695 */ 696 SCIP_RETCODE SCIPgetBendersSubproblemVar( 697 SCIP* scip, /**< SCIP data structure */ 698 SCIP_BENDERS* benders, /**< Benders' decomposition */ 699 SCIP_VAR* var, /**< the master variable */ 700 SCIP_VAR** mappedvar, /**< pointer to store the subproblem variable that var is mapped to */ 701 int probnumber /**< the subproblem number */ 702 ) 703 { 704 assert(scip != NULL); 705 assert(scip->set != NULL); 706 assert(benders != NULL); 707 assert(var != NULL); 708 assert(mappedvar != NULL); 709 assert(probnumber >= 0 && probnumber < SCIPgetBendersNSubproblems(scip, benders)); 710 711 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetBendersSubproblemVar", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 712 713 SCIP_CALL( SCIPbendersGetVar(benders, scip->set, var, mappedvar, probnumber) ); 714 715 return SCIP_OKAY; 716 } 717 718 /** returns the number of subproblems that are stored in the given Benders' decomposition 719 * 720 * @return the number of subproblems in the Benders' decomposition 721 */ 722 int SCIPgetBendersNSubproblems( 723 SCIP* scip, /**< SCIP data structure */ 724 SCIP_BENDERS* benders /**< Benders' decomposition */ 725 ) 726 { 727 assert(scip != NULL); 728 assert(benders != NULL); 729 730 return SCIPbendersGetNSubproblems(benders); 731 } 732 733 /** registers the Benders' decomposition subproblem with the Benders' decomposition struct. 734 * 735 * If a custom subproblem solving method is used and no internal cut generation methods will be employed, then the 736 * subproblem parameter can be set to NULL. By setting subproblem to NULL will inform the Benders' decomposition core 737 * that a custom solving method is used. This will ensure that no internal solving methods are invoked during the 738 * solution process. 739 * 740 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 741 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 742 * 743 * @pre This method can be called if SCIP is in one of the following stages: 744 * - \ref SCIP_STAGE_TRANSFORMED 745 */ 746 SCIP_RETCODE SCIPaddBendersSubproblem( 747 SCIP* scip, /**< SCIP data structure */ 748 SCIP_BENDERS* benders, /**< Benders' decomposition */ 749 SCIP* subproblem /**< Benders' decomposition subproblem, can be NULL */ 750 ) 751 { 752 assert(scip != NULL); 753 assert(benders != NULL); 754 755 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddBendersSubproblem", FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 756 757 SCIP_CALL( SCIPbendersAddSubproblem(benders, subproblem) ); 758 759 return SCIP_OKAY; 760 } 761 762 /** calls the generic subproblem setup method for a Benders' decomposition subproblem 763 * 764 * This is called if the user requires to solve the Benders' decomposition subproblem separately from the main Benders' 765 * solving loop. This could be in the case of enhancement techniques. 766 * 767 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 768 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 769 * 770 * @pre This method can be called if SCIP is in one of the following stages: 771 * - \ref SCIP_STAGE_TRANSFORMED 772 * - \ref SCIP_STAGE_INITPRESOLVE 773 * - \ref SCIP_STAGE_PRESOLVING 774 * - \ref SCIP_STAGE_EXITPRESOLVE 775 * - \ref SCIP_STAGE_PRESOLVED 776 * - \ref SCIP_STAGE_INITSOLVE 777 * - \ref SCIP_STAGE_SOLVING 778 * - \ref SCIP_STAGE_SOLVED 779 */ 780 SCIP_RETCODE SCIPsetupBendersSubproblem( 781 SCIP* scip, /**< SCIP data structure */ 782 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */ 783 SCIP_SOL* sol, /**< primal solution used to setup the problem, NULL for LP solution */ 784 int probnumber, /**< the subproblem number */ 785 SCIP_BENDERSENFOTYPE type /**< the enforcement type calling this function */ 786 ) 787 { 788 assert(scip != NULL); 789 assert(scip->set != NULL); 790 assert(benders != NULL); 791 assert(probnumber >= 0 && probnumber < SCIPgetBendersNSubproblems(scip, benders)); 792 793 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetupBendersSubproblem", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 794 795 SCIP_CALL( SCIPbendersSetupSubproblem(benders, scip->set, sol, probnumber, type) ); 796 797 return SCIP_OKAY; 798 } 799 800 /** calls the solving method for a single Benders' decomposition subproblem 801 * 802 * The method either calls the users solve subproblem method or calls the generic method. In the case of the generic 803 * method, the user must set up the subproblem prior to calling this method. 804 * 805 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 806 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 807 * 808 * @pre This method can be called if SCIP is in one of the following stages: 809 * - \ref SCIP_STAGE_TRANSFORMED 810 * - \ref SCIP_STAGE_INITPRESOLVE 811 * - \ref SCIP_STAGE_PRESOLVING 812 * - \ref SCIP_STAGE_EXITPRESOLVE 813 * - \ref SCIP_STAGE_PRESOLVED 814 * - \ref SCIP_STAGE_INITSOLVE 815 * - \ref SCIP_STAGE_SOLVING 816 * - \ref SCIP_STAGE_SOLVED 817 */ 818 SCIP_RETCODE SCIPsolveBendersSubproblem( 819 SCIP* scip, /**< SCIP data structure */ 820 SCIP_BENDERS* benders, /**< Benders' decomposition */ 821 SCIP_SOL* sol, /**< primal CIP solution, can be NULL for the current LP/Pseudo solution */ 822 int probnumber, /**< the subproblem number */ 823 SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */ 824 SCIP_Bool solvecip, /**< directly solve the CIP subproblem */ 825 SCIP_Real* objective /**< the objective function value of the subproblem, can be NULL */ 826 ) 827 { 828 assert(scip != NULL); 829 assert(scip->set != NULL); 830 assert(benders != NULL); 831 assert(probnumber >= 0 && probnumber < SCIPgetBendersNSubproblems(scip, benders)); 832 833 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveBendersSubproblem", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 834 835 SCIP_CALL( SCIPbendersSolveSubproblem(benders, scip->set, sol, probnumber, infeasible, solvecip, objective) ); 836 837 return SCIP_OKAY; 838 } 839 840 /** frees the subproblem after calling the solve subproblem method 841 * 842 * This will either call the user defined free 843 * subproblem callback for Benders' decomposition or the default freeing methods. In the default case, if the 844 * subproblem is an LP, then SCIPendProbing is called. If the subproblem is a MIP, then SCIPfreeTransform is called. 845 * 846 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 847 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 848 * 849 * @pre This method can be called if SCIP is in one of the following stages: 850 * - \ref SCIP_STAGE_TRANSFORMED 851 * - \ref SCIP_STAGE_INITPRESOLVE 852 * - \ref SCIP_STAGE_PRESOLVING 853 * - \ref SCIP_STAGE_EXITPRESOLVE 854 * - \ref SCIP_STAGE_PRESOLVED 855 * - \ref SCIP_STAGE_INITSOLVE 856 * - \ref SCIP_STAGE_SOLVING 857 * - \ref SCIP_STAGE_SOLVED 858 * - \ref SCIP_STAGE_EXITSOLVE 859 * - \ref SCIP_STAGE_FREETRANS 860 */ 861 SCIP_RETCODE SCIPfreeBendersSubproblem( 862 SCIP* scip, /**< SCIP data structure */ 863 SCIP_BENDERS* benders, /**< Benders' decomposition */ 864 int probnumber /**< the subproblem number */ 865 ) 866 { 867 assert(scip != NULL); 868 assert(scip->set != NULL); 869 assert(benders != NULL); 870 assert(probnumber >= 0 && probnumber < SCIPgetBendersNSubproblems(scip, benders)); 871 872 SCIP_CALL( SCIPcheckStage(scip, "SCIPfreeBendersSubproblem", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) ); 873 874 SCIP_CALL( SCIPbendersFreeSubproblem(benders, scip->set, probnumber) ); 875 876 return SCIP_OKAY; 877 } 878 879 /** checks the optimality of a Benders' decomposition subproblem by comparing the objective function value against the 880 * value of the corresponding auxiliary variable 881 * 882 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 883 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 884 * 885 * @pre This method can be called in any SCIP stage; however, it is necessary that the Benders' auxiliary variables 886 * exist. If they don't exist, then the optimal flag is returned as FALSE. 887 * 888 * @pre This method can be called if requested subproblem is in one of the following stages: 889 * - \ref SCIP_STAGE_SOLVING 890 * - \ref SCIP_STAGE_SOLVED 891 */ 892 SCIP_RETCODE SCIPcheckBendersSubproblemOptimality( 893 SCIP* scip, /**< SCIP data structure */ 894 SCIP_BENDERS* benders, /**< the benders' decomposition structure */ 895 SCIP_SOL* sol, /**< primal CIP solution, can be NULL for the current LP solution */ 896 int probnumber, /**< the number of the pricing problem */ 897 SCIP_Bool* optimal /**< flag to indicate whether the current subproblem is optimal for the master */ 898 ) 899 { 900 assert(scip != NULL); 901 assert(benders != NULL); 902 assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders)); 903 904 (*optimal) = FALSE; 905 906 if( SCIPbendersGetAuxiliaryVar(benders, probnumber) == NULL ) 907 { 908 SCIPinfoMessage(scip, NULL, "Benders' decomposition: The auxiliary variable for subproblem <%d> doesn't exist. " 909 "SCIPcheckBendersSubproblemOptimality can not be currently called at stage <%d>.\n", probnumber, 910 SCIPgetStage(scip)); 911 SCIPinfoMessage(scip, NULL, " The optimal flag will be returned as FALSE.\n"); 912 913 return SCIP_OKAY; 914 } 915 916 if( SCIPbendersSubproblem(benders, probnumber) != NULL ) 917 { 918 SCIP_CALL( SCIPcheckStage(SCIPbendersSubproblem(benders, probnumber), "SCIPcheckBendersSubproblemOptimality", 919 FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 920 } 921 922 (*optimal) = SCIPbendersSubproblemIsOptimal(benders, scip->set, sol, probnumber); 923 924 return SCIP_OKAY; 925 } 926 927 /** returns the value of the auxiliary variable for a given subproblem 928 * 929 * @return the value of the auxiliary variable for the given subproblem 930 */ 931 SCIP_Real SCIPgetBendersAuxiliaryVarVal( 932 SCIP* scip, /**< SCIP data structure */ 933 SCIP_BENDERS* benders, /**< the benders' decomposition structure */ 934 SCIP_SOL* sol, /**< primal CIP solution, can be NULL for the current LP solution */ 935 int probnumber /**< the number of the pricing problem */ 936 ) 937 { 938 assert(scip != NULL); 939 assert(benders != NULL); 940 assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders)); 941 942 return SCIPbendersGetAuxiliaryVarVal(benders, scip->set, sol, probnumber); 943 } 944 945 /** solves an independent subproblem to identify its lower bound and updates the lower bound of the corresponding 946 * auxiliary variable 947 * 948 * @pre This method can be called if SCIP is in one of the following stages: 949 * - \ref SCIP_STAGE_INITPRESOLVE 950 * - \ref SCIP_STAGE_PRESOLVING 951 * - \ref SCIP_STAGE_EXITPRESOLVE 952 * - \ref SCIP_STAGE_PRESOLVED 953 * - \ref SCIP_STAGE_INITSOLVE 954 * - \ref SCIP_STAGE_SOLVING 955 * 956 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 957 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 958 */ 959 SCIP_RETCODE SCIPcomputeBendersSubproblemLowerbound( 960 SCIP* scip, /**< the SCIP data structure */ 961 SCIP_BENDERS* benders, /**< Benders' decomposition */ 962 int probnumber, /**< the subproblem to be evaluated */ 963 SCIP_Real* lowerbound, /**< the lowerbound for the subproblem */ 964 SCIP_Bool* infeasible /**< was the subproblem found to be infeasible? */ 965 ) 966 { 967 assert(scip != NULL); 968 assert(benders != NULL); 969 assert(probnumber >= 0 && probnumber < SCIPgetBendersNSubproblems(scip, benders)); 970 971 SCIP_CALL( SCIPcheckStage(scip, "SCIPcomputeBendersSubproblemLowerbound", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 972 973 SCIP_CALL( SCIPbendersComputeSubproblemLowerbound(benders, scip->set, probnumber, lowerbound, infeasible) ); 974 975 return SCIP_OKAY; 976 } 977 978 /** Merges a subproblem into the master problem. This process just adds a copy of the subproblem variables and 979 * constraints to the master problem, but keeps the subproblem stored in the Benders' decomposition data structure. 980 * The reason for keeping the subproblem available is for when it is queried for solutions after the problem is solved. 981 * 982 * Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that 983 * it will not be solved in the subsequent subproblem solving loops. 984 * 985 * The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem 986 * is added as an underestimator constraint. 987 * 988 * @pre This method can be called if SCIP is in one of the following stages: 989 * - \ref SCIP_STAGE_INITPRESOLVE 990 * - \ref SCIP_STAGE_PRESOLVING 991 * - \ref SCIP_STAGE_EXITPRESOLVE 992 * - \ref SCIP_STAGE_PRESOLVED 993 * - \ref SCIP_STAGE_INITSOLVE 994 * - \ref SCIP_STAGE_SOLVING 995 * 996 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 997 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 998 */ 999 SCIP_RETCODE SCIPmergeBendersSubproblemIntoMaster( 1000 SCIP* scip, /**< the SCIP data structure */ 1001 SCIP_BENDERS* benders, /**< Benders' decomposition */ 1002 SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of subproblem variables corresponding 1003 * to the newly created master variables, or NULL */ 1004 SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of subproblem constraints to the 1005 * corresponding newly created constraints, or NULL */ 1006 int probnumber /**< the number of the subproblem that will be merged into the master problem*/ 1007 ) 1008 { 1009 assert(scip != NULL); 1010 assert(benders != NULL); 1011 assert(probnumber >= 0 && probnumber < SCIPgetBendersNSubproblems(scip, benders)); 1012 1013 SCIP_CALL( SCIPcheckStage(scip, "SCIPmergeBendersSubproblemIntoMaster", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1014 1015 SCIP_CALL( SCIPbendersMergeSubproblemIntoMaster(benders, scip->set, varmap, consmap, probnumber) ); 1016 1017 return SCIP_OKAY; 1018 } 1019 1020 /** applies a Benders' decomposition to the selected decomposition from the decomposition store 1021 * 1022 * @pre This method can be called if SCIP is in one of the following stages: 1023 * - \ref SCIP_STAGE_PROBLEM 1024 * 1025 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1026 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1027 */ 1028 SCIP_RETCODE SCIPapplyBendersDecomposition( 1029 SCIP* scip, /**< the SCIP data structure */ 1030 int decompindex /**< the index of the decomposition that will be applied */ 1031 ) 1032 { 1033 SCIP_BENDERS* benders; 1034 1035 assert(scip != NULL); 1036 assert(scip->decompstore != NULL); 1037 assert(SCIPdecompstoreGetNOrigDecomps(scip->decompstore) > 0); 1038 assert(decompindex >= 0 && decompindex < SCIPdecompstoreGetNOrigDecomps(scip->decompstore)); 1039 1040 SCIP_CALL( SCIPcheckStage(scip, "SCIPapplyBendersDecomposition", FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1041 1042 /* if there already exists an active Benders' decomposition, then default decomposition is not applied. */ 1043 if( SCIPgetNActiveBenders(scip) > 0 ) 1044 { 1045 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "A Benders' decomposition already exists. The default Benders' decomposition will not be applied to the stored decomposition.\n"); 1046 return SCIP_OKAY; 1047 } 1048 1049 /* retrieving the default Benders' decomposition plugin */ 1050 benders = SCIPfindBenders(scip, "default"); 1051 1052 /* if the default Benders' decomposition plugin doesn't exist, then this will result in an error */ 1053 if( benders == NULL ) 1054 { 1055 SCIPerrorMessage("The default Benders' decomposition plugin is required to apply Benders' decomposition using the input decomposition."); 1056 return SCIP_ERROR; 1057 } 1058 1059 /* applying the Benders' decomposition. If SCIP is in the PROBLEM stage, then the auxiliary variables don't need to 1060 * be added. However, in any other stage, then the auxiliary variables must be added to the problem. 1061 */ 1062 SCIP_CALL( SCIPbendersApplyDecomposition(benders, scip->set, 1063 SCIPdecompstoreGetOrigDecomps(scip->decompstore)[decompindex]) ); 1064 1065 return SCIP_OKAY; 1066 } 1067 1068 /** creates a Benders' cut algorithms and includes it in the associated Benders' decomposition 1069 * 1070 * This should be called from the SCIPincludeBendersXyz for the associated Benders' decomposition. It is only possible 1071 * to include a Benders' cut algorithm if a Benders' decomposition has already been included 1072 * This should be done during the problem creation stage. 1073 * 1074 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1075 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1076 * 1077 * @pre This method can be called if SCIP is in one of the following stages: 1078 * - \ref SCIP_STAGE_INIT 1079 * - \ref SCIP_STAGE_PROBLEM 1080 * 1081 * @note method has all Benders' decomposition callbacks as arguments and is thus changed every time a new callback is 1082 * added in future releases; consider using SCIPincludeBendersBasic() and setter functions 1083 * if you seek for a method which is less likely to change in future releases 1084 */ 1085 SCIP_RETCODE SCIPincludeBenderscut( 1086 SCIP* scip, /**< SCIP data structure */ 1087 SCIP_BENDERS* benders, /**< Benders' decomposition */ 1088 const char* name, /**< name of Benders' decomposition cuts */ 1089 const char* desc, /**< description of Benders' decomposition cuts */ 1090 int priority, /**< priority of the Benders' decomposition cuts */ 1091 SCIP_Bool islpcut, /**< indicates whether the cut is generated from the LP solution */ 1092 SCIP_DECL_BENDERSCUTCOPY((*benderscutcopy)),/**< copy method of Benders' decomposition cuts or NULL if you don't want to copy your plugin into sub-SCIPs */ 1093 SCIP_DECL_BENDERSCUTFREE((*benderscutfree)),/**< destructor of Benders' decomposition cuts */ 1094 SCIP_DECL_BENDERSCUTINIT((*benderscutinit)),/**< initialize Benders' decomposition cuts */ 1095 SCIP_DECL_BENDERSCUTEXIT((*benderscutexit)),/**< deinitialize Benders' decomposition cuts */ 1096 SCIP_DECL_BENDERSCUTINITSOL((*benderscutinitsol)),/**< solving process initialization method of Benders' decomposition cuts */ 1097 SCIP_DECL_BENDERSCUTEXITSOL((*benderscutexitsol)),/**< solving process deinitialization method of Benders' decomposition cuts */ 1098 SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)),/**< execution method of Benders' decomposition cuts */ 1099 SCIP_BENDERSCUTDATA* benderscutdata /**< Benders' decomposition cuts data */ 1100 ) 1101 { 1102 SCIP_BENDERSCUT* benderscut; 1103 1104 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBenderscut", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1105 1106 /* check whether pricer is already present */ 1107 if( SCIPfindBenderscut(benders, name) != NULL ) 1108 { 1109 SCIPerrorMessage("benders <%s> already included.\n", name); 1110 return SCIP_INVALIDDATA; 1111 } 1112 1113 SCIP_CALL( SCIPbenderscutCreate(benders, &benderscut, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, 1114 islpcut, benderscutcopy, benderscutfree, benderscutinit, benderscutexit, 1115 benderscutinitsol, benderscutexitsol, benderscutexec, benderscutdata) ); 1116 SCIP_CALL( SCIPbendersIncludeBenderscut(benders, scip->set, benderscut) ); 1117 1118 return SCIP_OKAY; 1119 } 1120 1121 /** creates a Benders' cut and includes it an associated Benders' decomposition with all non-fundamental callbacks set to NULL 1122 * 1123 * If needed, the non-fundamental callbacks can be added afterwards via setter functions SCIPsetBenderscutCopy(), 1124 * SCIPsetBenderscutFree(), SCIPsetBenderscutInit(), SCIPsetBenderscutExit(), SCIPsetBenderscutInitsol(), 1125 * SCIPsetBenderscutExitsol(). 1126 * 1127 * This should be done during the problem creation stage. 1128 * 1129 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1130 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1131 * 1132 * @pre This method can be called if SCIP is in one of the following stages: 1133 * - \ref SCIP_STAGE_INIT 1134 * - \ref SCIP_STAGE_PROBLEM 1135 * 1136 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBenders() instead 1137 */ 1138 SCIP_RETCODE SCIPincludeBenderscutBasic( 1139 SCIP* scip, /**< SCIP data structure */ 1140 SCIP_BENDERS* benders, /**< Benders' decomposition */ 1141 SCIP_BENDERSCUT** benderscutptr, /**< reference to a Benders' decomposition cut, or NULL */ 1142 const char* name, /**< name of Benders' decomposition */ 1143 const char* desc, /**< description of Benders' decomposition */ 1144 int priority, /**< priority of the Benders' decomposition */ 1145 SCIP_Bool islpcut, /**< indicates whether the cut is generated from the LP solution */ 1146 SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)),/**< the execution method of the Benders' cut algorithm */ 1147 SCIP_BENDERSCUTDATA* benderscutdata /**< Benders' cut data */ 1148 ) 1149 { 1150 SCIP_BENDERSCUT* benderscut; 1151 1152 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBenderscutBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1153 1154 /* check whether Benders' decomposition cut is already present */ 1155 if( SCIPfindBenderscut(benders, name) != NULL ) 1156 { 1157 SCIPerrorMessage("Benders' cut <%s> already included.\n", name); 1158 return SCIP_INVALIDDATA; 1159 } 1160 1161 SCIP_CALL( SCIPbenderscutCreate(benders, &benderscut, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, 1162 priority, islpcut, NULL, NULL, NULL, NULL, NULL, NULL, benderscutexec, benderscutdata) ); 1163 SCIP_CALL( SCIPbendersIncludeBenderscut(benders, scip->set, benderscut) ); 1164 1165 if( benderscutptr != NULL ) 1166 *benderscutptr = benderscut; 1167 1168 return SCIP_OKAY; 1169 } 1170 1171 /** sets copy method of Benders' decomposition cut 1172 * 1173 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1174 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1175 * 1176 * @pre This method can be called if SCIP is in one of the following stages: 1177 * - \ref SCIP_STAGE_INIT 1178 * - \ref SCIP_STAGE_PROBLEM 1179 */ 1180 SCIP_RETCODE SCIPsetBenderscutCopy( 1181 SCIP* scip, /**< SCIP data structure */ 1182 SCIP_BENDERSCUT* benderscut, /**< Benders' decomposition cut */ 1183 SCIP_DECL_BENDERSCUTCOPY((*benderscutcopy))/**< copy method of benderscut or NULL if you don't want to copy your plugin into sub-SCIPs */ 1184 ) 1185 { 1186 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBenderscutCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1187 1188 assert(benderscut != NULL); 1189 1190 SCIPbenderscutSetCopy(benderscut, benderscutcopy); 1191 1192 return SCIP_OKAY; 1193 } 1194 1195 /** sets destructor method of benderscut 1196 * 1197 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1198 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1199 * 1200 * @pre This method can be called if SCIP is in one of the following stages: 1201 * - \ref SCIP_STAGE_INIT 1202 * - \ref SCIP_STAGE_PROBLEM 1203 */ 1204 SCIP_RETCODE SCIPsetBenderscutFree( 1205 SCIP* scip, /**< SCIP data structure */ 1206 SCIP_BENDERSCUT* benderscut, /**< benderscut */ 1207 SCIP_DECL_BENDERSCUTFREE((*benderscutfree))/**< destructor of benderscut */ 1208 ) 1209 { 1210 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBenderscutFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1211 1212 assert(benderscut != NULL); 1213 1214 SCIPbenderscutSetFree(benderscut, benderscutfree); 1215 1216 return SCIP_OKAY; 1217 } 1218 1219 /** sets initialization method of benderscut 1220 * 1221 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1222 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1223 * 1224 * @pre This method can be called if SCIP is in one of the following stages: 1225 * - \ref SCIP_STAGE_INIT 1226 * - \ref SCIP_STAGE_PROBLEM 1227 */ 1228 SCIP_RETCODE SCIPsetBenderscutInit( 1229 SCIP* scip, /**< SCIP data structure */ 1230 SCIP_BENDERSCUT* benderscut, /**< benderscut */ 1231 SCIP_DECL_BENDERSCUTINIT((*benderscutinit))/**< initialize benderscut */ 1232 ) 1233 { 1234 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBenderscutInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1235 1236 assert(benderscut != NULL); 1237 1238 SCIPbenderscutSetInit(benderscut, benderscutinit); 1239 1240 return SCIP_OKAY; 1241 } 1242 1243 /** sets deinitialization method of benderscut 1244 * 1245 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1246 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1247 * 1248 * @pre This method can be called if SCIP is in one of the following stages: 1249 * - \ref SCIP_STAGE_INIT 1250 * - \ref SCIP_STAGE_PROBLEM 1251 */ 1252 SCIP_RETCODE SCIPsetBenderscutExit( 1253 SCIP* scip, /**< SCIP data structure */ 1254 SCIP_BENDERSCUT* benderscut, /**< benderscut */ 1255 SCIP_DECL_BENDERSCUTEXIT((*benderscutexit))/**< deinitialize benderscut */ 1256 ) 1257 { 1258 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBenderscutExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1259 1260 assert(benderscut != NULL); 1261 1262 SCIPbenderscutSetExit(benderscut, benderscutexit); 1263 1264 return SCIP_OKAY; 1265 } 1266 1267 /** sets solving process initialization method of benderscut 1268 * 1269 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1270 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1271 * 1272 * @pre This method can be called if SCIP is in one of the following stages: 1273 * - \ref SCIP_STAGE_INIT 1274 * - \ref SCIP_STAGE_PROBLEM 1275 */ 1276 SCIP_RETCODE SCIPsetBenderscutInitsol( 1277 SCIP* scip, /**< SCIP data structure */ 1278 SCIP_BENDERSCUT* benderscut, /**< benderscut */ 1279 SCIP_DECL_BENDERSCUTINITSOL((*benderscutinitsol))/**< solving process initialization method of benderscut */ 1280 ) 1281 { 1282 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBenderscutInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1283 1284 assert(benderscut != NULL); 1285 1286 SCIPbenderscutSetInitsol(benderscut, benderscutinitsol); 1287 1288 return SCIP_OKAY; 1289 } 1290 1291 /** sets solving process deinitialization method of benderscut 1292 * 1293 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1294 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1295 * 1296 * @pre This method can be called if SCIP is in one of the following stages: 1297 * - \ref SCIP_STAGE_INIT 1298 * - \ref SCIP_STAGE_PROBLEM 1299 */ 1300 SCIP_RETCODE SCIPsetBenderscutExitsol( 1301 SCIP* scip, /**< SCIP data structure */ 1302 SCIP_BENDERSCUT* benderscut, /**< benderscut */ 1303 SCIP_DECL_BENDERSCUTEXITSOL((*benderscutexitsol))/**< solving process deinitialization method of benderscut */ 1304 ) 1305 { 1306 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBenderscutExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1307 1308 assert(benderscut != NULL); 1309 1310 SCIPbenderscutSetExitsol(benderscut, benderscutexitsol); 1311 1312 return SCIP_OKAY; 1313 } 1314 1315 /** sets the priority of a Benders' decomposition cut algorithm 1316 * 1317 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1318 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1319 * 1320 * @pre This method can be called if SCIP is in one of the following stages: 1321 * - \ref SCIP_STAGE_INIT 1322 * - \ref SCIP_STAGE_PROBLEM 1323 */ 1324 SCIP_RETCODE SCIPsetBenderscutPriority( 1325 SCIP* scip, /**< SCIP data structure */ 1326 SCIP_BENDERSCUT* benderscut, /**< benderscut */ 1327 int priority /**< new priority of the Benders' decomposition */ 1328 ) 1329 { 1330 SCIP_BENDERS** benders; 1331 int nbenders; 1332 int i; 1333 1334 assert(scip != NULL); 1335 assert(scip->set != NULL); 1336 assert(benderscut != NULL); 1337 1338 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBenderscutPriority", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1339 1340 SCIPbenderscutSetPriority(benderscut, priority); 1341 1342 /* DIRTY: This is not a good fix */ 1343 /* Changing the priority of one Benders' cut in a Benders' decomposition requires all Benders' cuts to be set to 1344 * unsorted. This is a fix that is not very nice, but it does the job */ 1345 benders = SCIPgetBenders(scip); 1346 nbenders = SCIPgetNBenders(scip); 1347 for( i = 0; i < nbenders; i++ ) 1348 SCIPbendersSetBenderscutsSorted(benders[i], FALSE); 1349 1350 return SCIP_OKAY; 1351 } 1352 1353 /** adds the generated cuts to the Benders' cut storage 1354 * 1355 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1356 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1357 * 1358 * @pre This method can be called if SCIP is in one of the following stages: 1359 * - \ref SCIP_STAGE_INITPRESOLVE 1360 * - \ref SCIP_STAGE_PRESOLVING 1361 * - \ref SCIP_STAGE_EXITPRESOLVE 1362 * - \ref SCIP_STAGE_PRESOLVED 1363 * - \ref SCIP_STAGE_INITSOLVE 1364 * - \ref SCIP_STAGE_SOLVING 1365 */ 1366 SCIP_RETCODE SCIPstoreBendersCut( 1367 SCIP* scip, /**< the SCIP data structure */ 1368 SCIP_BENDERS* benders, /**< Benders' decomposition */ 1369 SCIP_VAR** vars, /**< the variables that have non-zero coefficients in the cut */ 1370 SCIP_Real* vals, /**< the coefficients of the variables in the cut */ 1371 SCIP_Real lhs, /**< the left hand side of the cut */ 1372 SCIP_Real rhs, /**< the right hand side of the cut */ 1373 int nvars /**< the number of variables with non-zero coefficients in the cut */ 1374 ) 1375 { 1376 assert(scip != NULL); 1377 assert(benders != NULL); 1378 assert(vars != NULL); 1379 assert(vals != NULL); 1380 1381 SCIP_CALL( SCIPcheckStage(scip, "SCIPstoreBendersCut", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1382 1383 SCIP_CALL( SCIPbendersStoreCut(benders, scip->set, vars, vals, lhs, rhs, nvars) ); 1384 1385 return SCIP_OKAY; 1386 } 1387 1388 /** creates a constraint in the input SCIP instance that corresponds to the given vars and vals arrays */ 1389 static 1390 SCIP_RETCODE createAndApplyStoredBendersCut( 1391 SCIP* scip, /**< the SCIP data structure */ 1392 SCIP_VAR** vars, /**< the variables from the source constraint */ 1393 SCIP_Real* vals, /**< the coefficients of the variables in the source constriant */ 1394 SCIP_Real lhs, /**< the LHS of the source constraint */ 1395 SCIP_Real rhs, /**< the RHS of the source constraint */ 1396 int nvars, /**< the number of variables in the source constraint */ 1397 int consindex /**< the store index for the constraint */ 1398 ) 1399 { 1400 SCIP_CONS* cons; 1401 char consname[SCIP_MAXSTRLEN]; 1402 1403 assert(scip != NULL); 1404 assert(vars != NULL); 1405 assert(vals != NULL); 1406 1407 /* setting the name of the transferred cut */ 1408 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "transferredbenderscut_%d", consindex); 1409 1410 /* creating a linear constraint given the input parameters */ 1411 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, consname, nvars, vars, vals, lhs, rhs) ); 1412 SCIP_CALL( SCIPsetConsRemovable(scip, cons, TRUE) ); 1413 1414 SCIP_CALL( SCIPaddCons(scip, cons) ); 1415 1416 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 1417 1418 return SCIP_OKAY; 1419 } 1420 1421 /** applies the Benders' decomposition cuts in storage to the input SCIP instance 1422 * 1423 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1424 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1425 * 1426 * @pre This method can be called if SCIP is in one of the following stages: 1427 * - \ref SCIP_STAGE_INITPRESOLVE 1428 * - \ref SCIP_STAGE_PRESOLVING 1429 * - \ref SCIP_STAGE_EXITPRESOLVE 1430 * - \ref SCIP_STAGE_PRESOLVED 1431 * - \ref SCIP_STAGE_INITSOLVE 1432 * - \ref SCIP_STAGE_SOLVING 1433 */ 1434 SCIP_RETCODE SCIPapplyBendersStoredCuts( 1435 SCIP* scip, /**< the SCIP data structure */ 1436 SCIP_BENDERS* benders /**< Benders' decomposition */ 1437 ) 1438 { 1439 SCIP_VAR** vars; 1440 SCIP_Real* vals; 1441 SCIP_Real lhs; 1442 SCIP_Real rhs; 1443 int naddedcuts; 1444 int nvars; 1445 int i; 1446 1447 assert(scip != NULL); 1448 assert(benders != NULL); 1449 1450 /* retrieving the number of stored Benders' cuts */ 1451 naddedcuts = SCIPbendersGetNStoredCuts(benders); 1452 1453 /* looping over all added cuts to construct the cut for the input SCIP instance */ 1454 for( i = 0; i < naddedcuts; i++ ) 1455 { 1456 /* collecting the variable information from the constraint */ 1457 SCIP_CALL( SCIPbendersGetStoredCutData(benders, i, &vars, &vals, &lhs, &rhs, &nvars) ); 1458 1459 if( nvars > 0 ) 1460 { 1461 /* create and apply the cut to be transferred from the sub SCIP to the source SCIP */ 1462 SCIP_CALL( createAndApplyStoredBendersCut(scip, vars, vals, lhs, rhs, nvars, i) ); 1463 } 1464 } 1465 1466 return SCIP_OKAY; 1467 } 1468