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_reopt.c 26 * @ingroup OTHER_CFILES 27 * @brief public methods for reoptimization 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/debug.h" 46 #include "scip/pub_message.h" 47 #include "scip/pub_reopt.h" 48 #include "scip/pub_tree.h" 49 #include "scip/reopt.h" 50 #include "scip/scip_mem.h" 51 #include "scip/scip_reopt.h" 52 #include "scip/scip_tree.h" 53 #include "scip/struct_mem.h" 54 #include "scip/struct_prob.h" 55 #include "scip/struct_scip.h" 56 #include "scip/struct_set.h" 57 #include "scip/struct_stat.h" 58 59 /** return the ids of child nodes stored in the reoptimization tree 60 * 61 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 62 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 63 * 64 * @pre This method can be called if @p scip is in one of the following stages: 65 * - \ref SCIP_STAGE_PRESOLVED 66 * - \ref SCIP_STAGE_SOLVING 67 * - \ref SCIP_STAGE_SOLVED 68 */ 69 SCIP_RETCODE SCIPgetReoptChildIDs( 70 SCIP* scip, /**< SCIP data structure */ 71 SCIP_NODE* node, /**< node of the search tree */ 72 unsigned int* ids, /**< array of ids */ 73 int idssize, /**< allocated memory */ 74 int* nids /**< number of child nodes */ 75 ) 76 { 77 assert(scip != NULL); 78 79 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetReoptChildIDs", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 80 81 (*nids) = 0; 82 83 if( !scip->set->reopt_enable ) 84 return SCIP_OKAY; 85 86 SCIP_CALL( SCIPreoptGetChildIDs(scip->reopt, scip->set, scip->mem->probmem, node, ids, idssize, nids) ); 87 88 return SCIP_OKAY; 89 } 90 91 /** return the ids of all leave nodes store in the reoptimization tree induced by the given node 92 * 93 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 94 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 95 * 96 * @pre This method can be called if @p scip is in one of the following stages: 97 * - \ref SCIP_STAGE_PRESOLVED 98 * - \ref SCIP_STAGE_SOLVING 99 * - \ref SCIP_STAGE_SOLVED 100 */ 101 SCIP_RETCODE SCIPgetReoptLeaveIDs( 102 SCIP* scip, /**< SCIP data structure */ 103 SCIP_NODE* node, /**< node of the search tree */ 104 unsigned int* ids, /**< array of ids */ 105 int idssize, /**< size of ids array */ 106 int* nids /**< number of child nodes */ 107 ) 108 { 109 assert(scip != NULL); 110 111 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetReoptLeaveIDs", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 112 113 (*nids) = 0; 114 115 if( idssize == 0 || !scip->set->reopt_enable ) 116 return SCIP_OKAY; 117 118 SCIP_CALL( SCIPreoptGetLeaves(scip->reopt, node, ids, idssize, nids) ); 119 120 return SCIP_OKAY; 121 } 122 123 /** returns the number of nodes in the reoptimization tree induced by @p node; if @p node == NULL the method 124 * returns the number of nodes of the whole reoptimization tree. 125 */ 126 int SCIPgetNReoptnodes( 127 SCIP* scip, /**< SCIP data structure */ 128 SCIP_NODE* node /**< node of the search tree */ 129 ) 130 { 131 assert(scip != NULL); 132 assert(scip->set->reopt_enable); 133 assert(scip->reopt != NULL); 134 135 return SCIPreoptGetNNodes(scip->reopt, node); 136 } 137 138 /** returns the number of leaf nodes of the subtree induced by @p node; if @p node == NULL, the method 139 * returns the number of leaf nodes of the whole reoptimization tree. 140 */ 141 int SCIPgetNReoptLeaves( 142 SCIP* scip, /**< SCIP data structure */ 143 SCIP_NODE* node /**< node of the search tree */ 144 ) 145 { 146 assert(scip != NULL); 147 assert(scip->set->reopt_enable); 148 assert(scip->reopt != NULL); 149 150 return SCIPreoptGetNLeaves(scip->reopt, node); 151 } 152 153 /** gets the node of the reoptimization tree corresponding to the unique @p id */ 154 SCIP_REOPTNODE* SCIPgetReoptnode( 155 SCIP* scip, /**< SCIP data structure */ 156 unsigned int id /**< unique id */ 157 ) 158 { 159 assert(scip != NULL); 160 assert(scip->set->reopt_enable); 161 assert(scip->reopt != NULL); 162 163 return SCIPreoptGetReoptnode(scip->reopt, id); 164 } 165 166 /** add a variable bound change to a given reoptnode 167 * 168 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 169 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 170 * 171 * @pre This method can be called if @p scip is in one of the following stages: 172 * - \ref SCIP_STAGE_PRESOLVED 173 * - \ref SCIP_STAGE_SOLVING 174 * - \ref SCIP_STAGE_SOLVED 175 */ 176 SCIP_RETCODE SCIPaddReoptnodeBndchg( 177 SCIP* scip, /**< SCIP data structure */ 178 SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */ 179 SCIP_VAR* var, /**< variable pointer */ 180 SCIP_Real bound, /**< variable bound to add */ 181 SCIP_BOUNDTYPE boundtype /**< bound type of the variable value */ 182 ) 183 { 184 assert(scip != NULL); 185 assert(reoptnode != NULL); 186 assert(scip->set->reopt_enable); 187 assert(scip->reopt != NULL); 188 189 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddReoptnodeBndchg", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 190 191 SCIP_CALL( SCIPreoptnodeAddBndchg(reoptnode, scip->set, scip->mem->probmem, var, bound, boundtype) ); 192 193 return SCIP_OKAY; 194 } 195 196 /** set the @p representation as the new search frontier 197 * 198 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 199 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 200 * 201 * @pre This method can be called if @p scip is in one of the following stages: 202 * - \ref SCIP_STAGE_PRESOLVED 203 */ 204 SCIP_RETCODE SCIPsetReoptCompression( 205 SCIP* scip, /**< SCIP data structure */ 206 SCIP_REOPTNODE** representation, /**< array of representatives */ 207 int nrepresentatives, /**< number of representatives */ 208 SCIP_Bool* success /**< pointer to store the result */ 209 ) 210 { 211 assert(scip != NULL); 212 assert(representation != NULL); 213 assert(nrepresentatives > 0); 214 assert(scip->set->reopt_enable); 215 assert(scip->reopt != NULL); 216 217 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetReoptCompression", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 218 219 SCIP_CALL( SCIPreoptApplyCompression(scip->reopt, scip->set, scip->mem->probmem, representation, nrepresentatives, success) ); 220 221 return SCIP_OKAY; 222 } 223 224 /** add stored constraint to a reoptimization node 225 * 226 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 227 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 228 * 229 * @pre This method can be called if @p scip is in one of the following stages: 230 * - \ref SCIP_STAGE_PRESOLVED 231 */ 232 SCIP_RETCODE SCIPaddReoptnodeCons( 233 SCIP* scip, /**< SCIP data structure */ 234 SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */ 235 SCIP_VAR** vars, /**< array of variables */ 236 SCIP_Real* vals, /**< array of variable bounds */ 237 SCIP_BOUNDTYPE* boundtypes, /**< array of variable boundtypes */ 238 SCIP_Real lhs, /**< lhs of the constraint */ 239 SCIP_Real rhs, /**< rhs of the constraint */ 240 int nvars, /**< number of variables */ 241 REOPT_CONSTYPE constype, /**< type of the constraint */ 242 SCIP_Bool linear /**< the given constraint has a linear representation */ 243 ) 244 { 245 assert(scip != NULL); 246 assert(reoptnode != NULL); 247 assert(vars != NULL); 248 assert(vals != NULL); 249 assert(nvars >= 0); 250 251 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddReoptnodeCons", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 252 253 SCIP_CALL( SCIPreoptnodeAddCons(reoptnode, scip->set, scip->mem->probmem, vars, vals, boundtypes, lhs, rhs, nvars, 254 constype, linear) ); 255 256 return SCIP_OKAY; 257 } 258 259 /** return the branching path stored in the reoptree at ID id */ 260 void SCIPgetReoptnodePath( 261 SCIP* scip, /**< SCIP data structure */ 262 SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */ 263 SCIP_VAR** vars, /**< array of variables */ 264 SCIP_Real* vals, /**< array of variable bounds */ 265 SCIP_BOUNDTYPE* boundtypes, /**< array of bound types */ 266 int mem, /**< allocated memory */ 267 int* nvars, /**< number of variables */ 268 int* nafterdualvars /**< number of variables directly after the first based on dual information */ 269 ) 270 { 271 assert(scip != NULL); 272 assert(vars != NULL); 273 assert(vals != NULL); 274 assert(boundtypes != NULL); 275 assert(scip->set->reopt_enable); 276 assert(scip->reopt != NULL); 277 278 SCIPreoptnodeGetPath(scip->reopt, reoptnode, vars, vals, boundtypes, mem, nvars, nafterdualvars); 279 } 280 281 /** initialize a set of empty reoptimization nodes 282 * 283 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 284 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 285 * 286 * @pre This method can be called if @p scip is in one of the following stages: 287 * - \ref SCIP_STAGE_PRESOLVED 288 */ 289 SCIP_RETCODE SCIPinitRepresentation( 290 SCIP* scip, /**< SCIP data structure */ 291 SCIP_REOPTNODE** representatives, /**< array of representatives */ 292 int nrepresentatives /**< number of representatives */ 293 ) 294 { 295 int r; 296 297 assert(scip != NULL); 298 assert(representatives != NULL); 299 300 SCIP_CALL( SCIPcheckStage(scip, "SCIPinitRepresentation", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 301 302 for( r = 0; r < nrepresentatives; r++ ) 303 { 304 SCIP_CALL( SCIPallocBlockMemory(scip, &representatives[r]) ); /*lint !e866*/ 305 SCIPreoptnodeInit(representatives[r], scip->set); 306 } 307 308 return SCIP_OKAY; 309 } 310 311 /** reset a set of initialized reoptimization nodes 312 * 313 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 314 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 315 * 316 * @pre This method can be called if @p scip is in one of the following stages: 317 * - \ref SCIP_STAGE_PRESOLVED 318 */ 319 SCIP_RETCODE SCIPresetRepresentation( 320 SCIP* scip, /**< SCIP data structure */ 321 SCIP_REOPTNODE** representatives, /**< array of representatives */ 322 int nrepresentatives /**< number of representatives */ 323 ) 324 { 325 int r; 326 327 assert(scip != NULL); 328 assert(representatives != NULL); 329 330 SCIP_CALL( SCIPcheckStage(scip, "SCIPresetRepresentation", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 331 332 for( r = 0; r < nrepresentatives; r++ ) 333 { 334 SCIP_CALL( SCIPreoptnodeReset(scip->reopt, scip->set, scip->mem->probmem, representatives[r]) ); 335 } 336 337 return SCIP_OKAY; 338 } 339 340 /** free a set of initialized reoptimization nodes 341 * 342 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 343 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 344 * 345 * @pre This method can be called if @p scip is in one of the following stages: 346 * - \ref SCIP_STAGE_PRESOLVED 347 */ 348 SCIP_RETCODE SCIPfreeRepresentation( 349 SCIP* scip, /**< SCIP data structure */ 350 SCIP_REOPTNODE** representatives, /**< array of representatives */ 351 int nrepresentatives /**< number of representatives */ 352 ) 353 { 354 int r; 355 356 assert(scip != NULL); 357 assert(representatives != NULL); 358 359 SCIP_CALL( SCIPcheckStage(scip, "SCIPfreeRepresentation", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 360 361 for( r = 0; r < nrepresentatives; r++ ) 362 { 363 if( representatives[r] != NULL ) 364 { 365 SCIP_CALL( SCIPreoptnodeDelete(&representatives[r], scip->mem->probmem) ); 366 assert(representatives[r] == NULL); 367 } 368 } 369 370 return SCIP_OKAY; 371 } 372 373 /** reactivate the given @p reoptnode and split them into several nodes if necessary 374 * 375 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 376 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 377 * 378 * @pre This method can be called if @p scip is in one of the following stages: 379 * - \ref SCIP_STAGE_SOLVING 380 * - \ref SCIP_STAGE_SOLVED 381 */ 382 SCIP_RETCODE SCIPapplyReopt( 383 SCIP* scip, /**< SCIP data structure */ 384 SCIP_REOPTNODE* reoptnode, /**< node to reactivate */ 385 unsigned int id, /**< unique id of the reoptimization node */ 386 SCIP_Real estimate, /**< estimate of the child nodes that should be created */ 387 SCIP_NODE** childnodes, /**< array to store the created child nodes */ 388 int* ncreatedchilds, /**< pointer to store number of created child nodes */ 389 int* naddedconss, /**< pointer to store number of generated constraints */ 390 int childnodessize, /**< available size of childnodes array */ 391 SCIP_Bool* success /**< pointer store the result*/ 392 ) 393 { 394 assert(scip != NULL); 395 assert(reoptnode != NULL); 396 397 SCIP_CALL( SCIPcheckStage(scip, "SCIPapplyReopt", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 398 399 SCIP_CALL( SCIPreoptApply(scip->reopt, scip, scip->set, scip->stat, scip->transprob, scip->origprob, scip->tree, 400 scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, scip->mem->probmem, reoptnode, id, estimate, 401 childnodes, ncreatedchilds, naddedconss, childnodessize, success) ); 402 403 return SCIP_OKAY; 404 } 405 406 /** return the similarity between two objective functions */ 407 SCIP_Real SCIPgetReoptSimilarity( 408 SCIP* scip, /**< SCIP data structure */ 409 int run1, /**< number of run */ 410 int run2 /**< number of run */ 411 ) 412 { 413 assert(scip != NULL); 414 assert(run1 > 0 && run1 <= scip->stat->nreoptruns); 415 assert(run2 > 0 && run2 <= scip->stat->nreoptruns); 416 417 if( (run1 == scip->stat->nreoptruns && run2 == run1-1) || (run2 == scip->stat->nreoptruns && run1 == run2-1) ) 418 return SCIPreoptGetSimToPrevious(scip->reopt); 419 else 420 return SCIPreoptGetSimilarity(scip->reopt, scip->set, run1, run2, scip->origprob->vars, scip->origprob->nvars); 421 } 422 423 /** returns if a node should be reoptimized */ 424 SCIP_Bool SCIPreoptimizeNode( 425 SCIP* scip, /**< SCIP data structure */ 426 SCIP_NODE* node /**< node of the search tree */ 427 ) 428 { 429 assert(scip != NULL); 430 assert(node != NULL); 431 432 if( scip->set->reopt_enable ) 433 { 434 SCIP_REOPTNODE* reoptnode; 435 unsigned int id; 436 437 assert(scip->reopt != NULL); 438 439 id = SCIPnodeGetReoptID(node); 440 441 if( id == 0 && node != SCIPgetRootNode(scip) ) 442 return FALSE; 443 else 444 { 445 reoptnode = SCIPgetReoptnode(scip, id); 446 assert(reoptnode != NULL); 447 448 return SCIPreoptnodeGetNChildren(reoptnode) > 0; 449 } 450 } 451 else 452 return FALSE; 453 } 454 455 /** deletes the given reoptimization node 456 * 457 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 458 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 459 * 460 * @pre This method can be called if @p scip is in one of the following stages: 461 * - \ref SCIP_STAGE_TRANSFORMED 462 * - \ref SCIP_STAGE_SOLVING 463 */ 464 SCIP_RETCODE SCIPdeleteReoptnode( 465 SCIP* scip, /**< SCIP data structure */ 466 SCIP_REOPTNODE** reoptnode /**< node of the reoptimization tree */ 467 ) 468 { 469 assert(scip != NULL); 470 assert(scip->set->reopt_enable); 471 assert(scip->reopt != NULL); 472 assert((*reoptnode) != NULL); 473 474 SCIP_CALL( SCIPcheckStage(scip, "SCIPdeleteReoptnode", FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 475 476 SCIP_CALL( SCIPreoptnodeDelete(reoptnode, scip->mem->probmem) ); 477 478 return SCIP_OKAY; 479 } 480 481 /** splits the root into several nodes and moves the child nodes of the root to one of the created nodes 482 * 483 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 484 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 485 * 486 * @pre This method can be called if @p scip is in one of the following stages: 487 * - \ref SCIP_STAGE_SOLVING 488 */ 489 SCIP_RETCODE SCIPsplitReoptRoot( 490 SCIP* scip, /**< SCIP data structure */ 491 int* ncreatedchilds, /**< pointer to store the number of created nodes */ 492 int* naddedconss /**< pointer to store the number added constraints */ 493 ) 494 { 495 assert(scip != NULL); 496 assert(scip->set->reopt_enable); 497 assert(scip->reopt != NULL); 498 499 SCIP_CALL( SCIPcheckStage(scip, "SCIPsplitReoptRoot", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 500 501 SCIP_CALL( SCIPreoptSplitRoot(scip->reopt, scip->tree, scip->set, scip->stat, scip->mem->probmem, ncreatedchilds, 502 naddedconss) ); 503 504 return SCIP_OKAY; 505 } 506 507 /** remove the stored information about bound changes based in dual information 508 * 509 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 510 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 511 * 512 * @pre This method can be called if @p scip is in one of the following stages: 513 * - \ref SCIP_STAGE_SOLVING 514 * - \ref SCIP_STAGE_SOLVED 515 */ 516 SCIP_RETCODE SCIPresetReoptnodeDualcons( 517 SCIP* scip, /**< SCIP data structure */ 518 SCIP_NODE* node /**< node of the search tree */ 519 ) 520 { 521 assert(scip != NULL); 522 assert(scip->set->reopt_enable); 523 assert(node != NULL); 524 525 SCIP_CALL( SCIPcheckStage(scip, "SCIPresetReoptnodeDualcons", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 526 527 SCIP_CALL( SCIPreoptResetDualBndchgs(scip->reopt, node, scip->mem->probmem) ); 528 529 return SCIP_OKAY; 530 } 531