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_solve.c 26 * @ingroup OTHER_CFILES 27 * @brief public solving methods 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 "blockmemshell/memory.h" 46 #include "scip/branch.h" 47 #include "scip/clock.h" 48 #include "scip/compr.h" 49 #include "scip/concsolver.h" 50 #include "scip/concurrent.h" 51 #include "scip/conflict.h" 52 #include "scip/conflictstore.h" 53 #include "scip/cons.h" 54 #include "scip/cutpool.h" 55 #include "scip/dcmp.h" 56 #include "scip/debug.h" 57 #include "scip/event.h" 58 #include "scip/implics.h" 59 #include "scip/interrupt.h" 60 #include "scip/lp.h" 61 #include "scip/nlp.h" 62 #include "scip/presol.h" 63 #include "scip/pricestore.h" 64 #include "scip/primal.h" 65 #include "scip/prob.h" 66 #include "scip/prop.h" 67 #include "scip/pub_branch.h" 68 #include "scip/pub_compr.h" 69 #include "scip/pub_cons.h" 70 #include "scip/pub_heur.h" 71 #include "scip/pub_message.h" 72 #include "scip/pub_misc.h" 73 #include "scip/pub_misc_select.h" 74 #include "scip/pub_presol.h" 75 #include "scip/pub_prop.h" 76 #include "scip/pub_sol.h" 77 #include "scip/pub_var.h" 78 #include "scip/relax.h" 79 #include "scip/reopt.h" 80 #include "scip/scip_benders.h" 81 #include "scip/scip_branch.h" 82 #include "scip/scip_concurrent.h" 83 #include "scip/scip_cons.h" 84 #include "scip/scip_general.h" 85 #include "scip/scip_lp.h" 86 #include "scip/scip_mem.h" 87 #include "scip/scip_message.h" 88 #include "scip/scip_numerics.h" 89 #include "scip/scip_param.h" 90 #include "scip/scip_prob.h" 91 #include "scip/scip_randnumgen.h" 92 #include "scip/scip_sol.h" 93 #include "scip/scip_solve.h" 94 #include "scip/scip_solvingstats.h" 95 #include "scip/scip_timing.h" 96 #include "scip/scip_tree.h" 97 #include "scip/scip_var.h" 98 #include "scip/sepastore.h" 99 #include "scip/set.h" 100 #include "scip/sol.h" 101 #include "scip/solve.h" 102 #include "scip/stat.h" 103 #include "scip/struct_event.h" 104 #include "scip/struct_mem.h" 105 #include "scip/struct_primal.h" 106 #include "scip/struct_prob.h" 107 #include "scip/struct_scip.h" 108 #include "scip/struct_set.h" 109 #include "scip/struct_stat.h" 110 #include "scip/struct_tree.h" 111 #include "scip/syncstore.h" 112 #include "scip/tree.h" 113 #include "scip/var.h" 114 #include "scip/visual.h" 115 116 /** calculates number of nonzeros in problem */ 117 static 118 SCIP_RETCODE calcNonZeros( 119 SCIP* scip, /**< SCIP data structure */ 120 SCIP_Longint* nchecknonzeros, /**< pointer to store number of non-zeros in all check constraints */ 121 SCIP_Longint* nactivenonzeros, /**< pointer to store number of non-zeros in all active constraints */ 122 SCIP_Bool* approxchecknonzeros,/**< pointer to store if the number of non-zeros in all check constraints 123 * is only a lowerbound 124 */ 125 SCIP_Bool* approxactivenonzeros/**< pointer to store if the number of non-zeros in all active constraints 126 * is only a lowerbound 127 */ 128 ) 129 { 130 SCIP_CONS** conss; 131 SCIP_Bool success; 132 SCIP_Bool ischeck; 133 int nconss; 134 int nvars; 135 int c; 136 int h; 137 138 *nchecknonzeros = 0LL; 139 *nactivenonzeros = 0LL; 140 *approxchecknonzeros = FALSE; 141 *approxactivenonzeros = FALSE; 142 143 /* computes number of non-zeros over all active constraints */ 144 for( h = scip->set->nconshdlrs - 1; h >= 0; --h ) 145 { 146 nconss = SCIPconshdlrGetNActiveConss(scip->set->conshdlrs[h]); 147 148 if( nconss > 0 ) 149 { 150 conss = SCIPconshdlrGetConss(scip->set->conshdlrs[h]); 151 152 /* calculate all active constraints */ 153 for( c = nconss - 1; c >= 0; --c ) 154 { 155 SCIP_CALL( SCIPconsGetNVars(conss[c], scip->set, &nvars, &success) ); 156 ischeck = SCIPconsIsChecked(conss[c]); 157 158 if( !success ) 159 { 160 *approxactivenonzeros = TRUE; 161 if( ischeck ) 162 *approxchecknonzeros = TRUE; 163 } 164 else 165 { 166 *nactivenonzeros += nvars; 167 if( ischeck ) 168 *nchecknonzeros += nvars; 169 } 170 } 171 } 172 173 /* add nonzeros on inactive check constraints */ 174 nconss = SCIPconshdlrGetNCheckConss(scip->set->conshdlrs[h]); 175 if( nconss > 0 ) 176 { 177 conss = SCIPconshdlrGetCheckConss(scip->set->conshdlrs[h]); 178 179 for( c = nconss - 1; c >= 0; --c ) 180 { 181 if( !SCIPconsIsActive(conss[c]) ) 182 { 183 SCIP_CALL( SCIPconsGetNVars(conss[c], scip->set, &nvars, &success) ); 184 185 if( !success ) 186 *approxchecknonzeros = TRUE; 187 else 188 *nchecknonzeros += nvars; 189 } 190 } 191 } 192 } 193 194 return SCIP_OKAY; 195 } 196 197 198 /** initializes solving data structures and transforms problem 199 * 200 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 201 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 202 * 203 * @pre This method can be called if @p scip is in one of the following stages: 204 * - \ref SCIP_STAGE_PROBLEM 205 * - \ref SCIP_STAGE_TRANSFORMED 206 * - \ref SCIP_STAGE_INITPRESOLVE 207 * - \ref SCIP_STAGE_PRESOLVING 208 * - \ref SCIP_STAGE_EXITPRESOLVE 209 * - \ref SCIP_STAGE_PRESOLVED 210 * - \ref SCIP_STAGE_INITSOLVE 211 * - \ref SCIP_STAGE_SOLVING 212 * - \ref SCIP_STAGE_SOLVED 213 * - \ref SCIP_STAGE_EXITSOLVE 214 * - \ref SCIP_STAGE_FREETRANS 215 * - \ref SCIP_STAGE_FREE 216 * 217 * @post When calling this method in the \ref SCIP_STAGE_PROBLEM stage, the \SCIP stage is changed to \ref 218 * SCIP_STAGE_TRANSFORMED; otherwise, the stage is not changed 219 * 220 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 221 */ 222 SCIP_RETCODE SCIPtransformProb( 223 SCIP* scip /**< SCIP data structure */ 224 ) 225 { 226 SCIP_Longint oldnsolsfound; 227 int nfeassols; 228 int ncandsols; 229 int h; 230 int s; 231 232 SCIP_CALL( SCIPcheckStage(scip, "SCIPtransformProb", FALSE, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE) ); 233 234 /* check, if the problem was already transformed */ 235 if( scip->set->stage >= SCIP_STAGE_TRANSFORMED ) 236 return SCIP_OKAY; 237 238 assert(scip->stat->status == SCIP_STATUS_UNKNOWN); 239 240 /* check, if a node selector exists */ 241 if( SCIPsetGetNodesel(scip->set, scip->stat) == NULL ) 242 { 243 SCIPerrorMessage("no node selector available\n"); 244 return SCIP_PLUGINNOTFOUND; 245 } 246 247 /* call garbage collector on original problem and parameter settings memory spaces */ 248 BMSgarbagecollectBlockMemory(scip->mem->setmem); 249 BMSgarbagecollectBlockMemory(scip->mem->probmem); 250 251 /* remember number of constraints */ 252 SCIPprobMarkNConss(scip->origprob); 253 254 /* switch stage to TRANSFORMING */ 255 scip->set->stage = SCIP_STAGE_TRANSFORMING; 256 257 /* mark statistics before solving */ 258 SCIPstatMark(scip->stat); 259 260 /* init solve data structures */ 261 SCIP_CALL( SCIPeventfilterCreate(&scip->eventfilter, scip->mem->probmem) ); 262 SCIP_CALL( SCIPeventqueueCreate(&scip->eventqueue) ); 263 SCIP_CALL( SCIPbranchcandCreate(&scip->branchcand) ); 264 SCIP_CALL( SCIPlpCreate(&scip->lp, scip->set, scip->messagehdlr, scip->stat, SCIPprobGetName(scip->origprob)) ); 265 SCIP_CALL( SCIPprimalCreate(&scip->primal) ); 266 SCIP_CALL( SCIPtreeCreate(&scip->tree, scip->mem->probmem, scip->set, SCIPsetGetNodesel(scip->set, scip->stat)) ); 267 SCIP_CALL( SCIPrelaxationCreate(&scip->relaxation, scip->mem->probmem, scip->set, scip->stat, scip->primal, scip->tree) ); 268 SCIP_CALL( SCIPconflictCreate(&scip->conflict, scip->mem->probmem, scip->set) ); 269 SCIP_CALL( SCIPcliquetableCreate(&scip->cliquetable, scip->set, scip->mem->probmem) ); 270 271 /* copy problem in solve memory */ 272 SCIP_CALL( SCIPprobTransform(scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal, scip->tree, 273 scip->reopt, scip->lp, scip->branchcand, scip->eventfilter, scip->eventqueue, scip->conflictstore, 274 &scip->transprob) ); 275 276 /* switch stage to TRANSFORMED */ 277 scip->set->stage = SCIP_STAGE_TRANSFORMED; 278 279 /* check, whether objective value is always integral by inspecting the problem, if it is the case adjust the 280 * cutoff bound if primal solution is already known 281 */ 282 SCIP_CALL( SCIPprobCheckObjIntegral(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal, 283 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) ); 284 285 /* if possible, scale objective function such that it becomes integral with gcd 1 */ 286 SCIP_CALL( SCIPprobScaleObj(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal, 287 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) ); 288 289 /* check solution of solution candidate storage */ 290 nfeassols = 0; 291 ncandsols = scip->origprimal->nsols; 292 oldnsolsfound = 0; 293 294 /* update upper bound and cutoff bound due to objective limit in primal data */ 295 SCIP_CALL( SCIPprimalUpdateObjlimit(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, 296 scip->eventqueue, scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp) ); 297 298 /* do not consider original solutions of a benders decomposition because their cost information is incomplete */ 299 if( !scip->set->reopt_enable && scip->set->nactivebenders == 0 ) 300 { 301 oldnsolsfound = scip->primal->nsolsfound; 302 for( s = scip->origprimal->nsols - 1; s >= 0; --s ) 303 { 304 SCIP_Bool feasible; 305 SCIP_SOL* sol; 306 307 sol = scip->origprimal->sols[s]; 308 309 /* recompute objective function, since the objective might have changed in the meantime */ 310 SCIPsolRecomputeObj(sol, scip->set, scip->stat, scip->origprob); 311 312 /* SCIPprimalTrySol() can only be called on transformed solutions; therefore check solutions in original problem 313 * including modifiable constraints 314 */ 315 SCIP_CALL( SCIPsolCheckOrig(sol, scip->set, scip->messagehdlr, scip->mem->probmem, scip->stat, scip->origprob, scip->origprimal, 316 (scip->set->disp_verblevel >= SCIP_VERBLEVEL_HIGH ? scip->set->misc_printreason : FALSE), 317 FALSE, TRUE, TRUE, TRUE, TRUE, &feasible) ); 318 319 if( feasible ) 320 { 321 SCIP_Real abssolobj; 322 323 abssolobj = REALABS(SCIPsolGetObj(sol, scip->set, scip->transprob, scip->origprob)); 324 325 /* we do not want to add solutions with objective value +infinity */ 326 if( !SCIPisInfinity(scip, abssolobj) ) 327 { 328 SCIP_SOL* bestsol = SCIPgetBestSol(scip); 329 SCIP_Bool stored; 330 331 /* add primal solution to solution storage by copying it */ 332 SCIP_CALL( SCIPprimalAddSol(scip->primal, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->origprob, scip->transprob, 333 scip->tree, scip->reopt, scip->lp, scip->eventqueue, scip->eventfilter, sol, &stored) ); 334 335 if( stored ) 336 { 337 nfeassols++; 338 339 if( bestsol != SCIPgetBestSol(scip) ) 340 SCIPstoreSolutionGap(scip); 341 } 342 } 343 } 344 345 SCIP_CALL( SCIPsolFree(&sol, scip->mem->probmem, scip->origprimal) ); 346 scip->origprimal->nsols--; 347 } 348 } 349 350 assert(scip->origprimal->nsols == 0); 351 352 scip->stat->nexternalsolsfound += scip->primal->nsolsfound - oldnsolsfound; 353 354 if( nfeassols > 0 ) 355 { 356 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 357 "%d/%d feasible solution%s given by solution candidate storage, new primal bound %.6e\n\n", 358 nfeassols, ncandsols, (nfeassols > 1 ? "s" : ""), SCIPgetSolOrigObj(scip, SCIPgetBestSol(scip))); 359 } 360 else if( ncandsols > 0 && !scip->set->reopt_enable ) 361 { 362 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 363 "all %d solutions given by solution candidate storage are infeasible\n\n", ncandsols); 364 } 365 366 /* print transformed problem statistics */ 367 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 368 "transformed problem has %d variables (%d bin, %d int, %d impl, %d cont) and %d constraints\n", 369 scip->transprob->nvars, scip->transprob->nbinvars, scip->transprob->nintvars, scip->transprob->nimplvars, 370 scip->transprob->ncontvars, scip->transprob->nconss); 371 372 for( h = 0; h < scip->set->nconshdlrs; ++h ) 373 { 374 int nactiveconss; 375 376 nactiveconss = SCIPconshdlrGetNActiveConss(scip->set->conshdlrs[h]); 377 if( nactiveconss > 0 ) 378 { 379 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 380 "%7d constraints of type <%s>\n", nactiveconss, SCIPconshdlrGetName(scip->set->conshdlrs[h])); 381 } 382 } 383 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, "\n"); 384 385 { 386 SCIP_Real maxnonzeros; 387 SCIP_Longint nchecknonzeros; 388 SCIP_Longint nactivenonzeros; 389 SCIP_Bool approxchecknonzeros; 390 SCIP_Bool approxactivenonzeros; 391 392 /* determine number of non-zeros */ 393 maxnonzeros = (SCIP_Real)SCIPgetNConss(scip) * SCIPgetNVars(scip); 394 maxnonzeros = MAX(maxnonzeros, 1.0); 395 SCIP_CALL( calcNonZeros(scip, &nchecknonzeros, &nactivenonzeros, &approxchecknonzeros, &approxactivenonzeros) ); 396 scip->stat->nnz = nactivenonzeros; 397 scip->stat->avgnnz = (SCIPgetNConss(scip) == 0 ? 0.0 : (SCIP_Real) nactivenonzeros / ((SCIP_Real) SCIPgetNConss(scip))); 398 399 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 400 "original problem has %s%" SCIP_LONGINT_FORMAT " active (%g%%) nonzeros and %s%" SCIP_LONGINT_FORMAT " (%g%%) check nonzeros\n", 401 approxactivenonzeros ? "more than " : "", nactivenonzeros, nactivenonzeros/maxnonzeros * 100, 402 approxchecknonzeros ? "more than " : "", nchecknonzeros, nchecknonzeros/maxnonzeros * 100); 403 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, "\n"); 404 } 405 406 /* call initialization methods of plugins */ 407 SCIP_CALL( SCIPsetInitPlugins(scip->set, scip->mem->probmem, scip->stat) ); 408 409 /* in case the permutation seed is different to 0, permute the transformed problem */ 410 if( scip->set->random_permutationseed > 0 ) 411 { 412 SCIP_Bool permuteconss; 413 SCIP_Bool permutevars; 414 int permutationseed; 415 416 permuteconss = scip->set->random_permuteconss; 417 permutevars = scip->set->random_permutevars; 418 permutationseed = scip->set->random_permutationseed; 419 420 SCIP_CALL( SCIPpermuteProb(scip, (unsigned int)permutationseed, permuteconss, permutevars, permutevars, permutevars, permutevars) ); 421 } 422 423 if( scip->set->misc_estimexternmem ) 424 { 425 /* the following formula was estimated empirically using linear regression */ 426 scip->stat->externmemestim = (SCIP_Longint) (MAX(1, 8.5e-04 * SCIPgetNConss(scip) + 7.6e-04 * SCIPgetNVars(scip) + 3.5e-05 * scip->stat->nnz) * 1048576.0); /*lint !e666*/ 427 SCIPdebugMsg(scip, "external memory usage estimated to %" SCIP_LONGINT_FORMAT " byte\n", scip->stat->externmemestim); 428 } 429 430 return SCIP_OKAY; 431 } 432 433 /** initializes presolving */ 434 static 435 SCIP_RETCODE initPresolve( 436 SCIP* scip /**< SCIP data structure */ 437 ) 438 { 439 #ifndef NDEBUG 440 size_t nusedbuffers; 441 size_t nusedcleanbuffers; 442 #endif 443 444 assert(scip != NULL); 445 assert(scip->mem != NULL); 446 assert(scip->set != NULL); 447 assert(scip->stat != NULL); 448 assert(scip->transprob != NULL); 449 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED); 450 451 /* retransform all existing solutions to original problem space, because the transformed problem space may 452 * get modified in presolving and the solutions may become invalid for the transformed problem 453 */ 454 SCIP_CALL( SCIPprimalRetransformSolutions(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, 455 scip->eventqueue, scip->origprob, scip->transprob, scip->tree, scip->reopt, scip->lp) ); 456 457 /* reset statistics for presolving and current branch and bound run */ 458 SCIPstatResetPresolving(scip->stat, scip->set, scip->transprob, scip->origprob); 459 460 /* increase number of branch and bound runs */ 461 scip->stat->nruns++; 462 463 /* remember problem size of previous run */ 464 scip->stat->prevrunnvars = scip->transprob->nvars; 465 466 /* switch stage to INITPRESOLVE */ 467 scip->set->stage = SCIP_STAGE_INITPRESOLVE; 468 469 /* create temporary presolving root node */ 470 SCIP_CALL( SCIPtreeCreatePresolvingRoot(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->messagehdlr, 471 scip->stat, scip->transprob, scip->origprob, scip->primal, scip->lp, scip->branchcand, scip->conflict, 472 scip->conflictstore, scip->eventfilter, scip->eventqueue, scip->cliquetable) ); 473 474 /* GCG wants to perform presolving during the reading process of a file reader; 475 * hence the number of used buffers does not need to be zero, however, it should not 476 * change by calling SCIPsetInitprePlugins() 477 */ 478 #ifndef NDEBUG 479 nusedbuffers = BMSgetNUsedBufferMemory(SCIPbuffer(scip)); 480 nusedcleanbuffers = BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)); 481 #endif 482 483 /* inform plugins that the presolving is abound to begin */ 484 SCIP_CALL( SCIPsetInitprePlugins(scip->set, scip->mem->probmem, scip->stat) ); 485 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers); 486 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers); 487 488 /* delete the variables from the problems that were marked to be deleted */ 489 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->cliquetable, scip->lp, scip->branchcand) ); 490 491 /* switch stage to PRESOLVING */ 492 scip->set->stage = SCIP_STAGE_PRESOLVING; 493 494 return SCIP_OKAY; 495 } 496 497 /** deinitializes presolving */ 498 static 499 SCIP_RETCODE exitPresolve( 500 SCIP* scip, /**< SCIP data structure */ 501 SCIP_Bool solved, /**< is problem already solved? */ 502 SCIP_Bool* infeasible /**< pointer to store if the clique clean up detects an infeasibility */ 503 ) 504 { 505 #ifndef NDEBUG 506 size_t nusedbuffers; 507 size_t nusedcleanbuffers; 508 #endif 509 510 assert(scip != NULL); 511 assert(scip->mem != NULL); 512 assert(scip->set != NULL); 513 assert(scip->stat != NULL); 514 assert(scip->transprob != NULL); 515 assert(scip->set->stage == SCIP_STAGE_PRESOLVING); 516 assert(infeasible != NULL); 517 518 *infeasible = FALSE; 519 520 /* switch stage to EXITPRESOLVE */ 521 scip->set->stage = SCIP_STAGE_EXITPRESOLVE; 522 523 if( !solved ) 524 { 525 SCIP_VAR** vars; 526 int nvars; 527 int v; 528 529 /* flatten all variables */ 530 vars = SCIPgetFixedVars(scip); 531 nvars = SCIPgetNFixedVars(scip); 532 assert(nvars == 0 || vars != NULL); 533 534 for( v = nvars - 1; v >= 0; --v ) 535 { 536 SCIP_VAR* var; 537 #ifndef NDEBUG 538 SCIP_VAR** multvars; 539 int i; 540 #endif 541 var = vars[v]; /*lint !e613*/ 542 assert(var != NULL); 543 544 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 545 { 546 /* flattens aggregation graph of multi-aggregated variable in order to avoid exponential recursion later-on */ 547 SCIP_CALL( SCIPvarFlattenAggregationGraph(var, scip->mem->probmem, scip->set, scip->eventqueue) ); 548 549 #ifndef NDEBUG 550 multvars = SCIPvarGetMultaggrVars(var); 551 for( i = SCIPvarGetMultaggrNVars(var) - 1; i >= 0; --i) 552 assert(SCIPvarGetStatus(multvars[i]) != SCIP_VARSTATUS_MULTAGGR); 553 #endif 554 } 555 } 556 } 557 558 /* exitPresolve() might be called during the reading process of a file reader; 559 * hence the number of used buffers does not need to be zero, however, it should not 560 * change by calling SCIPsetExitprePlugins() or SCIPprobExitPresolve() 561 */ 562 #ifndef NDEBUG 563 nusedbuffers = BMSgetNUsedBufferMemory(SCIPbuffer(scip)); 564 nusedcleanbuffers = BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)); 565 #endif 566 567 /* inform plugins that the presolving is finished, and perform final modifications */ 568 SCIP_CALL( SCIPsetExitprePlugins(scip->set, scip->mem->probmem, scip->stat) ); 569 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers); 570 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers); 571 572 /* remove empty and single variable cliques from the clique table, and convert all two variable cliques 573 * into implications 574 * delete the variables from the problems that were marked to be deleted 575 */ 576 if( !solved ) 577 { 578 int nlocalbdchgs = 0; 579 580 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, 581 scip->cliquetable, scip->lp, scip->branchcand) ); 582 583 SCIP_CALL( SCIPcliquetableCleanup(scip->cliquetable, scip->mem->probmem, scip->set, scip->stat, scip->transprob, 584 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, &nlocalbdchgs, 585 infeasible) ); 586 587 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 588 "clique table cleanup detected %d bound changes%s\n", nlocalbdchgs, *infeasible ? " and infeasibility" : ""); 589 } 590 591 /* exit presolving */ 592 SCIP_CALL( SCIPprobExitPresolve(scip->transprob, scip->set) ); 593 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers); 594 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers); 595 596 if( !solved ) 597 { 598 /* check, whether objective value is always integral by inspecting the problem, if it is the case adjust the 599 * cutoff bound if primal solution is already known 600 */ 601 SCIP_CALL( SCIPprobCheckObjIntegral(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal, 602 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) ); 603 604 /* if possible, scale objective function such that it becomes integral with gcd 1 */ 605 SCIP_CALL( SCIPprobScaleObj(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal, 606 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) ); 607 608 scip->stat->lastlowerbound = SCIPprobInternObjval(scip->transprob, scip->origprob, scip->set, scip->transprob->dualbound); 609 610 /* we need to update the primal dual integral here to update the last{upper/dual}bound values after a restart */ 611 if( scip->set->misc_calcintegral ) 612 { 613 SCIPstatUpdatePrimalDualIntegrals(scip->stat, scip->set, scip->transprob, scip->origprob, SCIPgetUpperbound(scip), SCIPgetLowerbound(scip) ); 614 } 615 } 616 617 /* free temporary presolving root node */ 618 SCIP_CALL( SCIPtreeFreePresolvingRoot(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->messagehdlr, 619 scip->stat, scip->transprob, scip->origprob, scip->primal, scip->lp, scip->branchcand, scip->conflict, 620 scip->conflictstore, scip->eventfilter, scip->eventqueue, scip->cliquetable) ); 621 622 /* switch stage to PRESOLVED */ 623 scip->set->stage = SCIP_STAGE_PRESOLVED; 624 625 return SCIP_OKAY; 626 } 627 628 /** applies one round of presolving with the given presolving timing 629 * 630 * This method will always be called with presoltiming fast first. It iterates over all presolvers, propagators, and 631 * constraint handlers and calls their presolving callbacks with timing fast. If enough reductions are found, it 632 * returns and the next presolving round will be started (again with timing fast). If the fast presolving does not 633 * find enough reductions, this methods calls itself recursively with presoltiming medium. Again, it calls the 634 * presolving callbacks of all presolvers, propagators, and constraint handlers with timing medium. If enough 635 * reductions are found, it returns and the next presolving round will be started (with timing fast). Otherwise, it is 636 * called recursively with presoltiming exhaustive. In exhaustive presolving, presolvers, propagators, and constraint 637 * handlers are called w.r.t. their priority, but this time, we stop as soon as enough reductions were found and do not 638 * necessarily call all presolving methods. If we stop, we return and another presolving round is started with timing 639 * fast. 640 * 641 * @todo check if we want to do the following (currently disabled): 642 * In order to avoid calling the same expensive presolving methods again and again (which is possibly ineffective 643 * for the current instance), we continue the loop for exhaustive presolving where we stopped it the last time. The 644 * {presol/prop/cons}start pointers are used to this end: they provide the plugins to start the loop with in the 645 * current presolving round (if we reach exhaustive presolving), and are updated in this case to the next ones to be 646 * called in the next round. In case we reach the end of the loop in exhaustive presolving, we call the method again 647 * with exhaustive timing, now starting with the first presolving steps in the loop until we reach the ones we started 648 * the last call with. This way, we won't stop until all exhaustive presolvers were called without finding enough 649 * reductions (in sum). 650 */ 651 static 652 SCIP_RETCODE presolveRound( 653 SCIP* scip, /**< SCIP data structure */ 654 SCIP_PRESOLTIMING* timing, /**< pointer to current presolving timing */ 655 SCIP_Bool* unbounded, /**< pointer to store whether presolving detected unboundedness */ 656 SCIP_Bool* infeasible, /**< pointer to store whether presolving detected infeasibility */ 657 SCIP_Bool lastround, /**< is this the last presolving round due to a presolving round limit? */ 658 int* presolstart, /**< pointer to get the presolver to start exhaustive presolving with in 659 * the current round and store the one to start with in the next round */ 660 int presolend, /**< last presolver to treat in exhaustive presolving */ 661 int* propstart, /**< pointer to get the propagator to start exhaustive presolving with in 662 * the current round and store the one to start with in the next round */ 663 int propend, /**< last propagator to treat in exhaustive presolving */ 664 int* consstart, /**< pointer to get the constraint handler to start exhaustive presolving with in 665 * the current round and store the one to start with in the next round */ 666 int consend /**< last constraint handler to treat in exhaustive presolving */ 667 ) 668 { 669 SCIP_RESULT result; 670 SCIP_EVENT event; 671 SCIP_Bool aborted; 672 SCIP_Bool lastranpresol; 673 #if 0 674 int oldpresolstart = 0; 675 int oldpropstart = 0; 676 int oldconsstart = 0; 677 #endif 678 int priopresol; 679 int prioprop; 680 int i; 681 int j; 682 int k; 683 #ifndef NDEBUG 684 size_t nusedbuffers; 685 size_t nusedcleanbuffers; 686 #endif 687 688 assert(scip != NULL); 689 assert(scip->set != NULL); 690 assert(unbounded != NULL); 691 assert(infeasible != NULL); 692 assert(presolstart != NULL); 693 assert(propstart != NULL); 694 assert(consstart != NULL); 695 696 assert((presolend == scip->set->npresols && propend == scip->set->nprops && consend == scip->set->nconshdlrs) 697 || (*presolstart == 0 && *propstart == 0 && *consstart == 0)); 698 699 *unbounded = FALSE; 700 *infeasible = FALSE; 701 aborted = FALSE; 702 703 assert( scip->set->propspresolsorted ); 704 705 /* GCG wants to perform presolving during the reading process of a file reader; 706 * hence the number of used buffers does not need to be zero, however, it should not 707 * change by calling the presolving callbacks 708 */ 709 #ifndef NDEBUG 710 nusedbuffers = BMSgetNUsedBufferMemory(SCIPbuffer(scip)); 711 nusedcleanbuffers = BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)); 712 #endif 713 714 if( *timing == SCIP_PRESOLTIMING_EXHAUSTIVE ) 715 { 716 /* In exhaustive presolving, we continue the loop where we stopped last time to avoid calling the same 717 * (possibly ineffective) presolving step again and again. If we reach the end of the arrays of presolvers, 718 * propagators, and constraint handlers without having made enough reductions, we start again from the beginning 719 */ 720 i = *presolstart; 721 j = *propstart; 722 k = *consstart; 723 #if 0 724 oldpresolstart = i; 725 oldpropstart = j; 726 oldconsstart = k; 727 #endif 728 if( i >= presolend && j >= propend && k >= consend ) 729 return SCIP_OKAY; 730 731 if( i == 0 && j == 0 && k == 0 ) 732 ++(scip->stat->npresolroundsext); 733 } 734 else 735 { 736 /* in fast and medium presolving, we always iterate over all presolvers, propagators, and constraint handlers */ 737 assert(presolend == scip->set->npresols); 738 assert(propend == scip->set->nprops); 739 assert(consend == scip->set->nconshdlrs); 740 741 i = 0; 742 j = 0; 743 k = 0; 744 745 if( *timing == SCIP_PRESOLTIMING_FAST ) 746 ++(scip->stat->npresolroundsfast); 747 if( *timing == SCIP_PRESOLTIMING_MEDIUM ) 748 ++(scip->stat->npresolroundsmed); 749 } 750 751 SCIPdebugMsg(scip, "starting presolving round %d (%d/%d/%d), timing = %u\n", 752 scip->stat->npresolrounds, scip->stat->npresolroundsfast, scip->stat->npresolroundsmed, 753 scip->stat->npresolroundsext, *timing); 754 755 /* call included presolvers with nonnegative priority */ 756 while( !(*unbounded) && !(*infeasible) && !aborted && (i < presolend || j < propend) ) 757 { 758 if( i < presolend ) 759 priopresol = SCIPpresolGetPriority(scip->set->presols[i]); 760 else 761 priopresol = -1; 762 763 if( j < propend ) 764 prioprop = SCIPpropGetPresolPriority(scip->set->props_presol[j]); 765 else 766 prioprop = -1; 767 768 /* call next propagator */ 769 if( prioprop >= priopresol ) 770 { 771 /* only presolving methods which have non-negative priority will be called before constraint handlers */ 772 if( prioprop < 0 ) 773 break; 774 775 SCIPdebugMsg(scip, "executing presolving of propagator <%s>\n", SCIPpropGetName(scip->set->props_presol[j])); 776 SCIP_CALL( SCIPpropPresol(scip->set->props_presol[j], scip->set, *timing, scip->stat->npresolrounds, 777 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes, 778 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss, 779 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs, 780 &scip->stat->npresolchgsides, &result) ); 781 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers); 782 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers); 783 784 lastranpresol = FALSE; 785 ++j; 786 } 787 /* call next presolver */ 788 else 789 { 790 /* only presolving methods which have non-negative priority will be called before constraint handlers */ 791 if( priopresol < 0 ) 792 break; 793 794 SCIPdebugMsg(scip, "executing presolver <%s>\n", SCIPpresolGetName(scip->set->presols[i])); 795 SCIP_CALL( SCIPpresolExec(scip->set->presols[i], scip->set, *timing, scip->stat->npresolrounds, 796 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes, 797 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss, 798 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs, 799 &scip->stat->npresolchgsides, &result) ); 800 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers); 801 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers); 802 803 lastranpresol = TRUE; 804 ++i; 805 } 806 807 if( result == SCIP_CUTOFF ) 808 { 809 *infeasible = TRUE; 810 811 if( lastranpresol ) 812 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 813 "presolver <%s> detected infeasibility\n", SCIPpresolGetName(scip->set->presols[i-1])); 814 else 815 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 816 "propagator <%s> detected infeasibility\n", SCIPpropGetName(scip->set->props_presol[j-1])); 817 } 818 else if( result == SCIP_UNBOUNDED ) 819 { 820 *unbounded = TRUE; 821 822 if( lastranpresol ) 823 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 824 "presolver <%s> detected unboundedness (or infeasibility)\n", SCIPpresolGetName(scip->set->presols[i-1])); 825 else 826 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 827 "propagator <%s> detected unboundedness (or infeasibility)\n", SCIPpropGetName(scip->set->props_presol[j-1])); 828 } 829 830 /* delete the variables from the problems that were marked to be deleted */ 831 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->cliquetable, scip->lp, 832 scip->branchcand) ); 833 834 SCIPdebugMsg(scip, "presolving callback returned result <%d>\n", result); 835 836 /* if we work off the exhaustive presolvers, we stop immediately if a reduction was found */ 837 if( (*timing == SCIP_PRESOLTIMING_EXHAUSTIVE) && !lastround && !SCIPisPresolveFinished(scip) ) 838 { 839 assert(*consstart == 0); 840 841 if( lastranpresol ) 842 { 843 *presolstart = i + 1; 844 *propstart = j; 845 } 846 else 847 { 848 *presolstart = i; 849 *propstart = j + 1; 850 } 851 aborted = TRUE; 852 853 break; 854 } 855 } 856 857 /* call presolve methods of constraint handlers */ 858 while( k < consend && !(*unbounded) && !(*infeasible) && !aborted ) 859 { 860 SCIPdebugMsg(scip, "executing presolve method of constraint handler <%s>\n", 861 SCIPconshdlrGetName(scip->set->conshdlrs[k])); 862 SCIP_CALL( SCIPconshdlrPresolve(scip->set->conshdlrs[k], scip->mem->probmem, scip->set, scip->stat, 863 *timing, scip->stat->npresolrounds, 864 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes, 865 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss, 866 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs, 867 &scip->stat->npresolchgsides, &result) ); 868 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers); 869 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers); 870 871 ++k; 872 873 if( result == SCIP_CUTOFF ) 874 { 875 *infeasible = TRUE; 876 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 877 "constraint handler <%s> detected infeasibility\n", SCIPconshdlrGetName(scip->set->conshdlrs[k-1])); 878 } 879 else if( result == SCIP_UNBOUNDED ) 880 { 881 *unbounded = TRUE; 882 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 883 "constraint handler <%s> detected unboundedness (or infeasibility)\n", 884 SCIPconshdlrGetName(scip->set->conshdlrs[k-1])); 885 } 886 887 /* delete the variables from the problems that were marked to be deleted */ 888 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->cliquetable, scip->lp, 889 scip->branchcand) ); 890 891 SCIPdebugMsg(scip, "presolving callback returned with result <%d>\n", result); 892 893 /* if we work off the exhaustive presolvers, we stop immediately if a reduction was found */ 894 if( (*timing == SCIP_PRESOLTIMING_EXHAUSTIVE) && !lastround && !SCIPisPresolveFinished(scip) ) 895 { 896 *presolstart = i; 897 *propstart = j; 898 *consstart = k + 1; 899 aborted = TRUE; 900 901 break; 902 } 903 } 904 905 assert( scip->set->propspresolsorted ); 906 907 /* call included presolvers with negative priority */ 908 while( !(*unbounded) && !(*infeasible) && !aborted && (i < presolend || j < propend) ) 909 { 910 if( i < scip->set->npresols ) 911 priopresol = SCIPpresolGetPriority(scip->set->presols[i]); 912 else 913 priopresol = -INT_MAX; 914 915 if( j < scip->set->nprops ) 916 prioprop = SCIPpropGetPresolPriority(scip->set->props_presol[j]); 917 else 918 prioprop = -INT_MAX; 919 920 /* choose presolving */ 921 if( prioprop >= priopresol ) 922 { 923 assert(prioprop <= 0); 924 925 SCIPdebugMsg(scip, "executing presolving of propagator <%s>\n", SCIPpropGetName(scip->set->props_presol[j])); 926 SCIP_CALL( SCIPpropPresol(scip->set->props_presol[j], scip->set, *timing, scip->stat->npresolrounds, 927 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes, 928 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss, 929 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs, 930 &scip->stat->npresolchgsides, &result) ); 931 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers); 932 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers); 933 934 lastranpresol = FALSE; 935 ++j; 936 } 937 else 938 { 939 assert(priopresol < 0); 940 941 SCIPdebugMsg(scip, "executing presolver <%s>\n", SCIPpresolGetName(scip->set->presols[i])); 942 SCIP_CALL( SCIPpresolExec(scip->set->presols[i], scip->set, *timing, scip->stat->npresolrounds, 943 &scip->stat->npresolfixedvars, &scip->stat->npresolaggrvars, &scip->stat->npresolchgvartypes, 944 &scip->stat->npresolchgbds, &scip->stat->npresoladdholes, &scip->stat->npresoldelconss, 945 &scip->stat->npresoladdconss, &scip->stat->npresolupgdconss, &scip->stat->npresolchgcoefs, 946 &scip->stat->npresolchgsides, &result) ); 947 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers); 948 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers); 949 950 lastranpresol = TRUE; 951 ++i; 952 } 953 954 if( result == SCIP_CUTOFF ) 955 { 956 *infeasible = TRUE; 957 958 if( lastranpresol ) 959 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 960 "presolver <%s> detected infeasibility\n", SCIPpresolGetName(scip->set->presols[i-1])); 961 else 962 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 963 "propagator <%s> detected infeasibility\n", SCIPpropGetName(scip->set->props_presol[j-1])); 964 } 965 else if( result == SCIP_UNBOUNDED ) 966 { 967 *unbounded = TRUE; 968 969 if( lastranpresol ) 970 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 971 "presolver <%s> detected unboundedness (or infeasibility)\n", SCIPpresolGetName(scip->set->presols[i-1])); 972 else 973 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 974 "propagator <%s> detected unboundedness (or infeasibility)\n", SCIPpropGetName(scip->set->props_presol[j-1])); 975 } 976 977 /* delete the variables from the problems that were marked to be deleted */ 978 SCIP_CALL( SCIPprobPerformVarDeletions(scip->transprob, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->cliquetable, scip->lp, 979 scip->branchcand) ); 980 981 SCIPdebugMsg(scip, "presolving callback return with result <%d>\n", result); 982 983 /* if we work off the exhaustive presolvers, we stop immediately if a reduction was found */ 984 if( (*timing == SCIP_PRESOLTIMING_EXHAUSTIVE) && !lastround && !SCIPisPresolveFinished(scip) ) 985 { 986 assert(k == consend); 987 988 if( lastranpresol ) 989 { 990 *presolstart = i + 1; 991 *propstart = j; 992 } 993 else 994 { 995 *presolstart = i; 996 *propstart = j + 1; 997 } 998 *consstart = k; 999 1000 break; 1001 } 1002 } 1003 1004 /* remove empty and single variable cliques from the clique table */ 1005 if( !(*unbounded) && !(*infeasible) ) 1006 { 1007 int nlocalbdchgs = 0; 1008 1009 SCIP_CALL( SCIPcliquetableCleanup(scip->cliquetable, scip->mem->probmem, scip->set, scip->stat, scip->transprob, 1010 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, &nlocalbdchgs, 1011 infeasible) ); 1012 1013 if( nlocalbdchgs > 0 || *infeasible ) 1014 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 1015 "clique table cleanup detected %d bound changes%s\n", nlocalbdchgs, *infeasible ? " and infeasibility" : ""); 1016 1017 scip->stat->npresolfixedvars += nlocalbdchgs; 1018 1019 /* do not call heuristics during presolving on a benders decomposition 1020 * because the cost information of the retransformed original solutions would be incomplete 1021 */ 1022 if( !*infeasible && scip->set->nheurs > 0 && scip->set->nactivebenders == 0 ) 1023 { 1024 /* call primal heuristics that are applicable during presolving */ 1025 SCIP_Bool foundsol; 1026 1027 SCIPdebugMsg(scip, "calling primal heuristics during presolving\n"); 1028 1029 /* call primal heuristics */ 1030 SCIP_CALL( SCIPprimalHeuristics(scip->set, scip->stat, scip->transprob, scip->primal, NULL, NULL, NULL, 1031 SCIP_HEURTIMING_DURINGPRESOLLOOP, FALSE, &foundsol, unbounded) ); 1032 1033 /* output a message, if a solution was found */ 1034 if( foundsol ) 1035 { 1036 SCIP_SOL* sol; 1037 1038 assert(SCIPgetNSols(scip) > 0); 1039 sol = SCIPgetBestSol(scip); 1040 assert(sol != NULL); 1041 assert(SCIPgetSolOrigObj(scip,sol) != SCIP_INVALID); /*lint !e777*/ 1042 1043 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 1044 "feasible solution found by %s heuristic after %.1f seconds, objective value %.6e\n", 1045 SCIPheurGetName(SCIPsolGetHeur(sol)), SCIPgetSolvingTime(scip), SCIPgetSolOrigObj(scip, sol)); 1046 } 1047 } 1048 } 1049 1050 if( !(*unbounded) && !(*infeasible) ) 1051 { 1052 /* call more expensive presolvers */ 1053 if( (SCIPisPresolveFinished(scip) || lastround) ) 1054 { 1055 if( *timing != SCIP_PRESOLTIMING_FINAL ) 1056 { 1057 assert((*timing == SCIP_PRESOLTIMING_FAST) || (*timing == SCIP_PRESOLTIMING_MEDIUM) || (*timing == SCIP_PRESOLTIMING_EXHAUSTIVE)); 1058 1059 SCIPdebugMsg(scip, "not enough reductions in %s presolving, running %s presolving now...\n", 1060 *timing == SCIP_PRESOLTIMING_FAST ? "fast" : *timing == SCIP_PRESOLTIMING_MEDIUM ? "medium" : "exhaustive", 1061 *timing == SCIP_PRESOLTIMING_FAST ? "medium" : *timing == SCIP_PRESOLTIMING_MEDIUM ? "exhaustive" : "final"); 1062 1063 /* increase timing */ 1064 *timing = ((*timing == SCIP_PRESOLTIMING_FAST) ? SCIP_PRESOLTIMING_MEDIUM : (*timing == SCIP_PRESOLTIMING_MEDIUM) ? SCIP_PRESOLTIMING_EXHAUSTIVE : SCIP_PRESOLTIMING_FINAL); 1065 1066 /* computational experiments showed that always starting the loop of exhaustive presolvers from the beginning 1067 * performs better than continuing from the last processed presolver. Therefore, we start from 0, but keep 1068 * the mechanisms to possibly change this back later. 1069 * @todo try starting from the last processed exhaustive presolver 1070 */ 1071 *presolstart = 0; 1072 *propstart = 0; 1073 *consstart = 0; 1074 1075 SCIP_CALL( presolveRound(scip, timing, unbounded, infeasible, lastround, presolstart, presolend, 1076 propstart, propend, consstart, consend) ); 1077 } 1078 #if 0 1079 /* run remaining exhaustive presolvers (if we did not start from the beginning anyway) */ 1080 else if( (oldpresolstart > 0 || oldpropstart > 0 || oldconsstart > 0) && presolend == scip->set->npresols 1081 && propend == scip->set->nprops && consend == scip->set->nconshdlrs ) 1082 { 1083 int newpresolstart = 0; 1084 int newpropstart = 0; 1085 int newconsstart = 0; 1086 1087 SCIPdebugMsg(scip, "reached end of exhaustive presolving loop, starting from the beginning...\n"); 1088 1089 SCIP_CALL( presolveRound(scip, timing, unbounded, infeasible, lastround, &newpresolstart, 1090 oldpresolstart, &newpropstart, oldpropstart, &newconsstart, oldconsstart) ); 1091 1092 *presolstart = newpresolstart; 1093 *propstart = newpropstart; 1094 *consstart = newconsstart; 1095 } 1096 #endif 1097 } 1098 } 1099 1100 /* issue PRESOLVEROUND event */ 1101 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_PRESOLVEROUND) ); 1102 SCIP_CALL( SCIPeventProcess(&event, scip->set, NULL, NULL, NULL, scip->eventfilter) ); 1103 1104 return SCIP_OKAY; 1105 } 1106 1107 1108 /** loops through the included presolvers and constraint's presolve methods, until changes are too few */ 1109 static 1110 SCIP_RETCODE presolve( 1111 SCIP* scip, /**< SCIP data structure */ 1112 SCIP_Bool* unbounded, /**< pointer to store whether presolving detected unboundedness */ 1113 SCIP_Bool* infeasible, /**< pointer to store whether presolving detected infeasibility */ 1114 SCIP_Bool* vanished /**< pointer to store whether the problem vanished in presolving */ 1115 ) 1116 { 1117 SCIP_PRESOLTIMING presoltiming; 1118 SCIP_Bool finished; 1119 SCIP_Bool stopped; 1120 SCIP_Bool lastround; 1121 int presolstart = 0; 1122 int propstart = 0; 1123 int consstart = 0; 1124 #ifndef NDEBUG 1125 size_t nusedbuffers; 1126 size_t nusedcleanbuffers; 1127 #endif 1128 1129 assert(scip != NULL); 1130 assert(scip->mem != NULL); 1131 assert(scip->primal != NULL); 1132 assert(scip->set != NULL); 1133 assert(scip->stat != NULL); 1134 assert(scip->transprob != NULL); 1135 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED || scip->set->stage == SCIP_STAGE_PRESOLVING); 1136 assert(unbounded != NULL); 1137 assert(infeasible != NULL); 1138 1139 *unbounded = FALSE; 1140 *vanished = FALSE; 1141 1142 /* GCG wants to perform presolving during the reading process of a file reader; 1143 * hence the number of used buffers does not need to be zero, however, it should 1144 * be the same again after presolve is finished 1145 */ 1146 #ifndef NDEBUG 1147 nusedbuffers = BMSgetNUsedBufferMemory(SCIPbuffer(scip)); 1148 nusedcleanbuffers = BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)); 1149 #endif 1150 1151 /* switch status to unknown */ 1152 scip->stat->status = SCIP_STATUS_UNKNOWN; 1153 1154 /* update upper bound and cutoff bound due to objective limit in primal data */ 1155 SCIP_CALL( SCIPprimalUpdateObjlimit(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, 1156 scip->eventqueue, scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp) ); 1157 1158 /* start presolving timer */ 1159 SCIPclockStart(scip->stat->presolvingtime, scip->set); 1160 SCIPclockStart(scip->stat->presolvingtimeoverall, scip->set); 1161 1162 /* initialize presolving */ 1163 if( scip->set->stage == SCIP_STAGE_TRANSFORMED ) 1164 { 1165 SCIP_CALL( initPresolve(scip) ); 1166 } 1167 assert(scip->set->stage == SCIP_STAGE_PRESOLVING); 1168 1169 /* call primal heuristics that are applicable before presolving but not on a benders decomposition 1170 * because the cost information of the retransformed original solutions would be incomplete 1171 */ 1172 if( scip->set->nheurs > 0 && scip->set->nactivebenders == 0 ) 1173 { 1174 SCIP_Bool foundsol; 1175 1176 SCIPdebugMsg(scip, "calling primal heuristics before presolving\n"); 1177 1178 /* call primal heuristics */ 1179 SCIP_CALL( SCIPprimalHeuristics(scip->set, scip->stat, scip->transprob, scip->primal, NULL, NULL, NULL, 1180 SCIP_HEURTIMING_BEFOREPRESOL, FALSE, &foundsol, unbounded) ); 1181 1182 /* output a message, if a solution was found */ 1183 if( foundsol ) 1184 { 1185 SCIP_SOL* sol; 1186 1187 assert(SCIPgetNSols(scip) > 0); 1188 sol = SCIPgetBestSol(scip); 1189 assert(sol != NULL); 1190 assert(SCIPgetSolOrigObj(scip,sol) != SCIP_INVALID); /*lint !e777*/ 1191 1192 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 1193 "feasible solution found by %s heuristic after %.1f seconds, objective value %.6e\n", 1194 SCIPheurGetName(SCIPsolGetHeur(sol)), SCIPgetSolvingTime(scip), SCIPgetSolOrigObj(scip, sol)); 1195 } 1196 } 1197 1198 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "presolving:\n"); 1199 1200 *infeasible = FALSE; 1201 *unbounded = (*unbounded) || (SCIPgetNSols(scip) > 0 && SCIPisInfinity(scip, -SCIPgetSolOrigObj(scip, SCIPgetBestSol(scip)))); 1202 *vanished = scip->transprob->nvars == 0 && scip->transprob->nconss == 0 && scip->set->nactivepricers == 0; 1203 1204 finished = (scip->set->presol_maxrounds != -1 && scip->stat->npresolrounds >= scip->set->presol_maxrounds) 1205 || (*unbounded) || (*vanished) || (scip->set->reopt_enable && scip->stat->nreoptruns >= 1); 1206 stopped = SCIPsolveIsStopped(scip->set, scip->stat, TRUE); 1207 1208 /* perform presolving rounds */ 1209 while( !finished && !stopped ) 1210 { 1211 /* store current number of reductions */ 1212 scip->stat->lastnpresolfixedvars = scip->stat->npresolfixedvars; 1213 scip->stat->lastnpresolaggrvars = scip->stat->npresolaggrvars; 1214 scip->stat->lastnpresolchgvartypes = scip->stat->npresolchgvartypes; 1215 scip->stat->lastnpresolchgbds = scip->stat->npresolchgbds; 1216 scip->stat->lastnpresoladdholes = scip->stat->npresoladdholes; 1217 scip->stat->lastnpresoldelconss = scip->stat->npresoldelconss; 1218 scip->stat->lastnpresoladdconss = scip->stat->npresoladdconss; 1219 scip->stat->lastnpresolupgdconss = scip->stat->npresolupgdconss; 1220 scip->stat->lastnpresolchgcoefs = scip->stat->npresolchgcoefs; 1221 scip->stat->lastnpresolchgsides = scip->stat->npresolchgsides; 1222 #ifdef SCIP_DISABLED_CODE 1223 scip->stat->lastnpresolimplications = scip->stat->nimplications; 1224 scip->stat->lastnpresolcliques = SCIPcliquetableGetNCliques(scip->cliquetable); 1225 #endif 1226 1227 /* set presolving flag */ 1228 scip->stat->performpresol = TRUE; 1229 1230 /* sort propagators */ 1231 SCIPsetSortPropsPresol(scip->set); 1232 1233 /* sort presolvers by priority */ 1234 SCIPsetSortPresols(scip->set); 1235 1236 /* check if this will be the last presolving round (in that case, we want to run all presolvers) */ 1237 lastround = (scip->set->presol_maxrounds == -1 ? FALSE : (scip->stat->npresolrounds + 1 >= scip->set->presol_maxrounds)); 1238 1239 presoltiming = SCIP_PRESOLTIMING_FAST; 1240 1241 /* perform the presolving round by calling the presolvers, propagators, and constraint handlers */ 1242 assert(!(*unbounded)); 1243 assert(!(*infeasible)); 1244 SCIP_CALL( presolveRound(scip, &presoltiming, unbounded, infeasible, lastround, 1245 &presolstart, scip->set->npresols, &propstart, scip->set->nprops, &consstart, scip->set->nconshdlrs) ); 1246 1247 /* check, if we should abort presolving due to not enough changes in the last round */ 1248 finished = SCIPisPresolveFinished(scip) || presoltiming == SCIP_PRESOLTIMING_FINAL; 1249 1250 SCIPdebugMsg(scip, "presolving round %d returned with unbounded = %u, infeasible = %u, finished = %u\n", scip->stat->npresolrounds, *unbounded, *infeasible, finished); 1251 1252 /* check whether problem is infeasible or unbounded or vanished */ 1253 *vanished = scip->transprob->nvars == 0 && scip->transprob->nconss == 0 && scip->set->nactivepricers == 0; 1254 finished = finished || *unbounded || *infeasible || *vanished; 1255 1256 /* increase round number */ 1257 scip->stat->npresolrounds++; 1258 1259 if( !finished ) 1260 { 1261 /* print presolving statistics */ 1262 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 1263 "(round %d, %-11s %d del vars, %d del conss, %d add conss, %d chg bounds, %d chg sides, %d chg coeffs, %d upgd conss, %d impls, %d clqs\n", 1264 scip->stat->npresolrounds, ( presoltiming == SCIP_PRESOLTIMING_FAST ? "fast)" : 1265 (presoltiming == SCIP_PRESOLTIMING_MEDIUM ? "medium)" : 1266 (presoltiming == SCIP_PRESOLTIMING_EXHAUSTIVE ?"exhaustive)" : 1267 "final)")) ), 1268 scip->stat->npresolfixedvars + scip->stat->npresolaggrvars, 1269 scip->stat->npresoldelconss, scip->stat->npresoladdconss, 1270 scip->stat->npresolchgbds, scip->stat->npresolchgsides, 1271 scip->stat->npresolchgcoefs, scip->stat->npresolupgdconss, 1272 scip->stat->nimplications, SCIPcliquetableGetNCliques(scip->cliquetable)); 1273 } 1274 1275 /* abort if time limit was reached or user interrupted */ 1276 stopped = SCIPsolveIsStopped(scip->set, scip->stat, TRUE); 1277 } 1278 1279 /* first change status of scip, so that all plugins in their exitpre callbacks can ask SCIP for the correct status */ 1280 if( *infeasible ) 1281 { 1282 /* switch status to OPTIMAL */ 1283 if( scip->primal->nlimsolsfound > 0 ) 1284 { 1285 scip->stat->status = SCIP_STATUS_OPTIMAL; 1286 } 1287 else /* switch status to INFEASIBLE */ 1288 scip->stat->status = SCIP_STATUS_INFEASIBLE; 1289 } 1290 else if( *unbounded ) 1291 { 1292 if( scip->primal->nsols >= 1 ) /* switch status to UNBOUNDED */ 1293 scip->stat->status = SCIP_STATUS_UNBOUNDED; 1294 else /* switch status to INFORUNBD */ 1295 scip->stat->status = SCIP_STATUS_INFORUNBD; 1296 } 1297 /* if no variables and constraints are present, we try to add the empty solution (constraint handlers with needscons 1298 * flag FALSE could theoretically reject it); if no active pricers could create variables later, we conclude 1299 * optimality or infeasibility */ 1300 else if( scip->transprob->nvars == 0 && scip->transprob->nconss == 0 ) 1301 { 1302 SCIP_SOL* sol; 1303 SCIP_Bool stored; 1304 1305 SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) ); 1306 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) ); 1307 1308 if( scip->set->nactivepricers == 0 ) 1309 { 1310 assert(*vanished); 1311 1312 if( scip->primal->nlimsolsfound > 0 ) 1313 scip->stat->status = SCIP_STATUS_OPTIMAL; 1314 else 1315 scip->stat->status = SCIP_STATUS_INFEASIBLE; 1316 } 1317 } 1318 1319 /* deinitialize presolving */ 1320 if( finished && (!stopped || *unbounded || *infeasible || *vanished) ) 1321 { 1322 SCIP_Real maxnonzeros; 1323 SCIP_Longint nchecknonzeros; 1324 SCIP_Longint nactivenonzeros; 1325 SCIP_Bool approxchecknonzeros; 1326 SCIP_Bool approxactivenonzeros; 1327 SCIP_Bool infeas; 1328 1329 SCIP_CALL( exitPresolve(scip, *unbounded || *infeasible || *vanished, &infeas) ); 1330 *infeasible = *infeasible || infeas; 1331 1332 assert(scip->set->stage == SCIP_STAGE_PRESOLVED); 1333 1334 /* resort variables if we are not already done (unless variable permutation was explicitly activated) */ 1335 if( !scip->set->random_permutevars && !(*infeasible) && !(*unbounded) && !(*vanished) ) 1336 { 1337 /* (Re)Sort the variables, which appear in the four categories (binary, integer, implicit, continuous) after 1338 * presolve with respect to their original index (within their categories). Adjust the problem index afterwards 1339 * which is supposed to reflect the position in the variable array. This additional (re)sorting is supposed to 1340 * get more robust against the order presolving fixed variables. (We also reobtain a possible block structure 1341 * induced by the user model) 1342 */ 1343 SCIPprobResortVars(scip->transprob); 1344 } 1345 1346 /* determine number of non-zeros */ 1347 maxnonzeros = (SCIP_Real)SCIPgetNConss(scip) * SCIPgetNVars(scip); 1348 maxnonzeros = MAX(maxnonzeros, 1.0); 1349 SCIP_CALL( calcNonZeros(scip, &nchecknonzeros, &nactivenonzeros, &approxchecknonzeros, &approxactivenonzeros) ); 1350 scip->stat->nnz = nactivenonzeros; 1351 1352 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, "\n"); 1353 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, 1354 "presolved problem has %s%" SCIP_LONGINT_FORMAT " active (%g%%) nonzeros and %s%" SCIP_LONGINT_FORMAT " (%g%%) check nonzeros\n", 1355 approxactivenonzeros ? "more than " : "", nactivenonzeros, nactivenonzeros/maxnonzeros * 100, 1356 approxchecknonzeros ? "more than " : "", nchecknonzeros, nchecknonzeros/maxnonzeros * 100); 1357 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_FULL, "\n"); 1358 } 1359 assert(BMSgetNUsedBufferMemory(SCIPbuffer(scip)) == nusedbuffers); 1360 assert(BMSgetNUsedBufferMemory(SCIPcleanbuffer(scip)) == nusedcleanbuffers); 1361 1362 /* stop presolving time */ 1363 SCIPclockStop(scip->stat->presolvingtime, scip->set); 1364 SCIPclockStop(scip->stat->presolvingtimeoverall, scip->set); 1365 1366 /* print presolving statistics */ 1367 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, 1368 "presolving (%d rounds: %d fast, %d medium, %d exhaustive):\n", scip->stat->npresolrounds, 1369 scip->stat->npresolroundsfast, scip->stat->npresolroundsmed, scip->stat->npresolroundsext); 1370 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, 1371 " %d deleted vars, %d deleted constraints, %d added constraints, %d tightened bounds, %d added holes, %d changed sides, %d changed coefficients\n", 1372 scip->stat->npresolfixedvars + scip->stat->npresolaggrvars, scip->stat->npresoldelconss, scip->stat->npresoladdconss, 1373 scip->stat->npresolchgbds, scip->stat->npresoladdholes, scip->stat->npresolchgsides, scip->stat->npresolchgcoefs); 1374 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, 1375 " %d implications, %d cliques\n", scip->stat->nimplications, SCIPcliquetableGetNCliques(scip->cliquetable)); 1376 1377 /* remember number of constraints */ 1378 SCIPprobMarkNConss(scip->transprob); 1379 1380 return SCIP_OKAY; 1381 } 1382 1383 /** tries to transform original solutions to the transformed problem space */ 1384 static 1385 SCIP_RETCODE transformSols( 1386 SCIP* scip /**< SCIP data structure */ 1387 ) 1388 { 1389 SCIP_SOL** sols; 1390 SCIP_SOL** scipsols; 1391 SCIP_SOL* sol; 1392 SCIP_Real* solvals; 1393 SCIP_Bool* solvalset; 1394 SCIP_Bool added; 1395 SCIP_Longint oldnsolsfound; 1396 int nsols; 1397 int ntransvars; 1398 int naddedsols; 1399 int s; 1400 1401 nsols = SCIPgetNSols(scip); 1402 oldnsolsfound = scip->primal->nsolsfound; 1403 1404 /* no solution to transform */ 1405 if( nsols == 0 ) 1406 return SCIP_OKAY; 1407 1408 SCIPdebugMsg(scip, "try to transfer %d original solutions into the transformed problem space\n", nsols); 1409 1410 ntransvars = scip->transprob->nvars; 1411 naddedsols = 0; 1412 1413 /* It might happen, that the added transferred solution does not equal the corresponding original one, which might 1414 * result in the array of solutions being changed. Thus we temporarily copy the array and traverse it in reverse 1415 * order to ensure that the regarded solution in the copied array was not already freed when new solutions were added 1416 * and the worst solutions were freed. 1417 */ 1418 scipsols = SCIPgetSols(scip); 1419 SCIP_CALL( SCIPduplicateBufferArray(scip, &sols, scipsols, nsols) ); 1420 SCIP_CALL( SCIPallocBufferArray(scip, &solvals, ntransvars) ); 1421 SCIP_CALL( SCIPallocBufferArray(scip, &solvalset, ntransvars) ); 1422 1423 for( s = nsols-1; s >= 0; --s ) 1424 { 1425 sol = sols[s]; 1426 1427 /* it might happen that a transferred original solution has a better objective than its original counterpart 1428 * (e.g., because multi-aggregated variables get another value, but the solution is still feasible); 1429 * in this case, it might happen that the solution is not an original one and we just skip this solution 1430 */ 1431 if( !SCIPsolIsOriginal(sol) ) 1432 continue; 1433 1434 SCIP_CALL( SCIPprimalTransformSol(scip->primal, sol, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, 1435 scip->origprob, scip->transprob, scip->tree, scip->reopt, scip->lp, scip->eventqueue, scip->eventfilter, solvals, 1436 solvalset, ntransvars, &added) ); 1437 1438 if( added ) 1439 ++naddedsols; 1440 } 1441 1442 if( naddedsols > 0 ) 1443 { 1444 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 1445 "transformed %d/%d original solutions to the transformed problem space\n", 1446 naddedsols, nsols); 1447 1448 scip->stat->nexternalsolsfound += scip->primal->nsolsfound - oldnsolsfound; 1449 } 1450 1451 SCIPfreeBufferArray(scip, &solvalset); 1452 SCIPfreeBufferArray(scip, &solvals); 1453 SCIPfreeBufferArray(scip, &sols); 1454 1455 return SCIP_OKAY; 1456 } 1457 1458 /** initializes solution process data structures */ 1459 static 1460 SCIP_RETCODE initSolve( 1461 SCIP* scip, /**< SCIP data structure */ 1462 SCIP_Bool solved /**< is problem already solved? */ 1463 ) 1464 { 1465 assert(scip != NULL); 1466 assert(scip->mem != NULL); 1467 assert(scip->set != NULL); 1468 assert(scip->stat != NULL); 1469 assert(scip->nlp == NULL); 1470 assert(scip->set->stage == SCIP_STAGE_PRESOLVED); 1471 1472 /**@todo check whether other methodscan be skipped if problem has been solved */ 1473 /* if problem has been solved, several time consuming tasks must not be performed */ 1474 if( !solved ) 1475 { 1476 /* reset statistics for current branch and bound run */ 1477 SCIPstatResetCurrentRun(scip->stat, scip->set, scip->transprob, scip->origprob, solved); 1478 SCIPstatEnforceLPUpdates(scip->stat); 1479 1480 /* LP is empty anyway; mark empty LP to be solved and update validsollp counter */ 1481 SCIP_CALL( SCIPlpReset(scip->lp, scip->mem->probmem, scip->set, scip->transprob, scip->stat, scip->eventqueue, scip->eventfilter) ); 1482 1483 /* update upper bound and cutoff bound due to objective limit in primal data */ 1484 SCIP_CALL( SCIPprimalUpdateObjlimit(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, 1485 scip->eventqueue, scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp) ); 1486 } 1487 1488 /* switch stage to INITSOLVE */ 1489 scip->set->stage = SCIP_STAGE_INITSOLVE; 1490 1491 /* initialize NLP if there are nonlinearities */ 1492 if( scip->transprob->nlpenabled && !scip->set->nlp_disable ) 1493 { 1494 SCIPdebugMsg(scip, "constructing empty NLP\n"); 1495 1496 SCIP_CALL( SCIPnlpCreate(&scip->nlp, scip->mem->probmem, scip->set, scip->stat, SCIPprobGetName(scip->transprob), scip->transprob->nvars) ); 1497 assert(scip->nlp != NULL); 1498 1499 SCIP_CALL( SCIPnlpAddVars(scip->nlp, scip->mem->probmem, scip->set, scip->transprob->nvars, scip->transprob->vars) ); 1500 1501 /* Adjust estimation of external memory: SCIPtransformProb() estimated the memory used for the LP-solver. As a 1502 * very crude approximation just double this number. Only do this once in the first run. */ 1503 if( scip->set->misc_estimexternmem && scip->stat->nruns <= 1 ) 1504 { 1505 scip->stat->externmemestim *= 2; 1506 SCIPdebugMsg(scip, "external memory usage estimated to %" SCIP_LONGINT_FORMAT " byte\n", scip->stat->externmemestim); 1507 } 1508 } 1509 1510 /* possibly create visualization output file */ 1511 SCIP_CALL( SCIPvisualInit(scip->stat->visual, scip->mem->probmem, scip->set, scip->messagehdlr) ); 1512 1513 /* initialize solution process data structures */ 1514 SCIP_CALL( SCIPpricestoreCreate(&scip->pricestore) ); 1515 SCIP_CALL( SCIPsepastoreCreate(&scip->sepastore, scip->mem->probmem, scip->set) ); 1516 SCIP_CALL( SCIPsepastoreCreate(&scip->sepastoreprobing, scip->mem->probmem, scip->set) ); 1517 SCIP_CALL( SCIPcutpoolCreate(&scip->cutpool, scip->mem->probmem, scip->set, scip->set->sepa_cutagelimit, TRUE) ); 1518 SCIP_CALL( SCIPcutpoolCreate(&scip->delayedcutpool, scip->mem->probmem, scip->set, scip->set->sepa_cutagelimit, FALSE) ); 1519 SCIP_CALL( SCIPtreeCreateRoot(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, 1520 scip->lp) ); 1521 1522 /* update dual bound of the root node if a valid dual bound is at hand */ 1523 if( scip->transprob->dualbound < SCIP_INVALID ) 1524 { 1525 SCIP_Real internobjval = SCIPprobInternObjval(scip->transprob, scip->origprob, scip->set, scip->transprob->dualbound); 1526 1527 scip->stat->lastlowerbound = internobjval; 1528 1529 SCIPnodeUpdateLowerbound(SCIPtreeGetRootNode(scip->tree), scip->stat, scip->set, scip->tree, scip->transprob, 1530 scip->origprob, internobjval); 1531 } 1532 1533 /* try to transform original solutions to the transformed problem space */ 1534 if( scip->set->misc_transorigsols ) 1535 { 1536 SCIP_CALL( transformSols(scip) ); 1537 } 1538 1539 /* inform the transformed problem that the branch and bound process starts now */ 1540 SCIP_CALL( SCIPprobInitSolve(scip->transprob, scip->set) ); 1541 1542 /* transform the decomposition storage */ 1543 SCIP_CALL( SCIPtransformDecompstore(scip) ); 1544 1545 /* inform plugins that the branch and bound process starts now */ 1546 SCIP_CALL( SCIPsetInitsolPlugins(scip->set, scip->mem->probmem, scip->stat) ); 1547 1548 /* remember number of constraints */ 1549 SCIPprobMarkNConss(scip->transprob); 1550 1551 /* if all variables are known, calculate a trivial primal bound by setting all variables to their worst bound */ 1552 if( scip->set->nactivepricers == 0 ) 1553 { 1554 SCIP_VAR* var; 1555 SCIP_Real obj; 1556 SCIP_Real objbound; 1557 SCIP_Real bd; 1558 int v; 1559 1560 objbound = 0.0; 1561 for( v = 0; v < scip->transprob->nvars && !SCIPsetIsInfinity(scip->set, objbound); ++v ) 1562 { 1563 var = scip->transprob->vars[v]; 1564 obj = SCIPvarGetObj(var); 1565 if( !SCIPsetIsZero(scip->set, obj) ) 1566 { 1567 bd = SCIPvarGetWorstBoundGlobal(var); 1568 if( SCIPsetIsInfinity(scip->set, REALABS(bd)) ) 1569 objbound = SCIPsetInfinity(scip->set); 1570 else 1571 objbound += obj * bd; 1572 } 1573 } 1574 1575 /* adjust primal bound, such that solution with worst bound may be found */ 1576 if( objbound + SCIPsetCutoffbounddelta(scip->set) != objbound ) /*lint !e777*/ 1577 objbound += SCIPsetCutoffbounddelta(scip->set); 1578 /* if objbound is very large, adding the cutoffbounddelta may not change the number; in this case, we are using 1579 * SCIPnextafter to ensure that the cutoffbound is really larger than the best possible solution value 1580 */ 1581 else 1582 objbound = SCIPnextafter(objbound, SCIP_REAL_MAX); 1583 1584 /* update cutoff bound */ 1585 if( !SCIPsetIsInfinity(scip->set, objbound) && SCIPsetIsLT(scip->set, objbound, scip->primal->cutoffbound) ) 1586 { 1587 /* adjust cutoff bound */ 1588 SCIP_CALL( SCIPprimalSetCutoffbound(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, 1589 scip->eventqueue, scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, objbound, FALSE) ); 1590 } 1591 } 1592 1593 /* switch stage to SOLVING */ 1594 scip->set->stage = SCIP_STAGE_SOLVING; 1595 1596 return SCIP_OKAY; 1597 } 1598 1599 /** frees solution process data structures */ 1600 static 1601 SCIP_RETCODE freeSolve( 1602 SCIP* scip, /**< SCIP data structure */ 1603 SCIP_Bool restart /**< was this free solve call triggered by a restart? */ 1604 ) 1605 { 1606 assert(scip != NULL); 1607 assert(scip->mem != NULL); 1608 assert(scip->set != NULL); 1609 assert(scip->stat != NULL); 1610 assert(scip->set->stage == SCIP_STAGE_SOLVING || scip->set->stage == SCIP_STAGE_SOLVED); 1611 1612 /* mark that we are currently restarting */ 1613 if( restart ) 1614 { 1615 scip->stat->inrestart = TRUE; 1616 1617 /* copy the current dual bound into the problem data structure such that it can be used initialize the new search 1618 * tree 1619 */ 1620 SCIPprobUpdateDualbound(scip->transprob, SCIPgetDualbound(scip)); 1621 } 1622 1623 /* remove focus from the current focus node */ 1624 if( SCIPtreeGetFocusNode(scip->tree) != NULL ) 1625 { 1626 SCIP_NODE* node = NULL; 1627 SCIP_Bool cutoff; 1628 1629 SCIP_CALL( SCIPnodeFocus(&node, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->transprob, 1630 scip->origprob, scip->primal, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->conflict, 1631 scip->conflictstore, scip->eventfilter, scip->eventqueue, scip->cliquetable, &cutoff, FALSE, TRUE) ); 1632 assert(!cutoff); 1633 } 1634 1635 /* switch stage to EXITSOLVE */ 1636 scip->set->stage = SCIP_STAGE_EXITSOLVE; 1637 1638 /* cleanup the conflict storage */ 1639 SCIP_CALL( SCIPconflictstoreClean(scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->reopt) ); 1640 1641 /* inform plugins that the branch and bound process is finished */ 1642 SCIP_CALL( SCIPsetExitsolPlugins(scip->set, scip->mem->probmem, scip->stat, restart) ); 1643 1644 /* free the NLP, if there is one, and reset the flags indicating nonlinearity */ 1645 if( scip->nlp != NULL ) 1646 { 1647 SCIP_CALL( SCIPnlpFree(&scip->nlp, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->lp) ); 1648 } 1649 scip->transprob->nlpenabled = FALSE; 1650 1651 /* clear the LP, and flush the changes to clear the LP of the solver */ 1652 SCIP_CALL( SCIPlpReset(scip->lp, scip->mem->probmem, scip->set, scip->transprob, scip->stat, scip->eventqueue, scip->eventfilter) ); 1653 SCIPlpInvalidateRootObjval(scip->lp); 1654 1655 /* resets the debug environment */ 1656 SCIP_CALL( SCIPdebugReset(scip->set) ); /*lint !e506 !e774*/ 1657 1658 /* clear all row references in internal data structures */ 1659 SCIP_CALL( SCIPcutpoolClear(scip->cutpool, scip->mem->probmem, scip->set, scip->lp) ); 1660 SCIP_CALL( SCIPcutpoolClear(scip->delayedcutpool, scip->mem->probmem, scip->set, scip->lp) ); 1661 1662 /* we have to clear the tree prior to the problem deinitialization, because the rows stored in the forks and 1663 * subroots have to be released 1664 */ 1665 SCIP_CALL( SCIPtreeClear(scip->tree, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, scip->lp) ); 1666 1667 SCIPexitSolveDecompstore(scip); 1668 1669 /* deinitialize transformed problem */ 1670 SCIP_CALL( SCIPprobExitSolve(scip->transprob, scip->mem->probmem, scip->set, scip->eventqueue, scip->lp, restart) ); 1671 1672 /* free solution process data structures */ 1673 SCIP_CALL( SCIPcutpoolFree(&scip->cutpool, scip->mem->probmem, scip->set, scip->lp) ); 1674 SCIP_CALL( SCIPcutpoolFree(&scip->delayedcutpool, scip->mem->probmem, scip->set, scip->lp) ); 1675 SCIP_CALL( SCIPsepastoreFree(&scip->sepastoreprobing, scip->mem->probmem) ); 1676 SCIP_CALL( SCIPsepastoreFree(&scip->sepastore, scip->mem->probmem) ); 1677 SCIP_CALL( SCIPpricestoreFree(&scip->pricestore) ); 1678 1679 /* possibly close visualization output file */ 1680 SCIPvisualExit(scip->stat->visual, scip->set, scip->messagehdlr); 1681 1682 /* reset statistics for current branch and bound run */ 1683 if( scip->stat->status == SCIP_STATUS_INFEASIBLE || scip->stat->status == SCIP_STATUS_OPTIMAL || scip->stat->status == SCIP_STATUS_UNBOUNDED || scip->stat->status == SCIP_STATUS_INFORUNBD ) 1684 SCIPstatResetCurrentRun(scip->stat, scip->set, scip->transprob, scip->origprob, TRUE); 1685 else 1686 SCIPstatResetCurrentRun(scip->stat, scip->set, scip->transprob, scip->origprob, FALSE); 1687 1688 /* switch stage to TRANSFORMED */ 1689 scip->set->stage = SCIP_STAGE_TRANSFORMED; 1690 1691 /* restart finished */ 1692 assert( ! restart || scip->stat->inrestart ); 1693 scip->stat->inrestart = FALSE; 1694 1695 return SCIP_OKAY; 1696 } 1697 1698 /** frees solution process data structures when reoptimization is used 1699 * 1700 * in contrast to a freeSolve() this method will preserve the transformed problem such that another presolving round 1701 * after changing the problem (modifying the objective function) is not necessary. 1702 */ 1703 static 1704 SCIP_RETCODE freeReoptSolve( 1705 SCIP* scip /**< SCIP data structure */ 1706 ) 1707 { 1708 assert(scip != NULL); 1709 assert(scip->mem != NULL); 1710 assert(scip->set != NULL); 1711 assert(scip->stat != NULL); 1712 assert(scip->set->stage == SCIP_STAGE_SOLVING || scip->set->stage == SCIP_STAGE_SOLVED); 1713 1714 /* remove focus from the current focus node */ 1715 if( SCIPtreeGetFocusNode(scip->tree) != NULL ) 1716 { 1717 SCIP_NODE* node = NULL; 1718 SCIP_Bool cutoff; 1719 1720 SCIP_CALL( SCIPnodeFocus(&node, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->transprob, 1721 scip->origprob, scip->primal, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->conflict, 1722 scip->conflictstore, scip->eventfilter, scip->eventqueue, scip->cliquetable, &cutoff, FALSE, TRUE) ); 1723 assert(!cutoff); 1724 } 1725 1726 /* mark current stats, such that new solve begins with the var/col/row indices from the previous run */ 1727 SCIPstatMark(scip->stat); 1728 1729 /* switch stage to EXITSOLVE */ 1730 scip->set->stage = SCIP_STAGE_EXITSOLVE; 1731 1732 /* deinitialize conflict store */ 1733 SCIP_CALL( SCIPconflictstoreClear(scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->reopt) ); 1734 1735 /* invalidate the dual bound */ 1736 SCIPprobInvalidateDualbound(scip->transprob); 1737 1738 /* inform plugins that the branch and bound process is finished */ 1739 SCIP_CALL( SCIPsetExitsolPlugins(scip->set, scip->mem->probmem, scip->stat, FALSE) ); 1740 1741 /* call exit methods of plugins */ 1742 SCIP_CALL( SCIPsetExitPlugins(scip->set, scip->mem->probmem, scip->stat) ); 1743 1744 /* free the NLP, if there is one, and reset the flags indicating nonlinearity */ 1745 if( scip->nlp != NULL ) 1746 { 1747 SCIP_CALL( SCIPnlpFree(&scip->nlp, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->lp) ); 1748 } 1749 scip->transprob->nlpenabled = FALSE; 1750 1751 /* clear the LP, and flush the changes to clear the LP of the solver */ 1752 SCIP_CALL( SCIPlpReset(scip->lp, scip->mem->probmem, scip->set, scip->transprob, scip->stat, scip->eventqueue, scip->eventfilter) ); 1753 SCIPlpInvalidateRootObjval(scip->lp); 1754 1755 /* resets the debug environment */ 1756 SCIP_CALL( SCIPdebugReset(scip->set) ); /*lint !e506 !e774*/ 1757 1758 /* clear all row references in internal data structures */ 1759 SCIP_CALL( SCIPcutpoolClear(scip->cutpool, scip->mem->probmem, scip->set, scip->lp) ); 1760 SCIP_CALL( SCIPcutpoolClear(scip->delayedcutpool, scip->mem->probmem, scip->set, scip->lp) ); 1761 1762 /* we have to clear the tree prior to the problem deinitialization, because the rows stored in the forks and 1763 * subroots have to be released 1764 */ 1765 SCIP_CALL( SCIPtreeClear(scip->tree, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, scip->lp) ); 1766 1767 /* deinitialize transformed problem */ 1768 SCIP_CALL( SCIPprobExitSolve(scip->transprob, scip->mem->probmem, scip->set, scip->eventqueue, scip->lp, FALSE) ); 1769 1770 /* free solution process data structures */ 1771 SCIP_CALL( SCIPrelaxationFree(&scip->relaxation) ); 1772 1773 SCIP_CALL( SCIPcutpoolFree(&scip->cutpool, scip->mem->probmem, scip->set, scip->lp) ); 1774 SCIP_CALL( SCIPcutpoolFree(&scip->delayedcutpool, scip->mem->probmem, scip->set, scip->lp) ); 1775 SCIP_CALL( SCIPsepastoreFree(&scip->sepastoreprobing, scip->mem->probmem) ); 1776 SCIP_CALL( SCIPsepastoreFree(&scip->sepastore, scip->mem->probmem) ); 1777 SCIP_CALL( SCIPpricestoreFree(&scip->pricestore) ); 1778 1779 /* possibly close visualization output file */ 1780 SCIPvisualExit(scip->stat->visual, scip->set, scip->messagehdlr); 1781 1782 /* reset statistics for current branch and bound run */ 1783 SCIPstatResetCurrentRun(scip->stat, scip->set, scip->transprob, scip->origprob, FALSE); 1784 1785 /* switch stage to PRESOLVED */ 1786 scip->set->stage = SCIP_STAGE_PRESOLVED; 1787 1788 /* restart finished */ 1789 scip->stat->inrestart = FALSE; 1790 1791 /* reset solving specific paramters */ 1792 if( scip->set->reopt_enable ) 1793 { 1794 assert(scip->reopt != NULL); 1795 SCIP_CALL( SCIPreoptReset(scip->reopt, scip->set, scip->mem->probmem) ); 1796 } 1797 1798 /* free the debug solution which might live in transformed primal data structure */ 1799 SCIP_CALL( SCIPprimalClear(&scip->primal, scip->mem->probmem) ); 1800 1801 if( scip->set->misc_resetstat ) 1802 { 1803 /* reset statistics to the point before the problem was transformed */ 1804 SCIPstatReset(scip->stat, scip->set, scip->transprob, scip->origprob); 1805 } 1806 else 1807 { 1808 /* even if statistics are not completely reset, a partial reset of the primal-dual integral is necessary */ 1809 SCIPstatResetPrimalDualIntegrals(scip->stat, scip->set, TRUE); 1810 } 1811 1812 /* reset objective limit */ 1813 SCIP_CALL( SCIPsetObjlimit(scip, SCIP_INVALID) ); 1814 1815 return SCIP_OKAY; 1816 } 1817 1818 /** free transformed problem */ 1819 static 1820 SCIP_RETCODE freeTransform( 1821 SCIP* scip /**< SCIP data structure */ 1822 ) 1823 { 1824 SCIP_Bool reducedfree; 1825 1826 assert(scip != NULL); 1827 assert(scip->mem != NULL); 1828 assert(scip->stat != NULL); 1829 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED || scip->set->stage == SCIP_STAGE_PRESOLVING || 1830 (scip->set->stage == SCIP_STAGE_PRESOLVED && scip->set->reopt_enable)); 1831 1832 /* If the following evaluates to true, SCIPfreeReoptSolve() has already called the exit-callbacks of the plugins. 1833 * We can skip calling some of the following methods. This can happen if a new objective function was 1834 * installed but the solve was not started. 1835 */ 1836 reducedfree = (scip->set->stage == SCIP_STAGE_PRESOLVED && scip->set->reopt_enable); 1837 1838 if( !reducedfree ) 1839 { 1840 /* call exit methods of plugins */ 1841 SCIP_CALL( SCIPsetExitPlugins(scip->set, scip->mem->probmem, scip->stat) ); 1842 } 1843 1844 /* copy best primal solutions to original solution candidate list but not for a benders decomposition 1845 * because their cost information would be incomplete 1846 */ 1847 if( !scip->set->reopt_enable && scip->set->limit_maxorigsol > 0 && scip->set->misc_transsolsorig && scip->set->nactivebenders == 0 ) 1848 { 1849 SCIP_Bool stored; 1850 SCIP_Bool hasinfval; 1851 int maxsols; 1852 int nsols; 1853 int s; 1854 1855 assert(scip->origprimal->nsols == 0); 1856 1857 nsols = scip->primal->nsols; 1858 maxsols = scip->set->limit_maxorigsol; 1859 stored = TRUE; 1860 s = 0; 1861 1862 /* iterate over all solutions as long as the original solution candidate store size limit is not reached */ 1863 while( s < nsols && scip->origprimal->nsols < maxsols ) 1864 { 1865 SCIP_SOL* sol; 1866 1867 sol = scip->primal->sols[s]; 1868 assert(sol != NULL); 1869 1870 if( !SCIPsolIsOriginal(sol) ) 1871 { 1872 /* retransform solution into the original problem space */ 1873 SCIP_CALL( SCIPsolRetransform(sol, scip->set, scip->stat, scip->origprob, scip->transprob, &hasinfval) ); 1874 } 1875 else 1876 hasinfval = FALSE; 1877 1878 /* removing infinite fixings is turned off by the corresponding parameter */ 1879 if( !scip->set->misc_finitesolstore ) 1880 hasinfval = FALSE; 1881 1882 if( !hasinfval ) 1883 { 1884 /* add solution to original candidate solution storage */ 1885 SCIP_CALL( SCIPprimalAddOrigSol(scip->origprimal, scip->mem->probmem, scip->set, scip->stat, scip->origprob, sol, &stored) ); 1886 } 1887 else 1888 { 1889 SCIP_SOL* newsol; 1890 SCIP_Bool success; 1891 1892 SCIP_CALL( SCIPcreateFiniteSolCopy(scip, &newsol, sol, &success) ); 1893 1894 /* infinite fixing could be removed */ 1895 if( newsol != NULL ) 1896 { 1897 /* add solution to original candidate solution storage; we must not use SCIPprimalAddOrigSolFree() 1898 * because we want to create a copy of the solution in the origprimal solution store, but newsol was 1899 * created in the (transformed) primal 1900 */ 1901 SCIP_CALL( SCIPprimalAddOrigSol(scip->origprimal, scip->mem->probmem, scip->set, scip->stat, scip->origprob, newsol, &stored) ); 1902 1903 /* free solution in (transformed) primal where it was created */ 1904 SCIP_CALL( SCIPsolFree(&newsol, scip->mem->probmem, scip->primal) ); 1905 } 1906 } 1907 ++s; 1908 } 1909 1910 if( scip->origprimal->nsols > 1 ) 1911 { 1912 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, 1913 "stored the %d best primal solutions in the original solution candidate list\n", scip->origprimal->nsols); 1914 } 1915 else if( scip->origprimal->nsols == 1 ) 1916 { 1917 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, 1918 "stored the best primal solution in the original solution candidate list\n"); 1919 } 1920 } 1921 1922 /* switch stage to FREETRANS */ 1923 scip->set->stage = SCIP_STAGE_FREETRANS; 1924 1925 /* reset solving specific paramters */ 1926 assert(!scip->set->reopt_enable || scip->reopt != NULL); 1927 if( scip->set->reopt_enable && scip->reopt != NULL ) 1928 { 1929 SCIP_CALL( SCIPreoptReset(scip->reopt, scip->set, scip->mem->probmem) ); 1930 } 1931 1932 if( !reducedfree ) 1933 { 1934 /* clear the conflict store 1935 * 1936 * since the conflict store can contain transformed constraints we need to remove them. the store will be finally 1937 * freed in SCIPfreeProb(). 1938 */ 1939 SCIP_CALL( SCIPconflictstoreClear(scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->reopt) ); 1940 } 1941 1942 /* free transformed problem data structures */ 1943 SCIP_CALL( SCIPprobFree(&scip->transprob, scip->messagehdlr, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->lp) ); 1944 SCIP_CALL( SCIPcliquetableFree(&scip->cliquetable, scip->mem->probmem) ); 1945 SCIP_CALL( SCIPconflictFree(&scip->conflict, scip->mem->probmem) ); 1946 1947 if( !reducedfree ) 1948 { 1949 SCIP_CALL( SCIPrelaxationFree(&scip->relaxation) ); 1950 } 1951 SCIP_CALL( SCIPtreeFree(&scip->tree, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, scip->lp) ); 1952 1953 /* free the debug solution which might live in transformed primal data structure */ 1954 SCIP_CALL( SCIPdebugFreeSol(scip->set) ); /*lint !e506 !e774*/ 1955 SCIP_CALL( SCIPprimalFree(&scip->primal, scip->mem->probmem) ); 1956 1957 SCIP_CALL( SCIPlpFree(&scip->lp, scip->mem->probmem, scip->set, scip->eventqueue, scip->eventfilter) ); 1958 SCIP_CALL( SCIPbranchcandFree(&scip->branchcand) ); 1959 SCIP_CALL( SCIPeventfilterFree(&scip->eventfilter, scip->mem->probmem, scip->set) ); 1960 SCIP_CALL( SCIPeventqueueFree(&scip->eventqueue) ); 1961 1962 if( scip->set->misc_resetstat && !reducedfree ) 1963 { 1964 /* reset statistics to the point before the problem was transformed */ 1965 SCIPstatReset(scip->stat, scip->set, scip->transprob, scip->origprob); 1966 } 1967 else 1968 { 1969 /* even if statistics are not completely reset, a partial reset of the primal-dual integral is necessary */ 1970 SCIPstatResetPrimalDualIntegrals(scip->stat, scip->set, TRUE); 1971 } 1972 1973 /* switch stage to PROBLEM */ 1974 scip->set->stage = SCIP_STAGE_PROBLEM; 1975 1976 /* reset objective limit */ 1977 SCIP_CALL( SCIPsetObjlimit(scip, SCIP_INVALID) ); 1978 1979 /* reset original variable's local and global bounds to their original values */ 1980 SCIP_CALL( SCIPprobResetBounds(scip->origprob, scip->mem->probmem, scip->set, scip->stat) ); 1981 1982 return SCIP_OKAY; 1983 } 1984 1985 /** free transformed problem in case an error occurs during transformation and return to SCIP_STAGE_PROBLEM */ 1986 static 1987 SCIP_RETCODE freeTransforming( 1988 SCIP* scip /**< SCIP data structure */ 1989 ) 1990 { 1991 assert(scip != NULL); 1992 assert(scip->mem != NULL); 1993 assert(scip->stat != NULL); 1994 assert(scip->set->stage == SCIP_STAGE_TRANSFORMING); 1995 1996 /* switch stage to FREETRANS */ 1997 scip->set->stage = SCIP_STAGE_FREETRANS; 1998 1999 /* free transformed problem data structures */ 2000 SCIP_CALL( SCIPprobFree(&scip->transprob, scip->messagehdlr, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->lp) ); 2001 SCIP_CALL( SCIPcliquetableFree(&scip->cliquetable, scip->mem->probmem) ); 2002 SCIP_CALL( SCIPconflictFree(&scip->conflict, scip->mem->probmem) ); 2003 SCIP_CALL( SCIPrelaxationFree(&scip->relaxation) ); 2004 SCIP_CALL( SCIPtreeFree(&scip->tree, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, scip->lp) ); 2005 2006 /* free the debug solution which might live in transformed primal data structure */ 2007 SCIP_CALL( SCIPdebugFreeSol(scip->set) ); /*lint !e506 !e774*/ 2008 SCIP_CALL( SCIPprimalFree(&scip->primal, scip->mem->probmem) ); 2009 2010 SCIP_CALL( SCIPlpFree(&scip->lp, scip->mem->probmem, scip->set, scip->eventqueue, scip->eventfilter) ); 2011 SCIP_CALL( SCIPbranchcandFree(&scip->branchcand) ); 2012 SCIP_CALL( SCIPeventfilterFree(&scip->eventfilter, scip->mem->probmem, scip->set) ); 2013 SCIP_CALL( SCIPeventqueueFree(&scip->eventqueue) ); 2014 2015 if( scip->set->misc_resetstat ) 2016 { 2017 /* reset statistics to the point before the problem was transformed */ 2018 SCIPstatReset(scip->stat, scip->set, scip->transprob, scip->origprob); 2019 } 2020 else 2021 { 2022 /* even if statistics are not completely reset, a partial reset of the primal-dual integral is necessary */ 2023 SCIPstatResetPrimalDualIntegrals(scip->stat, scip->set, TRUE); 2024 } 2025 2026 /* switch stage to PROBLEM */ 2027 scip->set->stage = SCIP_STAGE_PROBLEM; 2028 2029 return SCIP_OKAY; 2030 } 2031 2032 /** displays most relevant statistics after problem was solved */ 2033 static 2034 SCIP_RETCODE displayRelevantStats( 2035 SCIP* scip /**< SCIP data structure */ 2036 ) 2037 { 2038 assert(scip != NULL); 2039 2040 /* display most relevant statistics */ 2041 if( scip->set->disp_verblevel >= SCIP_VERBLEVEL_NORMAL && scip->set->disp_relevantstats ) 2042 { 2043 SCIP_Bool objlimitreached = FALSE; 2044 2045 /* We output that the objective limit has been reached if the problem has been solved, no solution respecting the 2046 * objective limit has been found (nlimsolsfound == 0) and the primal bound is finite. Note that it still might be 2047 * that the original problem is infeasible, even without the objective limit, i.e., we cannot be sure that we 2048 * actually reached the objective limit. */ 2049 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVED && scip->primal->nlimsolsfound == 0 && ! SCIPisInfinity(scip, SCIPgetPrimalbound(scip)) ) 2050 objlimitreached = TRUE; 2051 2052 SCIPmessagePrintInfo(scip->messagehdlr, "\n"); 2053 SCIPmessagePrintInfo(scip->messagehdlr, "SCIP Status : "); 2054 SCIP_CALL( SCIPprintStage(scip, NULL) ); 2055 SCIPmessagePrintInfo(scip->messagehdlr, "\n"); 2056 if( scip->set->reopt_enable ) 2057 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Time (sec) : %.2f (over %d runs: %.2f)\n", SCIPclockGetTime(scip->stat->solvingtime), scip->stat->nreoptruns, SCIPclockGetTime(scip->stat->solvingtimeoverall)); 2058 else 2059 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Time (sec) : %.2f\n", SCIPclockGetTime(scip->stat->solvingtime)); 2060 if( scip->stat->nruns > 1 ) 2061 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Nodes : %" SCIP_LONGINT_FORMAT " (total of %" SCIP_LONGINT_FORMAT " nodes in %d runs)\n", 2062 scip->stat->nnodes, scip->stat->ntotalnodes, scip->stat->nruns); 2063 else if( scip->set->reopt_enable ) 2064 { 2065 SCIP_BRANCHRULE* branchrule; 2066 2067 branchrule = SCIPfindBranchrule(scip, "nodereopt"); 2068 assert(branchrule != NULL); 2069 2070 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Nodes : %" SCIP_LONGINT_FORMAT " (%" SCIP_LONGINT_FORMAT " reactivated)\n", scip->stat->nnodes, SCIPbranchruleGetNChildren(branchrule)); 2071 } 2072 else 2073 SCIPmessagePrintInfo(scip->messagehdlr, "Solving Nodes : %" SCIP_LONGINT_FORMAT "\n", scip->stat->nnodes); 2074 if( scip->set->stage >= SCIP_STAGE_TRANSFORMED && scip->set->stage <= SCIP_STAGE_EXITSOLVE ) 2075 { 2076 if( objlimitreached ) 2077 { 2078 SCIPmessagePrintInfo(scip->messagehdlr, "Primal Bound : %+.14e (objective limit, %" SCIP_LONGINT_FORMAT " solutions", 2079 SCIPgetPrimalbound(scip), scip->primal->nsolsfound); 2080 if( scip->primal->nsolsfound > 0 ) 2081 { 2082 SCIPmessagePrintInfo(scip->messagehdlr, ", best solution %+.14e", SCIPgetSolOrigObj(scip, SCIPgetBestSol(scip))); 2083 } 2084 SCIPmessagePrintInfo(scip->messagehdlr, ")\n"); 2085 } 2086 else 2087 { 2088 char limsolstring[SCIP_MAXSTRLEN]; 2089 if( scip->primal->nsolsfound != scip->primal->nlimsolsfound ) 2090 (void) SCIPsnprintf(limsolstring, SCIP_MAXSTRLEN, ", %" SCIP_LONGINT_FORMAT " respecting the objective limit", scip->primal->nlimsolsfound); 2091 else 2092 (void) SCIPsnprintf(limsolstring, SCIP_MAXSTRLEN,""); 2093 2094 SCIPmessagePrintInfo(scip->messagehdlr, "Primal Bound : %+.14e (%" SCIP_LONGINT_FORMAT " solutions%s)\n", 2095 SCIPgetPrimalbound(scip), scip->primal->nsolsfound, limsolstring); 2096 } 2097 } 2098 if( scip->set->stage >= SCIP_STAGE_SOLVING && scip->set->stage <= SCIP_STAGE_SOLVED ) 2099 { 2100 SCIPmessagePrintInfo(scip->messagehdlr, "Dual Bound : %+.14e\n", SCIPgetDualbound(scip)); 2101 2102 SCIPmessagePrintInfo(scip->messagehdlr, "Gap : "); 2103 if( SCIPsetIsInfinity(scip->set, SCIPgetGap(scip)) ) 2104 SCIPmessagePrintInfo(scip->messagehdlr, "infinite\n"); 2105 else 2106 SCIPmessagePrintInfo(scip->messagehdlr, "%.2f %%\n", 100.0*SCIPgetGap(scip)); 2107 } 2108 2109 /* check solution for feasibility in original problem */ 2110 if( scip->set->stage >= SCIP_STAGE_TRANSFORMED ) 2111 { 2112 SCIP_SOL* sol; 2113 2114 sol = SCIPgetBestSol(scip); 2115 if( sol != NULL ) 2116 { 2117 SCIP_Real checkfeastolfac; 2118 SCIP_Real oldfeastol; 2119 SCIP_Bool dispallviols; 2120 SCIP_Bool feasible; 2121 2122 oldfeastol = SCIPfeastol(scip); 2123 SCIP_CALL( SCIPgetRealParam(scip, "numerics/checkfeastolfac", &checkfeastolfac) ); 2124 SCIP_CALL( SCIPgetBoolParam(scip, "display/allviols", &dispallviols) ); 2125 2126 /* scale feasibility tolerance by set->num_checkfeastolfac */ 2127 if( !SCIPisEQ(scip, checkfeastolfac, 1.0) ) 2128 { 2129 SCIP_CALL( SCIPchgFeastol(scip, oldfeastol * checkfeastolfac) ); 2130 } 2131 2132 SCIP_CALL( SCIPcheckSolOrig(scip, sol, &feasible, TRUE, dispallviols) ); 2133 2134 /* restore old feasibilty tolerance */ 2135 if( !SCIPisEQ(scip, checkfeastolfac, 1.0) ) 2136 { 2137 SCIP_CALL( SCIPchgFeastol(scip, oldfeastol) ); 2138 } 2139 2140 if( !feasible ) 2141 { 2142 SCIPmessagePrintInfo(scip->messagehdlr, "best solution is not feasible in original problem\n"); 2143 } 2144 } 2145 } 2146 } 2147 2148 return SCIP_OKAY; 2149 } 2150 2151 /** calls compression based on the reoptimization structure after the presolving */ 2152 static 2153 SCIP_RETCODE compressReoptTree( 2154 SCIP* scip /**< global SCIP settings */ 2155 ) 2156 { 2157 SCIP_RESULT result; 2158 int c; 2159 int noldnodes; 2160 int nnewnodes; 2161 2162 result = SCIP_DIDNOTFIND; 2163 2164 noldnodes = SCIPreoptGetNNodes(scip->reopt, scip->tree->root); 2165 2166 /* do not run if there exists only the root node */ 2167 if( noldnodes <= 1 ) 2168 return SCIP_OKAY; 2169 2170 /* do not run a tree compression if the problem contains (implicit) integer variables */ 2171 if( scip->transprob->nintvars > 0 || scip->transprob->nimplvars > 0 ) 2172 return SCIP_OKAY; 2173 2174 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 2175 "tree compression:\n"); 2176 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 2177 " given tree has %d nodes.\n", noldnodes); 2178 2179 /* sort compressions by priority */ 2180 SCIPsetSortComprs(scip->set); 2181 2182 for(c = 0; c < scip->set->ncomprs; c++) 2183 { 2184 assert(result == SCIP_DIDNOTFIND || result == SCIP_DIDNOTRUN); 2185 2186 /* call tree compression technique */ 2187 SCIP_CALL( SCIPcomprExec(scip->set->comprs[c], scip->set, scip->reopt, &result) ); 2188 2189 if( result == SCIP_SUCCESS ) 2190 { 2191 nnewnodes = SCIPreoptGetNNodes(scip->reopt, scip->tree->root); 2192 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 2193 " <%s> compressed the search tree to %d nodes (rate %g).\n", SCIPcomprGetName(scip->set->comprs[c]), 2194 nnewnodes, ((SCIP_Real)nnewnodes)/noldnodes); 2195 2196 break; 2197 } 2198 } 2199 2200 if( result != SCIP_SUCCESS ) 2201 { 2202 assert(result == SCIP_DIDNOTFIND || result == SCIP_DIDNOTRUN); 2203 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 2204 " search tree could not be compressed.\n"); 2205 } 2206 2207 return SCIP_OKAY; 2208 } 2209 2210 /* prepare all plugins and data structures for a reoptimization run */ 2211 static 2212 SCIP_RETCODE prepareReoptimization( 2213 SCIP* scip /**< SCIP data structure */ 2214 ) 2215 { 2216 SCIP_Bool reoptrestart; 2217 2218 assert(scip != NULL); 2219 assert(scip->set->reopt_enable); 2220 2221 /* @ todo: we could check if the problem is feasible, eg, by backtracking */ 2222 2223 /* increase number of reopt_runs */ 2224 ++scip->stat->nreoptruns; 2225 2226 /* inform the reoptimization plugin that a new iteration starts */ 2227 SCIP_CALL( SCIPreoptAddRun(scip->reopt, scip->set, scip->mem->probmem, scip->origprob->vars, 2228 scip->origprob->nvars, scip->set->limit_maxsol) ); 2229 2230 /* check whether we need to add globally valid constraints */ 2231 if( scip->set->reopt_sepaglbinfsubtrees || scip->set->reopt_sepabestsol ) 2232 { 2233 SCIP_CALL( SCIPreoptApplyGlbConss(scip, scip->reopt, scip->set, scip->stat, scip->mem->probmem) ); 2234 } 2235 2236 /* after presolving the problem the first time we remember all global bounds and active constraints. bounds and 2237 * constraints will be restored within SCIPreoptInstallBounds() and SCIPreoptResetActiveConss(). 2238 */ 2239 if( scip->stat->nreoptruns == 1 ) 2240 { 2241 assert(scip->set->stage == SCIP_STAGE_PRESOLVED || scip->set->stage == SCIP_STAGE_SOLVED); 2242 2243 SCIP_CALL( SCIPreoptSaveGlobalBounds(scip->reopt, scip->transprob, scip->mem->probmem) ); 2244 2245 SCIP_CALL( SCIPreoptSaveActiveConss(scip->reopt, scip->set, scip->transprob, scip->mem->probmem) ); 2246 } 2247 /* we are at least in the second run */ 2248 else 2249 { 2250 assert(scip->transprob != NULL); 2251 2252 SCIP_CALL( SCIPreoptMergeVarHistory(scip->reopt, scip->set, scip->stat, scip->origprob->vars, scip->origprob->nvars) ); 2253 2254 SCIP_CALL( SCIPrelaxationCreate(&scip->relaxation, scip->mem->probmem, scip->set, scip->stat, scip->primal, 2255 scip->tree) ); 2256 2257 /* mark statistics before solving */ 2258 SCIPstatMark(scip->stat); 2259 2260 SCIPbranchcandInvalidate(scip->branchcand); 2261 2262 SCIP_CALL( SCIPreoptResetActiveConss(scip->reopt, scip->set, scip->stat) ); 2263 2264 /* check whether we want to restart the tree search */ 2265 SCIP_CALL( SCIPreoptCheckRestart(scip->reopt, scip->set, scip->mem->probmem, NULL, scip->transprob->vars, 2266 scip->transprob->nvars, &reoptrestart) ); 2267 2268 /* call initialization methods of plugins */ 2269 SCIP_CALL( SCIPsetInitPlugins(scip->set, scip->mem->probmem, scip->stat) ); 2270 2271 /* install globally valid lower and upper bounds */ 2272 SCIP_CALL( SCIPreoptInstallBounds(scip->reopt, scip->set, scip->stat, scip->transprob, scip->lp, scip->branchcand, 2273 scip->eventqueue, scip->cliquetable, scip->mem->probmem) ); 2274 2275 /* check, whether objective value is always integral by inspecting the problem, if it is the case adjust the 2276 * cutoff bound if primal solution is already known 2277 */ 2278 SCIP_CALL( SCIPprobCheckObjIntegral(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, 2279 scip->primal, scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) ); 2280 2281 /* if possible, scale objective function such that it becomes integral with gcd 1 */ 2282 SCIP_CALL( SCIPprobScaleObj(scip->transprob, scip->origprob, scip->mem->probmem, scip->set, scip->stat, scip->primal, 2283 scip->tree, scip->reopt, scip->lp, scip->eventfilter, scip->eventqueue) ); 2284 2285 SCIPlpRecomputeLocalAndGlobalPseudoObjval(scip->lp, scip->set, scip->transprob); 2286 } 2287 2288 /* try to compress the search tree */ 2289 if( scip->set->compr_enable ) 2290 { 2291 SCIP_CALL( compressReoptTree(scip) ); 2292 } 2293 2294 return SCIP_OKAY; 2295 } 2296 2297 /** transforms and presolves problem 2298 * 2299 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 2300 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 2301 * 2302 * @pre This method can be called if @p scip is in one of the following stages: 2303 * - \ref SCIP_STAGE_PROBLEM 2304 * - \ref SCIP_STAGE_TRANSFORMED 2305 * - \ref SCIP_STAGE_PRESOLVING 2306 * - \ref SCIP_STAGE_PRESOLVED 2307 * - \ref SCIP_STAGE_SOLVED 2308 * 2309 * @post After calling this method \SCIP reaches one of the following stages: 2310 * - \ref SCIP_STAGE_PRESOLVING if the presolving process was interrupted 2311 * - \ref SCIP_STAGE_PRESOLVED if the presolving process was finished and did not solve the problem 2312 * - \ref SCIP_STAGE_SOLVED if the problem was solved during presolving 2313 * 2314 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 2315 */ 2316 SCIP_RETCODE SCIPpresolve( 2317 SCIP* scip /**< SCIP data structure */ 2318 ) 2319 { 2320 SCIP_Bool unbounded; 2321 SCIP_Bool infeasible; 2322 SCIP_Bool vanished; 2323 SCIP_RETCODE retcode; 2324 2325 SCIP_CALL( SCIPcheckStage(scip, "SCIPpresolve", FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE) ); 2326 2327 /* start solving timer */ 2328 SCIPclockStart(scip->stat->solvingtime, scip->set); 2329 SCIPclockStart(scip->stat->solvingtimeoverall, scip->set); 2330 2331 /* capture the CTRL-C interrupt */ 2332 if( scip->set->misc_catchctrlc ) 2333 SCIPinterruptCapture(scip->interrupt); 2334 2335 /* reset the user interrupt flag */ 2336 scip->stat->userinterrupt = FALSE; 2337 SCIP_CALL( SCIPinterruptLP(scip, FALSE) ); 2338 2339 switch( scip->set->stage ) 2340 { 2341 case SCIP_STAGE_PROBLEM: 2342 /* initialize solving data structures and transform problem */ 2343 retcode = SCIPtransformProb(scip); 2344 if( retcode != SCIP_OKAY ) 2345 { 2346 SCIP_CALL( SCIPfreeTransform(scip) ); 2347 return retcode; 2348 } 2349 2350 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED); 2351 2352 /*lint -fallthrough*/ 2353 2354 case SCIP_STAGE_TRANSFORMED: 2355 case SCIP_STAGE_PRESOLVING: 2356 /* presolve problem */ 2357 SCIP_CALL( presolve(scip, &unbounded, &infeasible, &vanished) ); 2358 assert(scip->set->stage == SCIP_STAGE_PRESOLVED || scip->set->stage == SCIP_STAGE_PRESOLVING); 2359 2360 if( infeasible || unbounded || vanished ) 2361 { 2362 assert(scip->set->stage == SCIP_STAGE_PRESOLVED); 2363 2364 /* initialize solving process data structures to be able to switch to SOLVED stage */ 2365 SCIP_CALL( initSolve(scip, TRUE) ); 2366 2367 /* switch stage to SOLVED */ 2368 scip->set->stage = SCIP_STAGE_SOLVED; 2369 2370 /* print solution message */ 2371 switch( scip->stat->status )/*lint --e{788}*/ 2372 { 2373 case SCIP_STATUS_OPTIMAL: 2374 /* remove the root node from the tree, s.t. the lower bound is set to +infinity ???????????? (see initSolve())*/ 2375 SCIP_CALL( SCIPtreeClear(scip->tree, scip->mem->probmem, scip->set, scip->stat, scip->eventfilter, scip->eventqueue, scip->lp) ); 2376 break; 2377 2378 case SCIP_STATUS_INFEASIBLE: 2379 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, 2380 "presolving detected infeasibility\n"); 2381 break; 2382 2383 case SCIP_STATUS_UNBOUNDED: 2384 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, 2385 "presolving detected unboundedness\n"); 2386 break; 2387 2388 case SCIP_STATUS_INFORUNBD: 2389 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, 2390 "presolving detected unboundedness (or infeasibility)\n"); 2391 break; 2392 2393 default: 2394 /* note that this is in an internal SCIP error since the status is corrupted */ 2395 SCIPerrorMessage("invalid SCIP status <%d>\n", scip->stat->status); 2396 SCIPABORT(); 2397 return SCIP_ERROR; /*lint !e527*/ 2398 } 2399 } 2400 else if( scip->set->stage == SCIP_STAGE_PRESOLVED ) 2401 { 2402 int h; 2403 2404 /* print presolved problem statistics */ 2405 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, 2406 "presolved problem has %d variables (%d bin, %d int, %d impl, %d cont) and %d constraints\n", 2407 scip->transprob->nvars, scip->transprob->nbinvars, scip->transprob->nintvars, scip->transprob->nimplvars, 2408 scip->transprob->ncontvars, scip->transprob->nconss); 2409 2410 for( h = 0; h < scip->set->nconshdlrs; ++h ) 2411 { 2412 int nactiveconss; 2413 2414 nactiveconss = SCIPconshdlrGetNActiveConss(scip->set->conshdlrs[h]); 2415 if( nactiveconss > 0 ) 2416 { 2417 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 2418 "%7d constraints of type <%s>\n", nactiveconss, SCIPconshdlrGetName(scip->set->conshdlrs[h])); 2419 } 2420 } 2421 2422 if( SCIPprobIsObjIntegral(scip->transprob) ) 2423 { 2424 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 2425 "transformed objective value is always integral (scale: %.15g)\n", scip->transprob->objscale); 2426 } 2427 } 2428 else 2429 { 2430 assert(scip->set->stage == SCIP_STAGE_PRESOLVING); 2431 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "presolving was interrupted.\n"); 2432 } 2433 2434 /* display timing statistics */ 2435 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 2436 "Presolving Time: %.2f\n", SCIPclockGetTime(scip->stat->presolvingtime)); 2437 break; 2438 2439 case SCIP_STAGE_PRESOLVED: 2440 case SCIP_STAGE_SOLVED: 2441 break; 2442 2443 default: 2444 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage); 2445 return SCIP_INVALIDCALL; 2446 } /*lint !e788*/ 2447 2448 /* release the CTRL-C interrupt */ 2449 if( scip->set->misc_catchctrlc ) 2450 SCIPinterruptRelease(scip->interrupt); 2451 2452 /* stop solving timer */ 2453 SCIPclockStop(scip->stat->solvingtime, scip->set); 2454 SCIPclockStop(scip->stat->solvingtimeoverall, scip->set); 2455 2456 if( scip->set->stage == SCIP_STAGE_SOLVED ) 2457 { 2458 /* display most relevant statistics */ 2459 SCIP_CALL( displayRelevantStats(scip) ); 2460 } 2461 2462 return SCIP_OKAY; 2463 } 2464 2465 /** transforms, presolves, and solves problem 2466 * 2467 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 2468 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 2469 * 2470 * @pre This method can be called if @p scip is in one of the following stages: 2471 * - \ref SCIP_STAGE_PROBLEM 2472 * - \ref SCIP_STAGE_TRANSFORMED 2473 * - \ref SCIP_STAGE_PRESOLVING 2474 * - \ref SCIP_STAGE_PRESOLVED 2475 * - \ref SCIP_STAGE_SOLVING 2476 * - \ref SCIP_STAGE_SOLVED 2477 * 2478 * @post After calling this method \SCIP reaches one of the following stages depending on if and when the solution 2479 * process was interrupted: 2480 * - \ref SCIP_STAGE_PRESOLVING if the solution process was interrupted during presolving 2481 * - \ref SCIP_STAGE_SOLVING if the solution process was interrupted during the tree search 2482 * - \ref SCIP_STAGE_SOLVED if the solving process was not interrupted 2483 * 2484 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 2485 */ 2486 SCIP_RETCODE SCIPsolve( 2487 SCIP* scip /**< SCIP data structure */ 2488 ) 2489 { 2490 SCIP_Longint cutpoolncutsfoundbeforerestart = 0; 2491 SCIP_Longint cutpoolncutsaddedbeforerestart = 0; 2492 SCIP_Longint cutpoolncallsbeforerestart = 0; 2493 SCIP_Longint cutpoolnrootcallsbeforerestart = 0; 2494 SCIP_Longint cutpoolmaxncutsbeforerestart = 0; 2495 SCIP_Real cutpooltimebeforerestart = 0; 2496 SCIP_Bool statsprinted = FALSE; 2497 SCIP_Bool restart; 2498 SCIP_Bool transferstatistics = FALSE; 2499 2500 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolve", FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 2501 2502 /* if the stage is already SCIP_STAGE_SOLVED do nothing */ 2503 if( scip->set->stage == SCIP_STAGE_SOLVED ) 2504 return SCIP_OKAY; 2505 2506 if( scip->stat->status == SCIP_STATUS_INFEASIBLE || scip->stat->status == SCIP_STATUS_OPTIMAL || scip->stat->status == SCIP_STATUS_UNBOUNDED || scip->stat->status == SCIP_STATUS_INFORUNBD ) 2507 { 2508 SCIPwarningMessage(scip, "SCIPsolve() was called, but problem is already solved\n"); 2509 return SCIP_OKAY; 2510 } 2511 2512 /* check, if a node selector exists */ 2513 if( SCIPsetGetNodesel(scip->set, scip->stat) == NULL ) 2514 { 2515 SCIPerrorMessage("no node selector available\n"); 2516 return SCIP_PLUGINNOTFOUND; 2517 } 2518 2519 /* check, if an integrality constraint handler exists if there are integral variables */ 2520 if( (SCIPgetNBinVars(scip) >= 0 || SCIPgetNIntVars(scip) >= 0) && SCIPfindConshdlr(scip, "integral") == NULL ) 2521 { 2522 SCIPwarningMessage(scip, "integrality constraint handler not available\n"); 2523 } 2524 2525 /* initialize presolving flag (may be modified in SCIPpresolve()) */ 2526 scip->stat->performpresol = FALSE; 2527 2528 /* if a decomposition exists and Benders' decomposition has been enabled, then a decomposition is performed */ 2529 if( scip->set->stage == SCIP_STAGE_PROBLEM && SCIPdecompstoreGetNOrigDecomps(scip->decompstore) > 0 2530 && scip->set->decomp_applybenders && SCIPgetNActiveBenders(scip) == 0 ) 2531 { 2532 int decompindex = 0; 2533 2534 /* applying the Benders' decomposition */ 2535 SCIP_CALL( SCIPapplyBendersDecomposition(scip, decompindex) ); 2536 } 2537 2538 /* start solving timer */ 2539 SCIPclockStart(scip->stat->solvingtime, scip->set); 2540 SCIPclockStart(scip->stat->solvingtimeoverall, scip->set); 2541 2542 /* capture the CTRL-C interrupt */ 2543 if( scip->set->misc_catchctrlc ) 2544 SCIPinterruptCapture(scip->interrupt); 2545 2546 /* reset the user interrupt flag */ 2547 scip->stat->userinterrupt = FALSE; 2548 SCIP_CALL( SCIPinterruptLP(scip, FALSE) ); 2549 2550 /* automatic restarting loop */ 2551 restart = scip->stat->userrestart; 2552 2553 do 2554 { 2555 if( restart ) 2556 { 2557 transferstatistics = TRUE; 2558 cutpoolncutsfoundbeforerestart = SCIPcutpoolGetNCutsFound(scip->cutpool); 2559 cutpoolncutsaddedbeforerestart = SCIPcutpoolGetNCutsAdded(scip->cutpool); 2560 cutpooltimebeforerestart = SCIPcutpoolGetTime(scip->cutpool); 2561 cutpoolncallsbeforerestart = SCIPcutpoolGetNCalls(scip->cutpool); 2562 cutpoolnrootcallsbeforerestart = SCIPcutpoolGetNRootCalls(scip->cutpool); 2563 cutpoolmaxncutsbeforerestart = SCIPcutpoolGetMaxNCuts(scip->cutpool); 2564 2565 /* free the solving process data in order to restart */ 2566 assert(scip->set->stage == SCIP_STAGE_SOLVING); 2567 if( scip->stat->userrestart ) 2568 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, 2569 "(run %d, node %" SCIP_LONGINT_FORMAT ") performing user restart\n", 2570 scip->stat->nruns, scip->stat->nnodes); 2571 else 2572 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, 2573 "(run %d, node %" SCIP_LONGINT_FORMAT ") restarting after %d global fixings of integer variables\n", 2574 scip->stat->nruns, scip->stat->nnodes, scip->stat->nrootintfixingsrun); 2575 /* an extra blank line should be printed separately since the buffer message handler only handles up to one line 2576 * correctly */ 2577 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n"); 2578 /* reset relaxation solution, so that the objective value is recomputed from scratch next time, using the new 2579 * fixings which may be produced during the presolving after the restart */ 2580 SCIP_CALL( SCIPclearRelaxSolVals(scip, NULL) ); 2581 2582 SCIP_CALL( freeSolve(scip, TRUE) ); 2583 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED); 2584 } 2585 restart = FALSE; 2586 scip->stat->userrestart = FALSE; 2587 2588 switch( scip->set->stage ) 2589 { 2590 case SCIP_STAGE_PROBLEM: 2591 case SCIP_STAGE_TRANSFORMED: 2592 case SCIP_STAGE_PRESOLVING: 2593 /* initialize solving data structures, transform and problem */ 2594 2595 SCIP_CALL( SCIPpresolve(scip) ); 2596 /* remember that we already printed the relevant statistics */ 2597 if( scip->set->stage == SCIP_STAGE_SOLVED ) 2598 statsprinted = TRUE; 2599 2600 if( scip->set->stage == SCIP_STAGE_SOLVED || scip->set->stage == SCIP_STAGE_PRESOLVING ) 2601 { 2602 if ( scip->set->reopt_enable ) 2603 { 2604 SCIP_CALL( prepareReoptimization(scip) ); 2605 } 2606 break; 2607 } 2608 assert(scip->set->stage == SCIP_STAGE_PRESOLVED); 2609 2610 if( SCIPsolveIsStopped(scip->set, scip->stat, FALSE) ) 2611 break; 2612 /*lint -fallthrough*/ 2613 2614 case SCIP_STAGE_PRESOLVED: 2615 /* check if reoptimization is enabled and global constraints are saved */ 2616 if( scip->set->reopt_enable ) 2617 { 2618 SCIP_CALL( prepareReoptimization(scip) ); 2619 } 2620 2621 /* initialize solving process data structures */ 2622 SCIP_CALL( initSolve(scip, FALSE) ); 2623 assert(scip->set->stage == SCIP_STAGE_SOLVING); 2624 SCIPmessagePrintVerbInfo(scip->messagehdlr, scip->set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, "\n"); 2625 2626 /*lint -fallthrough*/ 2627 2628 case SCIP_STAGE_SOLVING: 2629 /* reset display */ 2630 SCIPstatResetDisplay(scip->stat); 2631 2632 /* remember cutpool statistics after restart */ 2633 if( transferstatistics ) 2634 { 2635 SCIPcutpoolAddNCutsFound(scip->cutpool, cutpoolncutsfoundbeforerestart); 2636 SCIPcutpoolAddNCutsAdded(scip->cutpool, cutpoolncutsaddedbeforerestart); 2637 SCIPcutpoolSetTime(scip->cutpool, cutpooltimebeforerestart); 2638 SCIPcutpoolAddNCalls(scip->cutpool, cutpoolncallsbeforerestart); 2639 SCIPcutpoolAddNRootCalls(scip->cutpool, cutpoolnrootcallsbeforerestart); 2640 SCIPcutpoolAddMaxNCuts(scip->cutpool, cutpoolmaxncutsbeforerestart); 2641 } 2642 2643 /* continue solution process */ 2644 SCIP_CALL( SCIPsolveCIP(scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->mem, scip->origprob, scip->transprob, 2645 scip->primal, scip->tree, scip->reopt, scip->lp, scip->relaxation, scip->pricestore, scip->sepastore, 2646 scip->cutpool, scip->delayedcutpool, scip->branchcand, scip->conflict, scip->conflictstore, 2647 scip->eventfilter, scip->eventqueue, scip->cliquetable, &restart) ); 2648 2649 /* detect, whether problem is solved */ 2650 if( SCIPtreeGetNNodes(scip->tree) == 0 && SCIPtreeGetCurrentNode(scip->tree) == NULL ) 2651 { 2652 assert(scip->stat->status == SCIP_STATUS_OPTIMAL 2653 || scip->stat->status == SCIP_STATUS_INFEASIBLE 2654 || scip->stat->status == SCIP_STATUS_UNBOUNDED 2655 || scip->stat->status == SCIP_STATUS_INFORUNBD); 2656 assert(!restart); 2657 2658 /* tree is empty, and no current node exists -> problem is solved */ 2659 scip->set->stage = SCIP_STAGE_SOLVED; 2660 } 2661 break; 2662 2663 case SCIP_STAGE_SOLVED: 2664 assert(scip->stat->status == SCIP_STATUS_OPTIMAL 2665 || scip->stat->status == SCIP_STATUS_INFEASIBLE 2666 || scip->stat->status == SCIP_STATUS_UNBOUNDED 2667 || scip->stat->status == SCIP_STATUS_INFORUNBD); 2668 2669 break; 2670 2671 default: 2672 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage); 2673 return SCIP_INVALIDCALL; 2674 } /*lint !e788*/ 2675 } 2676 while( restart && !SCIPsolveIsStopped(scip->set, scip->stat, TRUE) ); 2677 2678 /* we have to store all unprocessed nodes if reoptimization is enabled */ 2679 if( scip->set->reopt_enable && scip->set->stage != SCIP_STAGE_PRESOLVING 2680 && SCIPsolveIsStopped(scip->set, scip->stat, TRUE) ) 2681 { 2682 /* save unprocessed nodes */ 2683 if( SCIPgetNNodesLeft(scip) > 0 ) 2684 { 2685 SCIP_NODE** leaves; 2686 SCIP_NODE** children; 2687 SCIP_NODE** siblings; 2688 int nleaves; 2689 int nchildren; 2690 int nsiblings; 2691 2692 /* get all open leave nodes */ 2693 SCIP_CALL( SCIPgetLeaves(scip, &leaves, &nleaves) ); 2694 2695 /* get all open children nodes */ 2696 SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) ); 2697 2698 /* get all open sibling nodes */ 2699 SCIP_CALL( SCIPgetSiblings(scip, &siblings, &nsiblings) ); 2700 2701 /* add all open node to the reoptimization tree */ 2702 SCIP_CALL( SCIPreoptSaveOpenNodes(scip->reopt, scip->set, scip->lp, scip->mem->probmem, leaves, nleaves, 2703 children, nchildren, siblings, nsiblings) ); 2704 } 2705 } 2706 2707 /* release the CTRL-C interrupt */ 2708 if( scip->set->misc_catchctrlc ) 2709 SCIPinterruptRelease(scip->interrupt); 2710 2711 if( scip->set->reopt_enable ) 2712 { 2713 /* save found solutions */ 2714 int nsols; 2715 int s; 2716 2717 nsols = scip->set->reopt_savesols == -1 ? INT_MAX : MAX(scip->set->reopt_savesols, 1); 2718 nsols = MIN(scip->primal->nsols, nsols); 2719 2720 for( s = 0; s < nsols; s++ ) 2721 { 2722 SCIP_SOL* sol; 2723 SCIP_Bool added; 2724 2725 sol = scip->primal->sols[s]; 2726 assert(sol != NULL); 2727 2728 if( !SCIPsolIsOriginal(sol) ) 2729 { 2730 SCIP_Bool hasinfval; 2731 2732 /* retransform solution into the original problem space */ 2733 SCIP_CALL( SCIPsolRetransform(sol, scip->set, scip->stat, scip->origprob, scip->transprob, &hasinfval) ); 2734 } 2735 2736 if( SCIPsolGetNodenum(sol) > 0 || SCIPsolGetHeur(sol) != NULL || (s == 0 && scip->set->reopt_sepabestsol) ) 2737 { 2738 /* if the best solution should be separated, we must not store it in the solution tree */ 2739 if( s == 0 && scip->set->reopt_sepabestsol ) 2740 { 2741 SCIP_CALL( SCIPreoptAddOptSol(scip->reopt, sol, scip->mem->probmem, scip->set, scip->stat, scip->origprimal, 2742 scip->origprob->vars, scip->origprob->nvars) ); 2743 } 2744 /* add solution to solution tree */ 2745 else 2746 { 2747 SCIPdebugMsg(scip, "try to add solution to the solution tree:\n"); 2748 SCIPdebug( SCIP_CALL( SCIPsolPrint(sol, scip->set, scip->messagehdlr, scip->stat, scip->origprob, \ 2749 scip->transprob, NULL, FALSE, FALSE) ); ); 2750 2751 SCIP_CALL( SCIPreoptAddSol(scip->reopt, scip->set, scip->stat, scip->origprimal, scip->mem->probmem, 2752 sol, s == 0, &added, scip->origprob->vars, scip->origprob->nvars, scip->stat->nreoptruns) ); 2753 } 2754 } 2755 } 2756 2757 SCIPdebugMsg(scip, "-> saved %d solution.\n", nsols); 2758 2759 /* store variable history */ 2760 if( scip->set->reopt_storevarhistory ) 2761 { 2762 SCIP_CALL( SCIPreoptUpdateVarHistory(scip->reopt, scip->set, scip->stat, scip->mem->probmem, 2763 scip->origprob->vars, scip->origprob->nvars) ); 2764 } 2765 } 2766 2767 /* stop solving timer */ 2768 SCIPclockStop(scip->stat->solvingtime, scip->set); 2769 SCIPclockStop(scip->stat->solvingtimeoverall, scip->set); 2770 2771 /* decrease time limit during reoptimization */ 2772 if( scip->set->reopt_enable && scip->set->reopt_commontimelimit ) 2773 { 2774 SCIP_Real timelimit; 2775 SCIP_Real usedtime; 2776 2777 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) ); 2778 usedtime = SCIPgetSolvingTime(scip); 2779 timelimit = timelimit - usedtime; 2780 timelimit = MAX(0, timelimit); 2781 2782 SCIP_CALL( SCIPsetRealParam(scip, "limits/time", timelimit) ); 2783 } 2784 2785 if( !statsprinted ) 2786 { 2787 /* display most relevant statistics */ 2788 SCIP_CALL( displayRelevantStats(scip) ); 2789 } 2790 2791 return SCIP_OKAY; 2792 } 2793 2794 /** transforms, presolves, and solves problem using the configured concurrent solvers 2795 * 2796 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 2797 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 2798 * 2799 * @pre This method can be called if @p scip is in one of the following stages: 2800 * - \ref SCIP_STAGE_PROBLEM 2801 * - \ref SCIP_STAGE_TRANSFORMED 2802 * - \ref SCIP_STAGE_PRESOLVING 2803 * - \ref SCIP_STAGE_PRESOLVED 2804 * - \ref SCIP_STAGE_SOLVING 2805 * - \ref SCIP_STAGE_SOLVED 2806 * 2807 * @post After calling this method \SCIP reaches one of the following stages depending on if and when the solution 2808 * process was interrupted: 2809 * - \ref SCIP_STAGE_PRESOLVING if the solution process was interrupted during presolving 2810 * - \ref SCIP_STAGE_SOLVING if the solution process was interrupted during the tree search 2811 * - \ref SCIP_STAGE_SOLVED if the solving process was not interrupted 2812 * 2813 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 2814 * 2815 * @deprecated Please use SCIPsolveConcurrent() instead. 2816 */ 2817 SCIP_RETCODE SCIPsolveParallel( 2818 SCIP* scip /**< SCIP data structure */ 2819 ) 2820 { 2821 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveParallel", FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 2822 2823 return SCIPsolveConcurrent(scip); 2824 } 2825 2826 /** transforms, presolves, and solves problem using the configured concurrent solvers 2827 * 2828 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 2829 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 2830 * 2831 * @pre This method can be called if @p scip is in one of the following stages: 2832 * - \ref SCIP_STAGE_PROBLEM 2833 * - \ref SCIP_STAGE_TRANSFORMED 2834 * - \ref SCIP_STAGE_PRESOLVING 2835 * - \ref SCIP_STAGE_PRESOLVED 2836 * - \ref SCIP_STAGE_SOLVING 2837 * - \ref SCIP_STAGE_SOLVED 2838 * 2839 * @post After calling this method \SCIP reaches one of the following stages depending on if and when the solution 2840 * process was interrupted: 2841 * - \ref SCIP_STAGE_PRESOLVING if the solution process was interrupted during presolving 2842 * - \ref SCIP_STAGE_SOLVING if the solution process was interrupted during the tree search 2843 * - \ref SCIP_STAGE_SOLVED if the solving process was not interrupted 2844 * 2845 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 2846 */ 2847 SCIP_RETCODE SCIPsolveConcurrent( 2848 SCIP* scip /**< SCIP data structure */ 2849 ) 2850 { 2851 #ifdef TPI_NONE 2852 SCIPinfoMessage(scip, NULL, "SCIP was compiled without task processing interface. Parallel solve not possible\n"); 2853 return SCIP_OKAY; 2854 #else 2855 SCIP_RETCODE retcode; 2856 int i; 2857 SCIP_RANDNUMGEN* rndgen; 2858 int minnthreads; 2859 int maxnthreads; 2860 2861 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveConcurrent", FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 2862 2863 SCIP_CALL( SCIPsetIntParam(scip, "timing/clocktype", SCIP_CLOCKTYPE_WALL) ); 2864 2865 minnthreads = scip->set->parallel_minnthreads; 2866 maxnthreads = scip->set->parallel_maxnthreads; 2867 2868 if( minnthreads > maxnthreads ) 2869 { 2870 SCIPerrorMessage("minimum number of threads greater than maximum number of threads\n"); 2871 return SCIP_INVALIDDATA; 2872 } 2873 if( scip->concurrent == NULL ) 2874 { 2875 int nconcsolvertypes; 2876 SCIP_CONCSOLVERTYPE** concsolvertypes; 2877 SCIP_Longint nthreads; 2878 SCIP_Real memorylimit; 2879 int* solvertypes; 2880 SCIP_Longint* weights; 2881 SCIP_Real* prios; 2882 int ncandsolvertypes; 2883 SCIP_Real prefpriosum; 2884 2885 /* check if concurrent solve is configured to presolve the problem 2886 * before setting up the concurrent solvers 2887 */ 2888 if( scip->set->concurrent_presolvebefore ) 2889 { 2890 /* if yes, then presolve the problem */ 2891 SCIP_CALL( SCIPpresolve(scip) ); 2892 if( SCIPgetStatus(scip) >= SCIP_STATUS_OPTIMAL ) 2893 return SCIP_OKAY; 2894 } 2895 else 2896 { 2897 SCIP_Bool infeas; 2898 2899 /* if not, transform the problem and switch stage to presolved */ 2900 SCIP_CALL( SCIPtransformProb(scip) ); 2901 SCIP_CALL( initPresolve(scip) ); 2902 SCIP_CALL( exitPresolve(scip, TRUE, &infeas) ); 2903 assert(!infeas); 2904 } 2905 2906 /* the presolving must have run into a limit, so we stop here */ 2907 if( scip->set->stage < SCIP_STAGE_PRESOLVED ) 2908 { 2909 SCIP_CALL( displayRelevantStats(scip) ); 2910 return SCIP_OKAY; 2911 } 2912 2913 nthreads = INT_MAX; 2914 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */ 2915 memorylimit = scip->set->limit_memory; 2916 if( memorylimit < SCIP_MEM_NOLIMIT ) 2917 { 2918 memorylimit -= SCIPgetMemUsed(scip)/1048576.0; 2919 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0; 2920 /* estimate maximum number of copies that be created based on memory limit */ 2921 if( !scip->set->misc_avoidmemout ) 2922 { 2923 nthreads = MAX(1, memorylimit / (4.0*SCIPgetMemExternEstim(scip)/1048576.0)); 2924 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "estimated a maximum of %lli threads based on memory limit\n", nthreads); 2925 } 2926 else 2927 { 2928 nthreads = minnthreads; 2929 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "ignoring memory limit; all threads can be created\n"); 2930 } 2931 } 2932 nconcsolvertypes = SCIPgetNConcsolverTypes(scip); 2933 concsolvertypes = SCIPgetConcsolverTypes(scip); 2934 2935 if( minnthreads > nthreads ) 2936 { 2937 SCIP_CALL( initSolve(scip, TRUE) ); 2938 scip->stat->status = SCIP_STATUS_MEMLIMIT; 2939 SCIPsyncstoreSetSolveIsStopped(SCIPgetSyncstore(scip), TRUE); 2940 SCIPwarningMessage(scip, "requested minimum number of threads could not be satisfied with given memory limit\n"); 2941 SCIP_CALL( displayRelevantStats(scip) ); 2942 return SCIP_OKAY; 2943 } 2944 2945 if( nthreads == 1 ) 2946 { 2947 SCIPwarningMessage(scip, "can only use 1 thread, doing sequential solve instead\n"); 2948 SCIP_CALL( SCIPfreeConcurrent(scip) ); 2949 return SCIPsolve(scip); 2950 } 2951 nthreads = MIN(nthreads, maxnthreads); 2952 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "using %lli threads for concurrent solve\n", nthreads); 2953 2954 /* now set up nthreads many concurrent solvers that will be used for the concurrent solve 2955 * using the preferred priorities of each concurrent solver 2956 */ 2957 prefpriosum = 0.0; 2958 for( i = 0; i < nconcsolvertypes; ++i ) 2959 prefpriosum += SCIPconcsolverTypeGetPrefPrio(concsolvertypes[i]); 2960 2961 ncandsolvertypes = 0; 2962 SCIP_CALL( SCIPallocBufferArray(scip, &solvertypes, nthreads + nconcsolvertypes) ); 2963 SCIP_CALL( SCIPallocBufferArray(scip, &weights, nthreads + nconcsolvertypes) ); 2964 SCIP_CALL( SCIPallocBufferArray(scip, &prios, nthreads + nconcsolvertypes) ); 2965 for( i = 0; i < nconcsolvertypes; ++i ) 2966 { 2967 int j; 2968 SCIP_Real prio; 2969 prio = nthreads * SCIPconcsolverTypeGetPrefPrio(concsolvertypes[i]) / prefpriosum; 2970 while( prio > 0.0 ) 2971 { 2972 j = ncandsolvertypes++; 2973 assert(j < 2*nthreads); 2974 weights[j] = 1; 2975 solvertypes[j] = i; 2976 prios[j] = MIN(1.0, prio); 2977 prio = prio - 1.0; 2978 } 2979 } 2980 /* select nthreads many concurrent solver types to create instances 2981 * according to the preferred prioriteis the user has set 2982 * This basically corresponds to a knapsack problem 2983 * with unit weights and capacity nthreads, where the profits are 2984 * the unrounded fraction of the total number of threads to be used. 2985 */ 2986 SCIPselectDownRealInt(prios, solvertypes, nthreads, ncandsolvertypes); 2987 2988 SCIP_CALL( SCIPcreateRandom(scip, &rndgen, (unsigned) scip->set->concurrent_initseed, TRUE) ); 2989 for( i = 0; i < nthreads; ++i ) 2990 { 2991 SCIP_CONCSOLVER* concsolver; 2992 2993 SCIP_CALL( SCIPconcsolverCreateInstance(scip->set, concsolvertypes[solvertypes[i]], &concsolver) ); 2994 if( scip->set->concurrent_changeseeds && SCIPgetNConcurrentSolvers(scip) > 1 ) 2995 SCIP_CALL( SCIPconcsolverInitSeeds(concsolver, SCIPrandomGetInt(rndgen, 0, INT_MAX)) ); 2996 } 2997 SCIPfreeRandom(scip, &rndgen); 2998 SCIPfreeBufferArray(scip, &prios); 2999 SCIPfreeBufferArray(scip, &weights); 3000 SCIPfreeBufferArray(scip, &solvertypes); 3001 3002 assert(SCIPgetNConcurrentSolvers(scip) == nthreads); 3003 3004 SCIP_CALL( SCIPsyncstoreInit(scip) ); 3005 } 3006 3007 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVED ) 3008 { 3009 /* switch stage to solving */ 3010 SCIP_CALL( initSolve(scip, TRUE) ); 3011 } 3012 3013 SCIPclockStart(scip->stat->solvingtime, scip->set); 3014 retcode = SCIPconcurrentSolve(scip); 3015 SCIPclockStop(scip->stat->solvingtime, scip->set); 3016 SCIP_CALL( displayRelevantStats(scip) ); 3017 3018 return retcode; 3019 #endif 3020 } 3021 3022 /** include specific heuristics and branching rules for reoptimization 3023 * 3024 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 3025 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 3026 * 3027 * @pre This method can be called if @p scip is in one of the following stages: 3028 * - \ref SCIP_STAGE_PROBLEM 3029 */ 3030 SCIP_RETCODE SCIPenableReoptimization( 3031 SCIP* scip, /**< SCIP data structure */ 3032 SCIP_Bool enable /**< enable reoptimization (TRUE) or disable it (FALSE) */ 3033 ) 3034 { 3035 assert(scip != NULL); 3036 3037 /* we want to skip if nothing has changed */ 3038 if( (enable && scip->set->reopt_enable && scip->reopt != NULL) 3039 || (!enable && !scip->set->reopt_enable && scip->reopt == NULL) ) 3040 return SCIP_OKAY; 3041 3042 /* check stage and throw an error if we try to disable reoptimization during the solving process. 3043 * 3044 * @note the case that we will disable the reoptimization and have already performed presolving can only happen if 3045 * we are try to solve a general MIP 3046 * 3047 * @note this fix is only for the bugfix release 3.2.1, in the next major release reoptimization can be used for 3048 * general MIPs, too. 3049 */ 3050 if( scip->set->stage > SCIP_STAGE_PROBLEM && !(!enable && scip->set->stage == SCIP_STAGE_PRESOLVED) ) 3051 { 3052 SCIPerrorMessage("Reoptimization cannot be %s after starting the (pre)solving process.\n", enable ? "enabled" : "disabled"); 3053 return SCIP_INVALIDCALL; 3054 } 3055 3056 /* if the current stage is SCIP_STAGE_PROBLEM we have to include the heuristics and branching rule */ 3057 if( scip->set->stage == SCIP_STAGE_PROBLEM || (!enable && scip->set->stage == SCIP_STAGE_PRESOLVED) ) 3058 { 3059 /* initialize all reoptimization data structures */ 3060 if( enable && scip->reopt == NULL ) 3061 { 3062 /* set enable flag */ 3063 scip->set->reopt_enable = enable; 3064 3065 SCIP_CALL( SCIPreoptCreate(&scip->reopt, scip->set, scip->mem->probmem) ); 3066 SCIP_CALL( SCIPsetSetReoptimizationParams(scip->set, scip->messagehdlr) ); 3067 } 3068 /* disable all reoptimization plugins and free the structure if necessary */ 3069 else if( (!enable && scip->reopt != NULL) || (!enable && scip->set->reopt_enable && scip->reopt == NULL) ) 3070 { 3071 /* set enable flag */ 3072 scip->set->reopt_enable = enable; 3073 3074 if( scip->reopt != NULL ) 3075 { 3076 SCIP_CALL( SCIPreoptFree(&(scip->reopt), scip->set, scip->origprimal, scip->mem->probmem) ); 3077 assert(scip->reopt == NULL); 3078 } 3079 SCIP_CALL( SCIPsetSetReoptimizationParams(scip->set, scip->messagehdlr) ); 3080 } 3081 } 3082 else 3083 { 3084 /* set enable flag */ 3085 scip->set->reopt_enable = enable; 3086 } 3087 3088 return SCIP_OKAY; 3089 } 3090 3091 /** save bound change based on dual information in the reoptimization tree 3092 * 3093 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 3094 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 3095 * 3096 * @pre This method can be called if @p scip is in one of the following stages: 3097 * - \ref SCIP_STAGE_SOLVING 3098 * - \ref SCIP_STAGE_SOLVED 3099 */ 3100 SCIP_RETCODE SCIPaddReoptDualBndchg( 3101 SCIP* scip, /**< SCIP data structure */ 3102 SCIP_NODE* node, /**< node of the search tree */ 3103 SCIP_VAR* var, /**< variable whose bound changed */ 3104 SCIP_Real newbound, /**< new bound of the variable */ 3105 SCIP_Real oldbound /**< old bound of the variable */ 3106 ) 3107 { 3108 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddReoptDualBndchg", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 3109 3110 assert(SCIPsetIsFeasLT(scip->set, newbound, oldbound) || SCIPsetIsFeasGT(scip->set, newbound, oldbound)); 3111 3112 SCIP_CALL( SCIPreoptAddDualBndchg(scip->reopt, scip->set, scip->mem->probmem, node, var, newbound, oldbound) ); 3113 3114 return SCIP_OKAY; 3115 } 3116 3117 /** returns the optimal solution of the last iteration or NULL of none exists */ 3118 SCIP_SOL* SCIPgetReoptLastOptSol( 3119 SCIP* scip /**< SCIP data structure */ 3120 ) 3121 { 3122 SCIP_SOL* sol; 3123 3124 assert(scip != NULL); 3125 3126 sol = NULL; 3127 3128 if( scip->set->reopt_enable && scip->stat->nreoptruns > 1 ) 3129 { 3130 sol = SCIPreoptGetLastBestSol(scip->reopt); 3131 } 3132 3133 return sol; 3134 } 3135 3136 /** returns the objective coefficent of a given variable in a previous iteration 3137 * 3138 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 3139 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 3140 * 3141 * @pre This method can be called if @p scip is in one of the following stages: 3142 * - \ref SCIP_STAGE_PRESOLVING 3143 * - \ref SCIP_STAGE_SOLVING 3144 */ 3145 SCIP_RETCODE SCIPgetReoptOldObjCoef( 3146 SCIP* scip, /**< SCIP data structure */ 3147 SCIP_VAR* var, /**< variable */ 3148 int run, /**< number of the run */ 3149 SCIP_Real* objcoef /**< pointer to store the objective coefficient */ 3150 ) 3151 { 3152 assert(scip != NULL); 3153 assert(var != NULL); 3154 assert(0 < run && run <= scip->stat->nreoptruns); 3155 3156 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetReoptOldObjCoef", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 3157 3158 if( SCIPvarIsOriginal(var) ) 3159 *objcoef = SCIPreoptGetOldObjCoef(scip->reopt, run, SCIPvarGetIndex(var)); 3160 else 3161 { 3162 SCIP_VAR* origvar; 3163 SCIP_Real constant; 3164 SCIP_Real scalar; 3165 3166 assert(SCIPvarIsActive(var)); 3167 3168 origvar = var; 3169 constant = 0.0; 3170 scalar = 1.0; 3171 3172 SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) ); 3173 assert(origvar != NULL); 3174 assert(SCIPvarIsOriginal(origvar)); 3175 3176 *objcoef = SCIPreoptGetOldObjCoef(scip->reopt, run, SCIPvarGetIndex(origvar)); 3177 } 3178 return SCIP_OKAY; 3179 } 3180 3181 /** frees branch and bound tree and all solution process data; statistics, presolving data and transformed problem is 3182 * preserved 3183 * 3184 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 3185 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 3186 * 3187 * @pre This method can be called if @p scip is in one of the following stages: 3188 * - \ref SCIP_STAGE_INIT 3189 * - \ref SCIP_STAGE_PROBLEM 3190 * - \ref SCIP_STAGE_TRANSFORMED 3191 * - \ref SCIP_STAGE_PRESOLVING 3192 * - \ref SCIP_STAGE_PRESOLVED 3193 * - \ref SCIP_STAGE_SOLVING 3194 * - \ref SCIP_STAGE_SOLVED 3195 * 3196 * @post If this method is called in \SCIP stage \ref SCIP_STAGE_INIT or \ref SCIP_STAGE_PROBLEM, the stage of 3197 * \SCIP is not changed; otherwise, the \SCIP stage is changed to \ref SCIP_STAGE_TRANSFORMED 3198 * 3199 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 3200 */ 3201 SCIP_RETCODE SCIPfreeSolve( 3202 SCIP* scip, /**< SCIP data structure */ 3203 SCIP_Bool restart /**< should certain data be preserved for improved restarting? */ 3204 ) 3205 { 3206 SCIP_CALL( SCIPcheckStage(scip, "SCIPfreeSolve", TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 3207 3208 switch( scip->set->stage ) 3209 { 3210 case SCIP_STAGE_INIT: 3211 case SCIP_STAGE_TRANSFORMED: 3212 case SCIP_STAGE_PROBLEM: 3213 return SCIP_OKAY; 3214 3215 case SCIP_STAGE_PRESOLVING: 3216 { 3217 SCIP_Bool infeasible; 3218 3219 assert(scip->stat->status != SCIP_STATUS_INFEASIBLE); 3220 assert(scip->stat->status != SCIP_STATUS_INFORUNBD); 3221 assert(scip->stat->status != SCIP_STATUS_UNBOUNDED); 3222 assert(scip->stat->status != SCIP_STATUS_OPTIMAL); 3223 3224 /* exit presolving */ 3225 SCIP_CALL( exitPresolve(scip, FALSE, &infeasible) ); 3226 assert(scip->set->stage == SCIP_STAGE_PRESOLVED); 3227 } 3228 3229 /*lint -fallthrough*/ 3230 case SCIP_STAGE_PRESOLVED: 3231 /* switch stage to TRANSFORMED */ 3232 scip->set->stage = SCIP_STAGE_TRANSFORMED; 3233 return SCIP_OKAY; 3234 3235 case SCIP_STAGE_SOLVING: 3236 case SCIP_STAGE_SOLVED: 3237 /* free solution process data structures */ 3238 SCIP_CALL( freeSolve(scip, restart) ); 3239 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED); 3240 return SCIP_OKAY; 3241 3242 default: 3243 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage); 3244 return SCIP_INVALIDCALL; 3245 } /*lint !e788*/ 3246 } 3247 3248 /** frees branch and bound tree and all solution process data; statistics, presolving data and transformed problem is 3249 * preserved 3250 * 3251 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 3252 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 3253 * 3254 * @pre This method can be called if @p scip is in one of the following stages: 3255 * - \ref SCIP_STAGE_INIT 3256 * - \ref SCIP_STAGE_PROBLEM 3257 * - \ref SCIP_STAGE_TRANSFORMED 3258 * - \ref SCIP_STAGE_PRESOLVING 3259 * - \ref SCIP_STAGE_PRESOLVED 3260 * - \ref SCIP_STAGE_SOLVING 3261 * - \ref SCIP_STAGE_SOLVED 3262 * 3263 * @post If this method is called in \SCIP stage \ref SCIP_STAGE_INIT, \ref SCIP_STAGE_TRANSFORMED or \ref SCIP_STAGE_PROBLEM, 3264 * the stage of \SCIP is not changed; otherwise, the \SCIP stage is changed to \ref SCIP_STAGE_PRESOLVED. 3265 * 3266 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 3267 */ 3268 SCIP_RETCODE SCIPfreeReoptSolve( 3269 SCIP* scip /**< SCIP data structure */ 3270 ) 3271 { 3272 SCIP_CALL( SCIPcheckStage(scip, "SCIPfreeReoptSolve", TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 3273 3274 switch( scip->set->stage ) 3275 { 3276 case SCIP_STAGE_INIT: 3277 case SCIP_STAGE_TRANSFORMED: 3278 case SCIP_STAGE_PRESOLVED: 3279 case SCIP_STAGE_PROBLEM: 3280 return SCIP_OKAY; 3281 3282 case SCIP_STAGE_PRESOLVING: 3283 { 3284 SCIP_Bool infeasible; 3285 3286 assert(scip->stat->status != SCIP_STATUS_INFEASIBLE); 3287 assert(scip->stat->status != SCIP_STATUS_INFORUNBD); 3288 assert(scip->stat->status != SCIP_STATUS_UNBOUNDED); 3289 assert(scip->stat->status != SCIP_STATUS_OPTIMAL); 3290 3291 /* exit presolving */ 3292 SCIP_CALL( exitPresolve(scip, FALSE, &infeasible) ); 3293 assert(scip->set->stage == SCIP_STAGE_PRESOLVED); 3294 3295 return SCIP_OKAY; 3296 } 3297 3298 case SCIP_STAGE_SOLVING: 3299 case SCIP_STAGE_SOLVED: 3300 /* free solution process data structures */ 3301 SCIP_CALL( freeReoptSolve(scip) ); 3302 assert(scip->set->stage == SCIP_STAGE_PRESOLVED); 3303 return SCIP_OKAY; 3304 3305 default: 3306 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage); 3307 return SCIP_INVALIDCALL; 3308 } /*lint !e788*/ 3309 } 3310 3311 /** frees all solution process data including presolving and transformed problem, only original problem is kept 3312 * 3313 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 3314 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 3315 * 3316 * @pre This method can be called if @p scip is in one of the following stages: 3317 * - \ref SCIP_STAGE_INIT 3318 * - \ref SCIP_STAGE_PROBLEM 3319 * - \ref SCIP_STAGE_TRANSFORMED 3320 * - \ref SCIP_STAGE_PRESOLVING 3321 * - \ref SCIP_STAGE_PRESOLVED 3322 * - \ref SCIP_STAGE_SOLVING 3323 * - \ref SCIP_STAGE_SOLVED 3324 * 3325 * @post After calling this method \SCIP reaches one of the following stages: 3326 * - \ref SCIP_STAGE_INIT if the method was called from \SCIP stage \ref SCIP_STAGE_INIT 3327 * - \ref SCIP_STAGE_PROBLEM if the method was called from any other of the allowed stages 3328 * 3329 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 3330 */ 3331 SCIP_RETCODE SCIPfreeTransform( 3332 SCIP* scip /**< SCIP data structure */ 3333 ) 3334 { 3335 SCIP_CALL( SCIPcheckStage(scip, "SCIPfreeTransform", TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE) ); 3336 3337 /* release variables and constraints captured by reoptimization */ 3338 if( scip->reopt != NULL ) 3339 { 3340 SCIP_CALL( SCIPreoptReleaseData(scip->reopt, scip->set, scip->mem->probmem) ); 3341 } 3342 3343 switch( scip->set->stage ) 3344 { 3345 case SCIP_STAGE_INIT: 3346 case SCIP_STAGE_PROBLEM: 3347 return SCIP_OKAY; 3348 3349 case SCIP_STAGE_PRESOLVING: 3350 { 3351 SCIP_Bool infeasible; 3352 3353 assert(scip->stat->status != SCIP_STATUS_INFEASIBLE); 3354 assert(scip->stat->status != SCIP_STATUS_INFORUNBD); 3355 assert(scip->stat->status != SCIP_STATUS_UNBOUNDED); 3356 assert(scip->stat->status != SCIP_STATUS_OPTIMAL); 3357 3358 /* exit presolving */ 3359 SCIP_CALL( exitPresolve(scip, FALSE, &infeasible) ); 3360 assert(scip->set->stage == SCIP_STAGE_PRESOLVED); 3361 } 3362 3363 /*lint -fallthrough*/ 3364 case SCIP_STAGE_PRESOLVED: 3365 case SCIP_STAGE_SOLVING: 3366 case SCIP_STAGE_SOLVED: 3367 /* the solve was already freed, we directly go to freeTransform() */ 3368 if( !scip->set->reopt_enable || scip->set->stage != SCIP_STAGE_PRESOLVED ) 3369 { 3370 /* free solution process data */ 3371 SCIP_CALL( SCIPfreeSolve(scip, FALSE) ); 3372 assert(scip->set->stage == SCIP_STAGE_TRANSFORMED); 3373 } 3374 /*lint -fallthrough*/ 3375 3376 case SCIP_STAGE_TRANSFORMED: 3377 /* free transformed problem data structures */ 3378 SCIP_CALL( freeTransform(scip) ); 3379 assert(scip->set->stage == SCIP_STAGE_PROBLEM); 3380 return SCIP_OKAY; 3381 3382 case SCIP_STAGE_TRANSFORMING: 3383 assert(scip->set->stage == SCIP_STAGE_TRANSFORMING); 3384 SCIP_CALL( freeTransforming(scip) ); 3385 assert(scip->set->stage == SCIP_STAGE_PROBLEM); 3386 return SCIP_OKAY; 3387 3388 default: 3389 SCIPerrorMessage("invalid SCIP stage <%d>\n", scip->set->stage); 3390 return SCIP_INVALIDCALL; 3391 } /*lint !e788*/ 3392 } 3393 3394 /** informs \SCIP that the solving process should be interrupted as soon as possible (e.g., after the current node has 3395 * been solved) 3396 * 3397 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 3398 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 3399 * 3400 * @pre This method can be called if @p scip is in one of the following stages: 3401 * - \ref SCIP_STAGE_PROBLEM 3402 * - \ref SCIP_STAGE_TRANSFORMING 3403 * - \ref SCIP_STAGE_TRANSFORMED 3404 * - \ref SCIP_STAGE_INITPRESOLVE 3405 * - \ref SCIP_STAGE_PRESOLVING 3406 * - \ref SCIP_STAGE_EXITPRESOLVE 3407 * - \ref SCIP_STAGE_PRESOLVED 3408 * - \ref SCIP_STAGE_SOLVING 3409 * - \ref SCIP_STAGE_SOLVED 3410 * - \ref SCIP_STAGE_EXITSOLVE 3411 * - \ref SCIP_STAGE_FREETRANS 3412 * 3413 * @note the \SCIP stage does not get changed 3414 */ 3415 SCIP_RETCODE SCIPinterruptSolve( 3416 SCIP* scip /**< SCIP data structure */ 3417 ) 3418 { 3419 SCIP_CALL( SCIPcheckStage(scip, "SCIPinterruptSolve", FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE) ); 3420 3421 /* set the userinterrupt flag */ 3422 scip->stat->userinterrupt = TRUE; 3423 3424 return SCIP_OKAY; 3425 } 3426 3427 /** indicates whether \SCIP has been informed that the solving process should be interrupted as soon as possible 3428 * 3429 * This function returns whether SCIPinterruptSolve() has been called, which is different from SCIPinterrupted(), 3430 * which returns whether a SIGINT signal has been received by the SCIP signal handler. 3431 * 3432 * @pre This method can be called if @p scip is in one of the following stages: 3433 * - \ref SCIP_STAGE_PROBLEM 3434 * - \ref SCIP_STAGE_TRANSFORMING 3435 * - \ref SCIP_STAGE_TRANSFORMED 3436 * - \ref SCIP_STAGE_INITPRESOLVE 3437 * - \ref SCIP_STAGE_PRESOLVING 3438 * - \ref SCIP_STAGE_EXITPRESOLVE 3439 * - \ref SCIP_STAGE_PRESOLVED 3440 * - \ref SCIP_STAGE_SOLVING 3441 * - \ref SCIP_STAGE_SOLVED 3442 * - \ref SCIP_STAGE_EXITSOLVE 3443 * - \ref SCIP_STAGE_FREETRANS 3444 * 3445 * @note the \SCIP stage does not get changed 3446 */ 3447 SCIP_Bool SCIPisSolveInterrupted( 3448 SCIP* scip /**< SCIP data structure */ 3449 ) 3450 { 3451 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisSolveInterrupted", FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE) ); 3452 3453 return scip->stat->userinterrupt; 3454 } 3455 3456 /** informs SCIP that the solving process should be restarted as soon as possible (e.g., after the current node has 3457 * been solved) 3458 * 3459 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 3460 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 3461 * 3462 * @pre This method can be called if @p scip is in one of the following stages: 3463 * - \ref SCIP_STAGE_INITPRESOLVE 3464 * - \ref SCIP_STAGE_PRESOLVING 3465 * - \ref SCIP_STAGE_EXITPRESOLVE 3466 * - \ref SCIP_STAGE_SOLVING 3467 * 3468 * @note the \SCIP stage does not get changed 3469 */ 3470 SCIP_RETCODE SCIPrestartSolve( 3471 SCIP* scip /**< SCIP data structure */ 3472 ) 3473 { 3474 SCIP_CALL( SCIPcheckStage(scip, "SCIPrestartSolve", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 3475 3476 /* set the userrestart flag */ 3477 scip->stat->userrestart = TRUE; 3478 3479 return SCIP_OKAY; 3480 } 3481 3482 /** returns whether reoptimization is enabled or not */ 3483 SCIP_Bool SCIPisReoptEnabled( 3484 SCIP* scip /**< SCIP data structure */ 3485 ) 3486 { 3487 assert(scip != NULL); 3488 3489 return scip->set->reopt_enable; 3490 } 3491 3492 /** returns the stored solutions corresponding to a given run */ 3493 SCIP_RETCODE SCIPgetReoptSolsRun( 3494 SCIP* scip, /**< SCIP data structure */ 3495 int run, /**< number of the run */ 3496 SCIP_SOL** sols, /**< array to store solutions */ 3497 int solssize, /**< size of the array */ 3498 int* nsols /**< pointer to store number of solutions */ 3499 ) 3500 { 3501 assert(scip != NULL); 3502 assert(sols != NULL); 3503 assert(solssize > 0); 3504 3505 if( scip->set->reopt_enable ) 3506 { 3507 assert(run > 0 && run <= scip->stat->nreoptruns); 3508 SCIP_CALL( SCIPreoptGetSolsRun(scip->reopt, run, sols, solssize, nsols) ); 3509 } 3510 else 3511 { 3512 *nsols = 0; 3513 } 3514 3515 return SCIP_OKAY; 3516 } 3517 3518 /** mark all stored solutions as not updated */ 3519 void SCIPresetReoptSolMarks( 3520 SCIP* scip /**< SCIP data structure */ 3521 ) 3522 { 3523 assert(scip != NULL); 3524 assert(scip->set->reopt_enable); 3525 assert(scip->reopt != NULL); 3526 3527 if( scip->set->reopt_enable ) 3528 { 3529 assert(scip->reopt != NULL); 3530 SCIPreoptResetSolMarks(scip->reopt); 3531 } 3532 } 3533 3534 /** check if the reoptimization process should be restarted 3535 * 3536 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 3537 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 3538 * 3539 * @pre This method can be called if @p scip is in one of the following stages: 3540 * - \ref SCIP_STAGE_TRANSFORMED 3541 * - \ref SCIP_STAGE_SOLVING 3542 */ 3543 SCIP_RETCODE SCIPcheckReoptRestart( 3544 SCIP* scip, /**< SCIP data structure */ 3545 SCIP_NODE* node, /**< current node of the branch and bound tree (or NULL) */ 3546 SCIP_Bool* restart /**< pointer to store of the reoptimitation process should be restarted */ 3547 ) 3548 { 3549 assert(scip != NULL); 3550 assert(scip->set->reopt_enable); 3551 assert(scip->reopt != NULL); 3552 3553 SCIP_CALL( SCIPcheckStage(scip, "SCIPcheckReoptRestart", FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 3554 3555 SCIP_CALL( SCIPreoptCheckRestart(scip->reopt, scip->set, scip->mem->probmem, node, scip->transprob->vars, 3556 scip->transprob->nvars, restart) ); 3557 3558 return SCIP_OKAY; 3559 } 3560 3561 /** returns whether we are in the restarting phase 3562 * 3563 * @return TRUE, if we are in the restarting phase; FALSE, otherwise 3564 * 3565 * @pre This method can be called if @p scip is in one of the following stages: 3566 * - \ref SCIP_STAGE_INITPRESOLVE 3567 * - \ref SCIP_STAGE_PRESOLVING 3568 * - \ref SCIP_STAGE_EXITPRESOLVE 3569 * - \ref SCIP_STAGE_PRESOLVED 3570 * - \ref SCIP_STAGE_INITSOLVE 3571 * - \ref SCIP_STAGE_SOLVING 3572 * - \ref SCIP_STAGE_SOLVED 3573 * - \ref SCIP_STAGE_EXITSOLVE 3574 * - \ref SCIP_STAGE_FREETRANS 3575 */ 3576 SCIP_Bool SCIPisInRestart( 3577 SCIP* scip /**< SCIP data structure */ 3578 ) 3579 { 3580 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisInRestart", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) ); 3581 3582 /* return the restart status */ 3583 return scip->stat->inrestart; 3584 } 3585