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 benders_default.c 26 * @ingroup OTHER_CFILES 27 * @brief default Benders' decomposition plugin 28 * @author Stephen J. Maher 29 * 30 * The default Benders' decomposition plugin is provided to simplify the interaction the Benders' decomposition 31 * framework within SCIP. This plugin is included in the SCIP package by default. Using the default Benders' 32 * decomposition plugin, a problem can be solved by Benders' decomposition by calling 33 * 34 * SCIPcreateBendersDefault(master problem, array of subproblems, number of subproblems) 35 * 36 * where "master problem" is a SCIP instance of the master problem, "array of subproblems" is an array of SCIP instances 37 * that are the Benders' decomposition subproblems and "number of subproblems" is an integer indicating the number of 38 * subproblems for this decomposition. 39 * 40 * A key feature of the default Benders' decomposition plugin is the automatic generation of the variable mapping 41 * between the variables of the master problem and the subproblems. 42 * 43 * In the traditional application of Benders' decomposition, master problem variables are fixed to a solution value and 44 * modify the RHS of the second stage constraints. The implementation within SCIP requires that a variable is created 45 * in the subproblem for every master problem variable that appears in the subproblem constraints. This variable MUST 46 * have the same name as the corresponding variable in the master problem. This name is used to automatically generate 47 * the mapping between the master problem and the corresponding subproblem variables. 48 * 49 */ 50 51 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 52 53 #include "scip/benders_default.h" 54 #include "scip/bendersdefcuts.h" 55 #include "scip/pub_benders.h" 56 #include "scip/pub_message.h" 57 #include "scip/pub_misc.h" 58 #include "scip/pub_var.h" 59 #include "scip/scip.h" 60 61 #define BENDERS_NAME "default" 62 #define BENDERS_DESC "default implementation of Benders' decomposition" 63 #define BENDERS_PRIORITY 0 64 #define BENDERS_CUTLP TRUE /**< should Benders' cut be generated for LP solutions */ 65 #define BENDERS_CUTPSEUDO TRUE /**< should Benders' cut be generated for pseudo solutions */ 66 #define BENDERS_CUTRELAX TRUE /**< should Benders' cut be generated for relaxation solutions */ 67 #define BENDERS_SHAREAUXVARS FALSE /**< should this Benders' share the highest priority Benders' aux vars */ 68 69 70 /* 71 * Data structures 72 */ 73 74 /** Benders' decomposition data */ 75 struct SCIP_BendersData 76 { 77 SCIP** subproblems; /**< the Benders' decomposition subproblems */ 78 SCIP_HASHMAP* mastervartosubindex;/**< hash map from the master variable to an index for the subproblemn variables */ 79 SCIP_HASHMAP* subvartomastervar; /**< hashmap from the subproblem variable to the master variable */ 80 SCIP_VAR*** subproblemvars; /**< the subproblem variables corresponding to master problem variables */ 81 int nmastervars; /**< the number of variables in the master problem */ 82 int nsubproblems; /**< the number of subproblems */ 83 SCIP_Bool created; /**< flag to indicate that the Benders' decomposition Data was created */ 84 SCIP_Bool subprobscopied; /**< were the subproblems copied during the SCIP copy */ 85 SCIP_Bool mappingcreated; /**< flag to indicate whether the variable mapping has been created */ 86 }; 87 88 89 90 91 /* 92 * Local methods 93 */ 94 95 /** creates the Benders' decomposition data */ 96 static 97 SCIP_RETCODE createBendersData( 98 SCIP* scip, /**< SCIP data structure */ 99 SCIP** subproblems, /**< the Benders' decomposition subproblems */ 100 SCIP_BENDERSDATA** bendersdata, /**< the Benders' decomposition data */ 101 int nsubproblems /**< the number of subproblems in the Benders' decomposition */ 102 ) 103 { 104 int i; 105 106 assert(scip != NULL); 107 assert(subproblems != NULL); 108 109 (*bendersdata)->nsubproblems = nsubproblems; 110 111 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*bendersdata)->subproblems, nsubproblems) ); 112 113 /* Copying the subproblem to the Benders' decomposition data. */ 114 for( i = 0; i < nsubproblems; i++ ) 115 (*bendersdata)->subproblems[i] = subproblems[i]; 116 117 (*bendersdata)->created = TRUE; 118 119 return SCIP_OKAY; 120 } 121 122 123 /** Creates the variable mappings between the master problem and the corresponding variable in the subproblem. 124 * 125 * TODO: add the functionality to allow the user to provide an array of hashmaps for mapping between the master problem 126 * variables and the corresponding subproblem variables. 127 * TODO: check for uniqueness of names in this function. 128 */ 129 static 130 SCIP_RETCODE createVariableMappings( 131 SCIP* scip, /**< SCIP data structure */ 132 SCIP_BENDERS* benders /**< the Benders' decomposition structure */ 133 ) 134 { 135 SCIP_BENDERSDATA* bendersdata; 136 SCIP_VAR** vars; 137 int nsubproblems; 138 int nvars; 139 char varname[SCIP_MAXSTRLEN]; 140 int i; 141 int j; 142 143 assert(scip != NULL); 144 assert(benders != NULL); 145 146 bendersdata = SCIPbendersGetData(benders); 147 assert(bendersdata != NULL); 148 149 nsubproblems = bendersdata->nsubproblems; 150 151 /* getting the master problem variable data */ 152 vars = SCIPgetVars(scip); 153 nvars = SCIPgetNVars(scip); 154 155 bendersdata->nmastervars = nvars; 156 157 /* creating the hashmaps for the mapping between the master variables and the sub variables */ 158 SCIP_CALL( SCIPhashmapCreate(&bendersdata->mastervartosubindex, SCIPblkmem(scip), nvars) ); 159 SCIP_CALL( SCIPhashmapCreate(&bendersdata->subvartomastervar, SCIPblkmem(scip), nvars*nsubproblems) ); 160 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &bendersdata->subproblemvars, nsubproblems) ); 161 for( i = 0; i < nsubproblems; i++ ) 162 { 163 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &bendersdata->subproblemvars[i], nvars) ); 164 } 165 166 /* this loop stores a mapping between the master problem variables and their counterpart in the subproblems. For each 167 * master problem variable, the variable name is used to search for any corresponding variables in each of the 168 * subproblems. If a corresponding variable exists, then a mapping is inserted into subvartomastervar and 169 * mastervartosubvar hashmaps 170 */ 171 for( i = 0; i < nvars; i++ ) 172 { 173 SCIP_VAR* origvar; 174 SCIP_VAR* subvar; 175 SCIP_Real scalar; 176 SCIP_Real constant; 177 const char* origvarname; 178 int charcount = SCIPgetSubscipDepth(scip)*2; 179 180 /* getting the original variable for the master variable 181 * NOTE: This retrieved variable is the original variable. It may be a bug in regards to other parts of the code. 182 * The process maps the subproblem variable to the original master variable. It was original supposed to be a 183 * mapping between the subproblem variables and the transformed master variable. 184 */ 185 origvar = vars[i]; 186 scalar = 1.0; 187 constant = 0.0; 188 SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) ); 189 190 /* retrieving the var name */ 191 origvarname = SCIPvarGetName(origvar); 192 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s", &origvarname[charcount]); 193 194 /* retrieving the subproblem variable for the given master variable */ 195 for( j = 0; j < nsubproblems; j++ ) 196 { 197 /* find the corresponding subproblem variable for a given master problem variable using the variable name. */ 198 subvar = SCIPfindVar(bendersdata->subproblems[j], varname); 199 200 /* adding the subvariable to master variable mapping into the hash map */ 201 if( subvar != NULL ) 202 { 203 SCIP_CALL( SCIPhashmapInsert(bendersdata->subvartomastervar, subvar, origvar) ); 204 } 205 206 /* storing the subproblem variable */ 207 bendersdata->subproblemvars[j][i] = subvar; 208 209 if( subvar != NULL ) 210 { 211 SCIP_CALL( SCIPcaptureVar(bendersdata->subproblems[j], bendersdata->subproblemvars[j][i]) ); 212 } 213 } 214 215 /* storing the mapping of the master variable to the variable index */ 216 SCIP_CALL( SCIPhashmapInsertInt(bendersdata->mastervartosubindex, vars[i], i) ); 217 } 218 219 bendersdata->mappingcreated = TRUE; 220 221 return SCIP_OKAY; 222 } 223 224 225 226 /* 227 * Callback methods for Benders' decomposition 228 */ 229 230 /** copy method for Benders' decomposition plugins (called when SCIP copies plugins) */ 231 static 232 SCIP_DECL_BENDERSCOPY(bendersCopyDefault) 233 { /*lint --e{715}*/ 234 SCIP_BENDERSDATA* bendersdata; /* the source Benders' decomposition data */ 235 236 assert(scip != NULL); 237 assert(benders != NULL); 238 239 bendersdata = SCIPbendersGetData(benders); 240 241 /* including the Benders' decomposition in the target SCIP. 242 * NOTE: this method uses the same subproblems as the main SCIP. In a parallel setting, this will not be thread safe. 243 * It would be cleaner to copy the subproblems also. 244 */ 245 SCIP_CALL( SCIPincludeBendersDefault(scip) ); 246 247 /* if the Benders' decomposition is active, then it must be created in the copy */ 248 if( SCIPbendersIsActive(benders) ) 249 { 250 SCIP** subproblems; 251 int i; 252 253 /* copying the subproblems if the threadsafe flag was set to TRUE */ 254 if( threadsafe ) 255 { 256 /* allocating memory for the subproblems array */ 257 SCIP_CALL( SCIPallocBufferArray(scip, &subproblems, bendersdata->nsubproblems) ); 258 259 for( i = 0; i < bendersdata->nsubproblems; i++ ) 260 { 261 SCIP_Bool valid; 262 263 /* creating the SCIP instance for the subproblem */ 264 SCIP_CALL( SCIPcreate(&subproblems[i]) ); 265 266 /* the original problem is copied so that the variable mappings are created correctly. 267 * TODO: use a varmap to create the mappings for the copies 268 */ 269 SCIP_CALL( SCIPcopyOrig(bendersdata->subproblems[i], subproblems[i], NULL, NULL, "", TRUE, FALSE, FALSE, 270 &valid) ); 271 assert(valid); 272 } 273 } 274 else 275 subproblems = bendersdata->subproblems; 276 277 SCIP_CALL( SCIPcreateBendersDefault(scip, subproblems, bendersdata->nsubproblems) ); 278 279 /* freeing the buffer memory for the subproblems */ 280 if( threadsafe ) 281 { 282 SCIP_BENDERS* targetbenders; 283 SCIP_BENDERSDATA* targetbendersdata; 284 285 targetbenders = SCIPfindBenders(scip, BENDERS_NAME); 286 assert(targetbenders != NULL); 287 288 targetbendersdata = SCIPbendersGetData(targetbenders); 289 290 /* indicating that the subproblems have been copied */ 291 targetbendersdata->subprobscopied = TRUE; 292 293 SCIPfreeBufferArray(scip, &subproblems); 294 } 295 } 296 297 return SCIP_OKAY; 298 } 299 300 /** destructor of Benders' decomposition to free user data (called when SCIP is exiting) */ 301 /**! [SnippetBendersFreeDefault] */ 302 static 303 SCIP_DECL_BENDERSFREE(bendersFreeDefault) 304 { /*lint --e{715}*/ 305 SCIP_BENDERSDATA* bendersdata; 306 int i; 307 308 assert(scip != NULL); 309 assert(benders != NULL); 310 311 bendersdata = SCIPbendersGetData(benders); 312 313 assert(bendersdata != NULL); 314 315 /* should have been freed in bendersExitDefault (if mappingcreated), or not been created at the first place */ 316 assert(bendersdata->subproblemvars == NULL); 317 assert(bendersdata->subvartomastervar == NULL); 318 assert(bendersdata->mastervartosubindex == NULL); 319 if( bendersdata->created ) 320 { 321 /* if the subproblems were copied, then the copy needs to be freed */ 322 if( bendersdata->subprobscopied ) 323 { 324 for( i = bendersdata->nsubproblems - 1; i >= 0; i-- ) 325 { 326 SCIP_CALL( SCIPfree(&bendersdata->subproblems[i]) ); 327 } 328 } 329 330 SCIPfreeBlockMemoryArray(scip, &bendersdata->subproblems, bendersdata->nsubproblems); 331 } 332 333 SCIPfreeBlockMemory(scip, &bendersdata); 334 335 return SCIP_OKAY; 336 } 337 /**! [SnippetBendersFreeDefault] */ 338 339 340 /** initialization method of Benders' decomposition (called after problem was transformed) */ 341 static 342 SCIP_DECL_BENDERSINIT(bendersInitDefault) 343 { /*lint --e{715}*/ 344 assert(scip != NULL); 345 assert(benders != NULL); 346 347 /* creating the variable mappings */ 348 SCIP_CALL( createVariableMappings(scip, benders) ); 349 350 return SCIP_OKAY; 351 } 352 353 /** deinitialization method of Benders' decomposition (called before transformed problem is freed and the Benders' 354 * decomposition is active) 355 */ 356 static 357 SCIP_DECL_BENDERSEXIT(bendersExitDefault) 358 { 359 SCIP_BENDERSDATA* bendersdata; 360 int i; 361 int j; 362 363 assert(scip != NULL); 364 assert(benders != NULL); 365 366 bendersdata = SCIPbendersGetData(benders); 367 368 assert(bendersdata != NULL); 369 370 if( bendersdata->mappingcreated ) 371 { 372 for( i = bendersdata->nsubproblems - 1; i >= 0; i-- ) 373 { 374 for( j = 0; j < bendersdata->nmastervars; j++ ) 375 { 376 if( bendersdata->subproblemvars[i][j] != NULL ) 377 { 378 SCIP_CALL( SCIPreleaseVar(bendersdata->subproblems[i], &bendersdata->subproblemvars[i][j]) ); 379 } 380 } 381 SCIPfreeBlockMemoryArray(scip, &bendersdata->subproblemvars[i], bendersdata->nmastervars); 382 } 383 SCIPfreeBlockMemoryArray(scip, &bendersdata->subproblemvars, bendersdata->nsubproblems); 384 385 /* free hash map */ 386 SCIPhashmapFree(&bendersdata->subvartomastervar); 387 SCIPhashmapFree(&bendersdata->mastervartosubindex); 388 } 389 390 return SCIP_OKAY; 391 } 392 393 /** mapping method between the master problem variables and the subproblem variables of Benders' decomposition */ 394 /**! [SnippetBendersGetvarDefault] */ 395 static 396 SCIP_DECL_BENDERSGETVAR(bendersGetvarDefault) 397 { /*lint --e{715}*/ 398 SCIP_BENDERSDATA* bendersdata; 399 SCIP_VAR* origvar; 400 SCIP_Real scalar; 401 SCIP_Real constant; 402 403 assert(scip != NULL); 404 assert(benders != NULL); 405 assert(var != NULL); 406 assert(mappedvar != NULL); 407 408 bendersdata = SCIPbendersGetData(benders); 409 410 if( probnumber == -1 ) 411 { 412 origvar = var; 413 /* The variable needs to be transformed back into an original variable. If the variable is already original, then 414 * this function just returns the same variable 415 */ 416 scalar = 1.0; 417 constant = 0.0; 418 SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) ); 419 420 /* using the original variable, the master variable can be retrieved from the hash map */ 421 (*mappedvar) = (SCIP_VAR*) SCIPhashmapGetImage(bendersdata->subvartomastervar, origvar); 422 423 if( (*mappedvar) == NULL ) 424 (*mappedvar) = (SCIP_VAR*) SCIPhashmapGetImage(bendersdata->subvartomastervar, var); 425 } 426 else 427 { 428 int masterindex; 429 /* The variable needs to be transformed back into an original variable. If the variable is already original, then 430 * this function just returns the same variable 431 */ 432 433 /* we are requesting the subproblem variable for a master problem variable 434 * The master problem variable is a transformed variable. The original variable is not required. 435 * NOTE: Currently the original variable is being used. This may not be correct and should be the transformed 436 * variable. 437 */ 438 masterindex = SCIPhashmapGetImageInt(bendersdata->mastervartosubindex, var); 439 (*mappedvar) = bendersdata->subproblemvars[probnumber][masterindex]; 440 } 441 442 return SCIP_OKAY; 443 } 444 /**! [SnippetBendersGetvarDefault] */ 445 446 /** the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage 447 * (after the master problem was transformed) 448 * 449 * This method must create the SCIP instance for the subproblem and add the required variables and constraints. In 450 * addition, the settings required for the solving the problem must be set here. However, some settings will be 451 * overridden by the standard solving method included in the Benders' decomposition framework. If a special solving 452 * method is desired, the user can implement the bendersSolvesubDefault callback. 453 */ 454 static 455 SCIP_DECL_BENDERSCREATESUB(bendersCreatesubDefault) 456 { /*lint --e{715}*/ 457 SCIP_BENDERSDATA* bendersdata; 458 459 assert(scip != NULL); 460 assert(benders != NULL); 461 462 bendersdata = SCIPbendersGetData(benders); 463 assert(bendersdata != NULL); 464 465 /* adding the subproblem to the Benders' decomposition structure */ 466 SCIP_CALL( SCIPaddBendersSubproblem(scip, benders, bendersdata->subproblems[probnumber]) ); 467 468 return SCIP_OKAY; 469 } 470 471 472 /* 473 * Benders' decomposition specific interface methods 474 */ 475 476 /** Creates a default Benders' decomposition algorithm and activates it in SCIP 477 * 478 * @note Every variable that appears in the subproblem constraints must be created in the corresponding subproblem with 479 * the same name as in the master problem. 480 * 481 * @note The default Benders' decomposition implementation relies on unique variable names in the master problem and in 482 * each of the subproblems. This is required because a variable mapping is made between the master problem variables and 483 * the counterparts in the subproblems. This mapping is created using the variable names. 484 */ 485 SCIP_RETCODE SCIPcreateBendersDefault( 486 SCIP* scip, /**< SCIP data structure */ 487 SCIP** subproblems, /**< the Benders' decomposition subproblems */ 488 int nsubproblems /**< the number of subproblems in the Benders' decomposition */ 489 ) 490 { 491 SCIP_BENDERS* benders; 492 SCIP_BENDERSDATA* bendersdata; 493 int maxrestarts; 494 495 assert(scip != NULL); 496 assert(subproblems != NULL); 497 assert(nsubproblems > 0); 498 499 benders = SCIPfindBenders(scip, BENDERS_NAME); 500 bendersdata = SCIPbendersGetData(benders); 501 502 /* turning restarts off */ 503 SCIP_CALL( SCIPgetIntParam(scip, "presolving/maxrestarts", &maxrestarts) ); 504 if( SCIPisParamFixed(scip, "presolving/maxrestarts") && maxrestarts != 0) 505 { 506 SCIPerrorMessage("The number of restarts is fixed to %d. The default Benders' decomposition requires the number" 507 " of restarts to be 0.", maxrestarts); 508 return SCIP_ERROR; 509 } 510 else 511 { 512 SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) ); 513 SCIP_CALL( SCIPfixParam(scip, "presolving/maxrestarts") ); 514 } 515 516 SCIP_CALL( createBendersData(scip, subproblems, &bendersdata, nsubproblems) ); 517 518 SCIP_CALL( SCIPactivateBenders(scip, benders, nsubproblems) ); 519 520 return SCIP_OKAY; 521 } 522 523 /** creates the default Benders' decomposition and includes it in SCIP */ 524 SCIP_RETCODE SCIPincludeBendersDefault( 525 SCIP* scip /**< SCIP data structure */ 526 ) 527 { 528 SCIP_BENDERSDATA* bendersdata; 529 SCIP_BENDERS* benders; 530 531 /* create default Benders' decomposition data */ 532 bendersdata = NULL; 533 534 SCIP_CALL( SCIPallocBlockMemory(scip, &bendersdata) ); 535 BMSclearMemory(bendersdata); 536 537 benders = NULL; 538 539 /* include Benders' decomposition */ 540 SCIP_CALL( SCIPincludeBendersBasic(scip, &benders, BENDERS_NAME, BENDERS_DESC, BENDERS_PRIORITY, BENDERS_CUTLP, 541 BENDERS_CUTPSEUDO, BENDERS_CUTRELAX, BENDERS_SHAREAUXVARS, bendersGetvarDefault, bendersCreatesubDefault, 542 bendersdata) ); 543 assert(benders != NULL); 544 545 /* set non fundamental callbacks via setter functions */ 546 SCIP_CALL( SCIPsetBendersCopy(scip, benders, bendersCopyDefault) ); 547 SCIP_CALL( SCIPsetBendersFree(scip, benders, bendersFreeDefault) ); 548 SCIP_CALL( SCIPsetBendersInit(scip, benders, bendersInitDefault) ); 549 SCIP_CALL( SCIPsetBendersExit(scip, benders, bendersExitDefault) ); 550 551 /* OPTIONAL: including the default cuts for Benders' decomposition */ 552 SCIP_CALL( SCIPincludeBendersDefaultCuts(scip, benders) ); 553 554 return SCIP_OKAY; 555 } 556