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 solve.c 26 * @ingroup OTHER_CFILES 27 * @brief main solving loop and node processing 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Marc Pfetsch 31 * @author Gerald Gamrath 32 */ 33 34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 35 #include <assert.h> 36 37 #include "lpi/lpi.h" 38 #include "scip/branch.h" 39 #include "scip/clock.h" 40 #include "scip/concurrent.h" 41 #include "scip/conflict.h" 42 #include "scip/cons.h" 43 #include "scip/cutpool.h" 44 #include "scip/disp.h" 45 #include "scip/event.h" 46 #include "scip/heur.h" 47 #include "scip/interrupt.h" 48 #include "scip/lp.h" 49 #include "scip/nodesel.h" 50 #include "scip/pricer.h" 51 #include "scip/pricestore.h" 52 #include "scip/primal.h" 53 #include "scip/prob.h" 54 #include "scip/prop.h" 55 #include "scip/pub_cons.h" 56 #include "scip/pub_heur.h" 57 #include "scip/pub_message.h" 58 #include "scip/pub_misc.h" 59 #include "scip/pub_pricer.h" 60 #include "scip/pub_prop.h" 61 #include "scip/pub_relax.h" 62 #include "scip/pub_sepa.h" 63 #include "scip/pub_tree.h" 64 #include "scip/pub_var.h" 65 #include "scip/relax.h" 66 #include "scip/reopt.h" 67 #include "scip/scip_concurrent.h" 68 #include "scip/scip_mem.h" 69 #include "scip/scip_prob.h" 70 #include "scip/scip_sol.h" 71 #include "scip/scip_solvingstats.h" 72 #include "scip/sepa.h" 73 #include "scip/sepastore.h" 74 #include "scip/set.h" 75 #include "scip/sol.h" 76 #include "scip/solve.h" 77 #include "scip/stat.h" 78 #include "scip/struct_cons.h" 79 #include "scip/struct_event.h" 80 #include "scip/struct_lp.h" 81 #include "scip/struct_mem.h" 82 #include "scip/struct_primal.h" 83 #include "scip/struct_prob.h" 84 #include "scip/struct_set.h" 85 #include "scip/struct_stat.h" 86 #include "scip/struct_tree.h" 87 #include "scip/struct_var.h" 88 #include "scip/syncstore.h" 89 #include "scip/tree.h" 90 #include "scip/var.h" 91 #include "scip/visual.h" 92 93 94 #define MAXNLPERRORS 10 /**< maximal number of LP error loops in a single node */ 95 #define MAXNCLOCKSKIPS 64 /**< maximum number of SCIPsolveIsStopped() calls without checking the clock */ 96 #define NINITCALLS 1000L /**< minimum number of calls to SCIPsolveIsStopped() prior to dynamic clock skips */ 97 #define SAFETYFACTOR 1e-2 /**< the probability that SCIP skips the clock call after the time limit has already been reached */ 98 99 /** returns whether the solving process will be / was stopped before proving optimality; 100 * if the solving process was stopped, stores the reason as status in stat 101 */ 102 SCIP_Bool SCIPsolveIsStopped( 103 SCIP_SET* set, /**< global SCIP settings */ 104 SCIP_STAT* stat, /**< dynamic problem statistics */ 105 SCIP_Bool checknodelimits /**< should the node limits be involved in the check? */ 106 ) 107 { 108 assert(set != NULL); 109 assert(stat != NULL); 110 111 /* increase the number of calls to this method */ 112 SCIPstatIncrement(stat, set, nisstoppedcalls); 113 114 /* in case lowerbound >= upperbound, we do not want to terminate with SCIP_STATUS_GAPLIMIT but with the ordinary 115 * SCIP_STATUS_OPTIMAL/INFEASIBLE/... 116 */ 117 if( set->stage >= SCIP_STAGE_SOLVING && SCIPsetIsLE(set, SCIPgetUpperbound(set->scip), SCIPgetLowerbound(set->scip)) ) 118 return TRUE; 119 120 /* if some limit has been changed since the last call, we reset the status */ 121 if( set->limitchanged ) 122 { 123 stat->status = SCIP_STATUS_UNKNOWN; 124 set->limitchanged = FALSE; 125 } 126 127 if( SCIPinterrupted() || stat->userinterrupt ) 128 { 129 stat->status = SCIP_STATUS_USERINTERRUPT; 130 stat->userinterrupt = FALSE; 131 132 /* only reset the interrupted counter if this is the main SCIP catching CTRL-C */ 133 if( set->misc_catchctrlc ) 134 { 135 SCIPresetInterrupted(); 136 } 137 } 138 else if( SCIPterminated() ) 139 { 140 stat->status = SCIP_STATUS_TERMINATE; 141 142 return TRUE; 143 } 144 /* only measure the clock if a time limit is set */ 145 else if( set->istimelimitfinite ) 146 { 147 /* check if we have already called this function sufficiently often for a valid estimation of its average call interval */ 148 if( stat->nclockskipsleft <= 0 || stat->nisstoppedcalls < NINITCALLS ) 149 { 150 SCIP_Real currtime = SCIPclockGetTime(stat->solvingtime); 151 152 /* use the measured time to update the average time interval between two calls to this method */ 153 if( set->time_rareclockcheck && stat->nisstoppedcalls >= NINITCALLS ) 154 { 155 SCIP_Real avgisstoppedfreq; 156 int nclockskips = MAXNCLOCKSKIPS; 157 158 avgisstoppedfreq = currtime / stat->nisstoppedcalls; 159 160 /* if we are approaching the time limit, reset the number of clock skips to 0 */ 161 if( (SAFETYFACTOR * (set->limit_time - currtime) / (avgisstoppedfreq + 1e-6)) < nclockskips ) 162 nclockskips = 0; 163 164 stat->nclockskipsleft = nclockskips; 165 } 166 else 167 stat->nclockskipsleft = 0; 168 169 /* set the status if the time limit was hit */ 170 if( currtime >= set->limit_time ) 171 { 172 stat->status = SCIP_STATUS_TIMELIMIT; 173 return TRUE; 174 } 175 } 176 else if( SCIPclockGetLastTime(stat->solvingtime) >= set->limit_time ) 177 { 178 /* use information if clock has been updated more recently */ 179 stat->status = SCIP_STATUS_TIMELIMIT; 180 return TRUE; 181 } 182 else 183 --stat->nclockskipsleft; 184 } 185 if( SCIPgetConcurrentMemTotal(set->scip) >= set->limit_memory*1048576.0 - stat->externmemestim * (1.0 + SCIPgetNConcurrentSolvers(set->scip)) ) 186 stat->status = SCIP_STATUS_MEMLIMIT; 187 else if( SCIPgetNLimSolsFound(set->scip) > 0 188 && (SCIPsetIsLT(set, SCIPgetGap(set->scip), set->limit_gap) 189 || SCIPsetIsLT(set, (SCIPgetUpperbound(set->scip) - SCIPgetLowerbound(set->scip)) * SCIPgetTransObjscale(set->scip), set->limit_absgap )) ) 190 stat->status = SCIP_STATUS_GAPLIMIT; 191 else if( set->limit_solutions >= 0 && set->stage >= SCIP_STAGE_PRESOLVING 192 && SCIPgetNLimSolsFound(set->scip) >= set->limit_solutions ) 193 stat->status = SCIP_STATUS_SOLLIMIT; 194 else if( set->limit_bestsol >= 0 && set->stage >= SCIP_STAGE_PRESOLVING 195 && SCIPgetNBestSolsFound(set->scip) >= set->limit_bestsol ) 196 stat->status = SCIP_STATUS_BESTSOLLIMIT; 197 else if( checknodelimits && set->limit_nodes >= 0 && stat->nnodes >= set->limit_nodes ) 198 stat->status = SCIP_STATUS_NODELIMIT; 199 else if( checknodelimits && set->limit_totalnodes >= 0 && stat->ntotalnodes >= set->limit_totalnodes ) 200 stat->status = SCIP_STATUS_TOTALNODELIMIT; 201 else if( checknodelimits && set->limit_stallnodes >= 0 && stat->nnodes >= stat->bestsolnode + set->limit_stallnodes ) 202 stat->status = SCIP_STATUS_STALLNODELIMIT; 203 204 /* If stat->status was initialized to SCIP_STATUS_NODELIMIT or SCIP_STATUS_STALLNODELIMIT due to a previous call to SCIPsolveIsStopped(,,TRUE), 205 * in the case of checknodelimits == FALSE, we do not want to report here that the solve will be stopped due to a nodelimit. 206 */ 207 if( !checknodelimits ) 208 return SCIPsyncstoreSolveIsStopped(SCIPgetSyncstore(set->scip)) || (stat->status != SCIP_STATUS_UNKNOWN && stat->status != SCIP_STATUS_NODELIMIT && stat->status != SCIP_STATUS_TOTALNODELIMIT && stat->status != SCIP_STATUS_STALLNODELIMIT); 209 else 210 return SCIPsyncstoreSolveIsStopped(SCIPgetSyncstore(set->scip)) || (stat->status != SCIP_STATUS_UNKNOWN); 211 } 212 213 /** calls primal heuristics */ 214 SCIP_RETCODE SCIPprimalHeuristics( 215 SCIP_SET* set, /**< global SCIP settings */ 216 SCIP_STAT* stat, /**< dynamic problem statistics */ 217 SCIP_PROB* prob, /**< transformed problem after presolve */ 218 SCIP_PRIMAL* primal, /**< primal data */ 219 SCIP_TREE* tree, /**< branch and bound tree, or NULL if called during presolving */ 220 SCIP_LP* lp, /**< LP data, or NULL if called during presolving or propagation */ 221 SCIP_NODE* nextnode, /**< next node that will be processed, or NULL if no more nodes left 222 * (only needed when calling after node heuristics) */ 223 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */ 224 SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */ 225 SCIP_Bool* foundsol, /**< pointer to store whether a solution has been found */ 226 SCIP_Bool* unbounded /**< pointer to store whether an unbounded ray was found in the LP */ 227 ) 228 { /*lint --e{715}*/ 229 SCIP_RESULT result; 230 SCIP_Longint oldnbestsolsfound; 231 SCIP_Real lowerbound; 232 int ndelayedheurs; 233 int depth; 234 int lpstateforkdepth; 235 int h; 236 #ifndef NDEBUG 237 SCIP_Bool inprobing; 238 SCIP_Bool indiving; 239 #endif 240 241 assert(set != NULL); 242 assert(primal != NULL); 243 assert(tree != NULL || heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP); 244 assert(lp != NULL || heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP 245 || heurtiming == SCIP_HEURTIMING_AFTERPROPLOOP); 246 assert(heurtiming == SCIP_HEURTIMING_BEFORENODE || heurtiming == SCIP_HEURTIMING_DURINGLPLOOP 247 || heurtiming == SCIP_HEURTIMING_AFTERLPLOOP || heurtiming == SCIP_HEURTIMING_AFTERNODE 248 || heurtiming == SCIP_HEURTIMING_DURINGPRICINGLOOP || heurtiming == SCIP_HEURTIMING_BEFOREPRESOL 249 || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP || heurtiming == SCIP_HEURTIMING_AFTERPROPLOOP 250 || heurtiming == (SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)); 251 assert(heurtiming != SCIP_HEURTIMING_AFTERNODE || (nextnode == NULL) == (SCIPtreeGetNNodes(tree) == 0)); 252 assert(foundsol != NULL); 253 254 *foundsol = FALSE; 255 256 /* nothing to do, if no heuristics are available, or if the branch-and-bound process is finished */ 257 if( set->nheurs == 0 || (heurtiming == SCIP_HEURTIMING_AFTERNODE && nextnode == NULL) ) 258 return SCIP_OKAY; 259 260 /* do not continue if we reached a time limit */ 261 if( SCIPsolveIsStopped(set, stat, FALSE) ) 262 return SCIP_OKAY; 263 264 /* sort heuristics by priority, but move the delayed heuristics to the front */ 265 SCIPsetSortHeurs(set); 266 267 /* specialize the AFTERNODE timing flag */ 268 if( (heurtiming & SCIP_HEURTIMING_AFTERNODE) == SCIP_HEURTIMING_AFTERNODE ) 269 { 270 SCIP_Bool plunging; 271 SCIP_Bool pseudonode; 272 273 /* clear the AFTERNODE flags and replace them by the right ones */ 274 heurtiming &= ~SCIP_HEURTIMING_AFTERNODE; 275 276 /* we are in plunging mode iff the next node is a sibling or a child, and no leaf */ 277 assert(nextnode == NULL 278 || SCIPnodeGetType(nextnode) == SCIP_NODETYPE_SIBLING 279 || SCIPnodeGetType(nextnode) == SCIP_NODETYPE_CHILD 280 || SCIPnodeGetType(nextnode) == SCIP_NODETYPE_LEAF); 281 plunging = (nextnode != NULL && SCIPnodeGetType(nextnode) != SCIP_NODETYPE_LEAF); 282 pseudonode = !SCIPtreeHasFocusNodeLP(tree); 283 if( plunging && SCIPtreeGetCurrentDepth(tree) > 0 ) /* call plunging heuristics also at root node */ 284 { 285 if( !pseudonode ) 286 heurtiming |= SCIP_HEURTIMING_AFTERLPNODE; 287 else 288 heurtiming |= SCIP_HEURTIMING_AFTERPSEUDONODE; 289 } 290 else 291 { 292 if( !pseudonode ) 293 heurtiming |= SCIP_HEURTIMING_AFTERLPPLUNGE | SCIP_HEURTIMING_AFTERLPNODE; 294 else 295 heurtiming |= SCIP_HEURTIMING_AFTERPSEUDOPLUNGE | SCIP_HEURTIMING_AFTERPSEUDONODE; 296 } 297 } 298 299 /* initialize the tree related data, if we are not in presolving */ 300 if( heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP ) 301 { 302 depth = -1; 303 lpstateforkdepth = -1; 304 305 SCIPsetDebugMsg(set, "calling primal heuristics %s presolving\n", 306 heurtiming == SCIP_HEURTIMING_BEFOREPRESOL ? "before" : "during"); 307 } 308 else 309 { 310 assert(tree != NULL); /* for lint */ 311 depth = SCIPtreeGetFocusDepth(tree); 312 lpstateforkdepth = (tree->focuslpstatefork != NULL ? SCIPnodeGetDepth(tree->focuslpstatefork) : -1); 313 314 SCIPsetDebugMsg(set, "calling primal heuristics in depth %d (timing: %u)\n", depth, heurtiming); 315 } 316 317 /* call heuristics */ 318 ndelayedheurs = 0; 319 oldnbestsolsfound = primal->nbestsolsfound; 320 321 #ifndef NDEBUG 322 /* remember old probing and diving status */ 323 inprobing = tree != NULL && SCIPtreeProbing(tree); 324 indiving = lp != NULL && SCIPlpDiving(lp); 325 326 /* heuristics should currently not be called in diving mode */ 327 assert(!indiving); 328 #endif 329 330 /* collect lower bound of current node */ 331 if( tree != NULL ) 332 { 333 assert(SCIPtreeGetFocusNode(tree) != NULL); 334 lowerbound = SCIPnodeGetLowerbound(SCIPtreeGetFocusNode(tree)); 335 } 336 else if( lp != NULL ) 337 lowerbound = SCIPlpGetPseudoObjval(lp, set, prob); 338 else 339 lowerbound = -SCIPsetInfinity(set); 340 341 for( h = 0; h < set->nheurs; ++h ) 342 { 343 #ifndef NDEBUG 344 size_t nusedbuffer = BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)); 345 #endif 346 /* it might happen that a diving heuristic renders the previously solved node LP invalid 347 * such that additional calls to LP heuristics will fail; better abort the loop in this case 348 */ 349 if( lp != NULL && lp->resolvelperror) 350 break; 351 352 #ifdef SCIP_DEBUG 353 { 354 SCIP_Bool delayed; 355 if( SCIPheurShouldBeExecuted(set->heurs[h], depth, lpstateforkdepth, heurtiming, &delayed) ) 356 { 357 SCIPsetDebugMsg(set, " -> executing heuristic <%s> with priority %d\n", 358 SCIPheurGetName(set->heurs[h]), SCIPheurGetPriority(set->heurs[h])); 359 } 360 } 361 #endif 362 363 SCIP_CALL( SCIPheurExec(set->heurs[h], set, primal, depth, lpstateforkdepth, heurtiming, nodeinfeasible, 364 &ndelayedheurs, &result) ); 365 366 #ifndef NDEBUG 367 if( BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)) > nusedbuffer ) 368 { 369 SCIPerrorMessage("Buffer not completely freed after executing heuristic <%s>\n", SCIPheurGetName(set->heurs[h])); 370 SCIPABORT(); 371 } 372 #endif 373 374 /* if the new solution cuts off the current node due to a new primal solution (via the cutoff bound) interrupt 375 * calling the remaining heuristics 376 */ 377 if( (result == SCIP_FOUNDSOL && lowerbound > primal->cutoffbound) || SCIPsolveIsStopped(set, stat, FALSE) ) 378 break; 379 380 /* check if the problem is proven to be unbounded, currently this happens only in reoptimization */ 381 if( result == SCIP_UNBOUNDED ) 382 { 383 *unbounded = TRUE; 384 break; 385 } 386 387 /* make sure that heuristic did not change probing or diving status */ 388 assert(tree == NULL || inprobing == SCIPtreeProbing(tree)); 389 assert(lp == NULL || indiving == SCIPlpDiving(lp)); 390 } 391 assert(0 <= ndelayedheurs && ndelayedheurs <= set->nheurs); 392 393 *foundsol = (primal->nbestsolsfound > oldnbestsolsfound); 394 395 return SCIP_OKAY; 396 } 397 398 /** applies one round of propagation */ 399 static 400 SCIP_RETCODE propagationRound( 401 BMS_BLKMEM* blkmem, /**< block memory buffers */ 402 SCIP_SET* set, /**< global SCIP settings */ 403 SCIP_STAT* stat, /**< dynamic problem statistics */ 404 SCIP_TREE* tree, /**< branch and bound tree */ 405 int depth, /**< depth level to use for propagator frequency checks */ 406 SCIP_Bool fullpropagation, /**< should all constraints be propagated (or only new ones)? */ 407 SCIP_Bool onlydelayed, /**< should only delayed propagators be called? */ 408 SCIP_Bool* delayed, /**< pointer to store whether a propagator was delayed */ 409 SCIP_Bool* propagain, /**< pointer to store whether propagation should be applied again */ 410 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */ 411 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */ 412 SCIP_Bool* postpone /**< pointer to store whether the node should be postponed */ 413 ) 414 { /*lint --e{715}*/ 415 SCIP_RESULT result; 416 SCIP_Bool abortoncutoff; 417 int i; 418 419 assert(set != NULL); 420 assert(delayed != NULL); 421 assert(propagain != NULL); 422 assert(cutoff != NULL); 423 assert(postpone != NULL); 424 425 *delayed = FALSE; 426 *propagain = FALSE; 427 428 /* sort propagators */ 429 SCIPsetSortProps(set); 430 431 /* check if we want to abort on a cutoff; if we are not in the solving stage (e.g., in presolving), we want to abort 432 * anyway 433 */ 434 abortoncutoff = set->prop_abortoncutoff || (set->stage != SCIP_STAGE_SOLVING); 435 436 /* call additional propagators with nonnegative priority */ 437 for( i = 0; i < set->nprops && !(*postpone) && (!(*cutoff) || !abortoncutoff); ++i ) 438 { 439 #ifndef NDEBUG 440 size_t nusedbuffer = BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)); 441 #endif 442 /* timing needs to fit */ 443 if( (SCIPpropGetTimingmask(set->props[i]) & timingmask) == 0 ) 444 continue; 445 446 if( SCIPpropGetPriority(set->props[i]) < 0 ) 447 continue; 448 449 if( onlydelayed && !SCIPpropWasDelayed(set->props[i]) ) 450 continue; 451 452 SCIPsetDebugMsg(set, "calling propagator <%s>\n", SCIPpropGetName(set->props[i])); 453 454 SCIP_CALL( SCIPpropExec(set->props[i], set, stat, depth, onlydelayed, tree->sbprobing, timingmask, &result) ); 455 456 #ifndef NDEBUG 457 if( BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)) > nusedbuffer ) 458 { 459 SCIPerrorMessage("Buffer not completely freed after executing propagator <%s>\n", SCIPpropGetName(set->props[i])); 460 SCIPABORT(); 461 } 462 #endif 463 464 *delayed = *delayed || (result == SCIP_DELAYED); 465 *propagain = *propagain || (result == SCIP_REDUCEDDOM); 466 467 /* beside the result pointer of the propagator we have to check if an internal cutoff was detected; this can 468 * happen when a global bound change was applied which is globally valid and leads locally (for the current node 469 * and others) to an infeasible problem; 470 */ 471 *cutoff = *cutoff || (result == SCIP_CUTOFF) || (tree->cutoffdepth <= SCIPtreeGetCurrentDepth(tree)); 472 *postpone = (result == SCIP_DELAYNODE) && !(*cutoff); 473 474 if( result == SCIP_CUTOFF ) 475 { 476 SCIPsetDebugMsg(set, " -> propagator <%s> detected cutoff\n", SCIPpropGetName(set->props[i])); 477 } 478 479 /* if we work off the delayed propagators, we stop immediately if a reduction was found */ 480 if( onlydelayed && result == SCIP_REDUCEDDOM ) 481 { 482 *delayed = TRUE; 483 return SCIP_OKAY; 484 } 485 } 486 487 /* propagate constraints */ 488 for( i = 0; i < set->nconshdlrs && !(*postpone) && (!(*cutoff) || !abortoncutoff); ++i ) 489 { 490 /* timing needs to fit */ 491 if( (SCIPconshdlrGetPropTiming(set->conshdlrs[i]) & timingmask) == 0 ) 492 continue; 493 494 if( onlydelayed && !SCIPconshdlrWasPropagationDelayed(set->conshdlrs[i]) ) 495 continue; 496 497 SCIPsetDebugMsg(set, "calling propagation method of constraint handler <%s>\n", SCIPconshdlrGetName(set->conshdlrs[i])); 498 499 SCIP_CALL( SCIPconshdlrPropagate(set->conshdlrs[i], blkmem, set, stat, depth, fullpropagation, onlydelayed, 500 tree->sbprobing, timingmask, &result) ); 501 *delayed = *delayed || (result == SCIP_DELAYED); 502 *propagain = *propagain || (result == SCIP_REDUCEDDOM); 503 504 /* beside the result pointer of the propagator we have to check if an internal cutoff was detected; this can 505 * happen when a global bound change was applied which is globally valid and leads locally (for the current node 506 * and others) to an infeasible problem; 507 */ 508 *cutoff = *cutoff || (result == SCIP_CUTOFF) || (tree->cutoffdepth <= SCIPtreeGetCurrentDepth(tree)); 509 *postpone = (result == SCIP_DELAYNODE) && !(*cutoff); 510 511 if( result == SCIP_CUTOFF ) 512 { 513 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in propagation\n", 514 SCIPconshdlrGetName(set->conshdlrs[i])); 515 } 516 517 /* if we work off the delayed propagators, we stop immediately if a reduction was found */ 518 if( onlydelayed && result == SCIP_REDUCEDDOM ) 519 { 520 *delayed = TRUE; 521 return SCIP_OKAY; 522 } 523 } 524 525 /* call additional propagators with negative priority */ 526 for( i = 0; i < set->nprops && !(*postpone) && (!(*cutoff) || !abortoncutoff); ++i ) 527 { 528 /* timing needs to fit */ 529 if( (SCIPpropGetTimingmask(set->props[i]) & timingmask) == 0 ) 530 continue; 531 532 if( SCIPpropGetPriority(set->props[i]) >= 0 ) 533 continue; 534 535 if( onlydelayed && !SCIPpropWasDelayed(set->props[i]) ) 536 continue; 537 538 SCIPsetDebugMsg(set, "calling propagator <%s>\n", SCIPpropGetName(set->props[i])); 539 540 SCIP_CALL( SCIPpropExec(set->props[i], set, stat, depth, onlydelayed, tree->sbprobing, timingmask, &result) ); 541 *delayed = *delayed || (result == SCIP_DELAYED); 542 *propagain = *propagain || (result == SCIP_REDUCEDDOM); 543 544 /* beside the result pointer of the propagator we have to check if an internal cutoff was detected; this can 545 * happen when a global bound change was applied which is globally valid and leads locally (for the current node 546 * and others) to an infeasible problem; 547 */ 548 *cutoff = *cutoff || (result == SCIP_CUTOFF) || (tree->cutoffdepth <= SCIPtreeGetCurrentDepth(tree)); 549 *postpone = (result == SCIP_DELAYNODE) && !(*cutoff); 550 551 if( result == SCIP_CUTOFF ) 552 { 553 SCIPsetDebugMsg(set, " -> propagator <%s> detected cutoff\n", SCIPpropGetName(set->props[i])); 554 } 555 556 /* if we work off the delayed propagators, we stop immediately if a reduction was found */ 557 if( onlydelayed && result == SCIP_REDUCEDDOM ) 558 { 559 *delayed = TRUE; 560 return SCIP_OKAY; 561 } 562 } 563 564 return SCIP_OKAY; 565 } 566 567 /** applies domain propagation on current node */ 568 static 569 SCIP_RETCODE propagateDomains( 570 BMS_BLKMEM* blkmem, /**< block memory buffers */ 571 SCIP_SET* set, /**< global SCIP settings */ 572 SCIP_STAT* stat, /**< dynamic problem statistics */ 573 SCIP_TREE* tree, /**< branch and bound tree */ 574 int depth, /**< depth level to use for propagator frequency checks */ 575 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */ 576 SCIP_Bool fullpropagation, /**< should all constraints be propagated (or only new ones)? */ 577 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */ 578 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */ 579 SCIP_Bool* postpone /**< pointer to store whether the node should be postponed */ 580 ) 581 { 582 SCIP_NODE* node; 583 SCIP_Bool delayed; 584 SCIP_Bool propagain; 585 int propround; 586 587 assert(set != NULL); 588 assert(tree != NULL); 589 assert(depth >= 0); 590 assert(cutoff != NULL); 591 592 node = SCIPtreeGetCurrentNode(tree); 593 assert(node != NULL && SCIPnodeIsActive(node)); 594 assert(SCIPnodeGetType(node) == SCIP_NODETYPE_FOCUSNODE 595 || SCIPnodeGetType(node) == SCIP_NODETYPE_REFOCUSNODE 596 || SCIPnodeGetType(node) == SCIP_NODETYPE_PROBINGNODE); 597 598 /* adjust maximal number of propagation rounds */ 599 if( maxproprounds == 0 ) 600 maxproprounds = (depth == 0 ? set->prop_maxroundsroot : set->prop_maxrounds); 601 if( maxproprounds == -1 ) 602 maxproprounds = INT_MAX; 603 604 SCIPsetDebugMsg(set, "domain propagation of node %p in depth %d (using depth %d, maxrounds %d, proptiming %u)\n", 605 (void*)node, SCIPnodeGetDepth(node), depth, maxproprounds, timingmask); 606 607 /* propagate as long new bound changes were found and the maximal number of propagation rounds is not exceeded */ 608 *cutoff = FALSE; 609 *postpone = FALSE; 610 propround = 0; 611 propagain = TRUE; 612 while( propagain && !(*cutoff) && !(*postpone) && propround < maxproprounds && !SCIPsolveIsStopped(set, stat, FALSE) ) 613 { 614 propround++; 615 616 /* perform the propagation round by calling the propagators and constraint handlers */ 617 SCIP_CALL( propagationRound(blkmem, set, stat, tree, depth, fullpropagation, FALSE, &delayed, &propagain, timingmask, cutoff, postpone) ); 618 619 /* if the propagation will be terminated, call the delayed propagators */ 620 while( delayed && (!propagain || propround >= maxproprounds) && !(*cutoff) ) 621 { 622 /* call the delayed propagators and constraint handlers */ 623 SCIP_CALL( propagationRound(blkmem, set, stat, tree, depth, fullpropagation, TRUE, &delayed, &propagain, timingmask, cutoff, postpone) ); 624 } 625 626 /* if a reduction was found, we want to do another full propagation round (even if the propagator only claimed 627 * to have done a domain reduction without applying a domain change) 628 */ 629 fullpropagation = TRUE; 630 } 631 632 /* mark the node to be completely propagated in the current repropagation subtree level */ 633 SCIPnodeMarkPropagated(node, tree); 634 635 if( *cutoff ) 636 { 637 SCIPsetDebugMsg(set, " --> domain propagation of node %p finished: cutoff!\n", (void*)node); 638 } 639 640 return SCIP_OKAY; 641 } 642 643 /** applies domain propagation on current node and flushes the conflict store afterwards */ 644 SCIP_RETCODE SCIPpropagateDomains( 645 BMS_BLKMEM* blkmem, /**< block memory buffers */ 646 SCIP_SET* set, /**< global SCIP settings */ 647 SCIP_STAT* stat, /**< dynamic problem statistics */ 648 SCIP_PROB* transprob, /**< transformed problem */ 649 SCIP_PROB* origprob, /**< original problem */ 650 SCIP_TREE* tree, /**< branch and bound tree */ 651 SCIP_REOPT* reopt, /**< reoptimization data structure */ 652 SCIP_LP* lp, /**< LP data */ 653 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 654 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 655 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 656 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 657 int depth, /**< depth level to use for propagator frequency checks */ 658 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */ 659 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */ 660 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 661 ) 662 { 663 SCIP_Bool postpone; 664 665 /* apply domain propagation */ 666 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, depth, maxproprounds, TRUE, timingmask, cutoff, &postpone) ); 667 668 /* flush the conflict set storage */ 669 SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable) ); 670 671 return SCIP_OKAY; 672 } 673 674 /** returns whether the given variable with the old LP solution value should lead to an update of the pseudo cost entry */ 675 static 676 SCIP_Bool isPseudocostUpdateValid( 677 SCIP_VAR* var, /**< problem variable */ 678 SCIP_SET* set, /**< global SCIP settings */ 679 SCIP_Real oldlpsolval, /**< solution value of variable in old LP */ 680 SCIP_Bool updateintegers, /**< whether to update pseudo costs for integer variables */ 681 SCIP_Bool updatecontinuous /**< whether to update pseudo costs for continuous variables */ 682 ) 683 { 684 SCIP_Real newlpsolval; 685 686 assert(var != NULL); 687 688 if( !updatecontinuous && SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 689 return FALSE; 690 691 if( !updateintegers && SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ) 692 return FALSE; 693 694 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS && set->branch_lpgainnorm != 'l' ) 695 { 696 /* if the variable is fixed at +/- infinity or it has an unbounded domain, then the domain-based update strategies will not work */ 697 if( SCIPsetIsInfinity(set, REALABS(SCIPvarGetLbLocal(var))) || SCIPsetIsInfinity(set, REALABS(SCIPvarGetUbLocal(var))) ) 698 return FALSE; 699 700 /* @todo if set->branch_lpgainnorm == 's', then we would need to know then domain before branching 701 * since this is difficult to get, we don't check for unboundedness here and let the pscost update fail later 702 * however, this makes the weights used to spread a pseudo cost update over all domain changes inaccurate 703 */ 704 705 return TRUE; 706 } 707 708 /* if the old LP solution value is unknown, the pseudo cost update cannot be performed */ 709 if( oldlpsolval >= SCIP_INVALID ) 710 return FALSE; 711 712 /* the bound change on the given variable was responsible for the gain in the dual bound, if the variable's 713 * old solution value is outside the current bounds, and the new solution value is equal to the bound 714 * closest to the old solution value 715 */ 716 717 /* find out, which of the current bounds is violated by the old LP solution value */ 718 if( SCIPsetIsLT(set, oldlpsolval, SCIPvarGetLbLocal(var)) ) 719 { 720 newlpsolval = SCIPvarGetLPSol(var); 721 return SCIPsetIsEQ(set, newlpsolval, SCIPvarGetLbLocal(var)); 722 } 723 else if( SCIPsetIsGT(set, oldlpsolval, SCIPvarGetUbLocal(var)) ) 724 { 725 newlpsolval = SCIPvarGetLPSol(var); 726 return SCIPsetIsEQ(set, newlpsolval, SCIPvarGetUbLocal(var)); 727 } 728 else 729 return FALSE; 730 } 731 732 /** pseudo cost flag stored in the variables to mark them for the pseudo cost update */ 733 enum PseudocostFlag 734 { 735 PSEUDOCOST_NONE = 0, /**< variable's bounds were not changed */ 736 PSEUDOCOST_IGNORE = 1, /**< bound changes on variable should be ignored for pseudo cost updates */ 737 PSEUDOCOST_UPDATE = 2 /**< pseudo cost value of variable should be updated */ 738 }; 739 typedef enum PseudocostFlag PSEUDOCOSTFLAG; 740 741 /** updates the variable's pseudo cost values after the node's initial LP was solved */ 742 static 743 SCIP_RETCODE updatePseudocost( 744 SCIP_SET* set, /**< global SCIP settings */ 745 SCIP_STAT* stat, /**< dynamic problem statistics */ 746 SCIP_PROB* prob, /**< transformed problem after presolve */ 747 SCIP_TREE* tree, /**< branch and bound tree */ 748 SCIP_LP* lp, /**< LP data */ 749 SCIP_Bool updateintegers, /**< whether to update pseudo costs for integer variables */ 750 SCIP_Bool updatecontinuous /**< whether to update pseudo costs for continuous variables */ 751 ) 752 { 753 SCIP_NODE* focusnode; 754 int actdepth; 755 756 assert(lp != NULL); 757 assert(tree != NULL); 758 assert(tree->path != NULL); 759 760 focusnode = SCIPtreeGetFocusNode(tree); 761 assert(SCIPnodeIsActive(focusnode)); 762 assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE); 763 actdepth = SCIPnodeGetDepth(focusnode); 764 assert(tree->path[actdepth] == focusnode); 765 766 if( (updateintegers || updatecontinuous) && lp->solved && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && tree->focuslpstatefork != NULL ) 767 { 768 SCIP_BOUNDCHG** updates; 769 SCIP_NODE* node; 770 SCIP_VAR* var; 771 SCIP_Real weight; 772 SCIP_Real lpgain; 773 int nupdates; 774 int nvalidupdates; 775 int d; 776 int i; 777 778 assert(SCIPnodeIsActive(tree->focuslpstatefork)); 779 assert(tree->path[tree->focuslpstatefork->depth] == tree->focuslpstatefork); 780 781 /* get a buffer for the collected bound changes; start with a size twice as large as the number of nodes between 782 * current node and LP fork 783 */ 784 SCIP_CALL( SCIPsetAllocBufferArray(set, &updates, (int)(2*(actdepth - tree->focuslpstatefork->depth))) ); 785 nupdates = 0; 786 nvalidupdates = 0; 787 788 /* search the nodes from LP fork down to current node for bound changes in between; move in this direction, 789 * because the bound changes closer to the LP fork are more likely to have a valid LP solution information 790 * attached; collect the bound changes for pseudo cost value updates and mark the corresponding variables such 791 * that they are not updated twice in case of more than one bound change on the same variable 792 */ 793 for( d = tree->focuslpstatefork->depth+1; d <= actdepth; ++d ) 794 { 795 node = tree->path[d]; 796 797 if( node->domchg != NULL ) 798 { 799 SCIP_BOUNDCHG* boundchgs; 800 int nboundchgs; 801 802 boundchgs = node->domchg->domchgbound.boundchgs; 803 nboundchgs = (int) node->domchg->domchgbound.nboundchgs; 804 for( i = 0; i < nboundchgs; ++i ) 805 { 806 var = boundchgs[i].var; 807 assert(var != NULL); 808 809 /* we even collect redundant bound changes, since they were not redundant in the LP branching decision 810 * and therefore should be regarded in the pseudocost updates 811 * 812 * however, if the variable is continuous and we normalize the pseudo costs by the domain reduction, 813 * then getting the variable bound before the branching is not possible by looking at the variables branching information (since redundant branchings are not applied) 814 * thus, in this case we ignore the boundchange 815 */ 816 if( (SCIP_BOUNDCHGTYPE)boundchgs[i].boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING && 817 (PSEUDOCOSTFLAG)var->pseudocostflag == PSEUDOCOST_NONE 818 ) 819 { 820 /* remember the bound change and mark the variable */ 821 SCIP_CALL( SCIPsetReallocBufferArray(set, &updates, nupdates+1) ); 822 updates[nupdates] = &boundchgs[i]; 823 nupdates++; 824 825 /* check, if the bound change would lead to a valid pseudo cost update 826 * and see comment above (however, ...) */ 827 if( isPseudocostUpdateValid(var, set, boundchgs[i].data.branchingdata.lpsolval, updateintegers, updatecontinuous) && 828 (SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS || !boundchgs[i].redundant || set->branch_lpgainnorm != 'd') 829 ) 830 { 831 var->pseudocostflag = PSEUDOCOST_UPDATE; /*lint !e641*/ 832 nvalidupdates++; 833 } 834 else 835 var->pseudocostflag = PSEUDOCOST_IGNORE; /*lint !e641*/ 836 } 837 } 838 } 839 } 840 841 /* update the pseudo cost values and reset the variables' flags; assume, that the responsibility for the dual gain 842 * is equally spread on all bound changes that lead to valid pseudo cost updates 843 */ 844 assert(SCIPnodeGetType(tree->focuslpstatefork) == SCIP_NODETYPE_FORK); 845 weight = (nvalidupdates > 0 ? 1.0 / (SCIP_Real)nvalidupdates : 1.0); 846 lpgain = (SCIPlpGetObjval(lp, set, prob) - tree->focuslpstatefork->data.fork->lpobjval) * weight; 847 lpgain = MAX(lpgain, 0.0); 848 849 for( i = 0; i < nupdates; ++i ) 850 { 851 assert((SCIP_BOUNDCHGTYPE)updates[i]->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING); 852 853 var = updates[i]->var; 854 assert(var != NULL); 855 assert((PSEUDOCOSTFLAG)var->pseudocostflag != PSEUDOCOST_NONE); 856 857 if( (PSEUDOCOSTFLAG)var->pseudocostflag == PSEUDOCOST_UPDATE ) 858 { 859 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS || set->branch_lpgainnorm == 'l' ) 860 { 861 SCIPsetDebugMsg(set, "updating pseudocosts of <%s>: sol: %g -> %g, LP: %e -> %e => solvaldelta = %g, gain=%g, weight: %g\n", 862 SCIPvarGetName(var), updates[i]->data.branchingdata.lpsolval, SCIPvarGetLPSol(var), 863 tree->focuslpstatefork->data.fork->lpobjval, SCIPlpGetObjval(lp, set, prob), 864 SCIPvarGetLPSol(var) - updates[i]->data.branchingdata.lpsolval, lpgain, weight); 865 SCIP_CALL( SCIPvarUpdatePseudocost(var, set, stat, 866 SCIPvarGetLPSol(var) - updates[i]->data.branchingdata.lpsolval, lpgain, weight) ); 867 } 868 else 869 { 870 /* set->branch_lpgainnorm == 'd': 871 * For continuous variables, we want to pseudocosts to be the average of the gain in the LP value 872 * if the domain is reduced from x% of its original width to y% of its original (e.g., global) width, i.e., 873 * to be the average of LPgain / (oldwidth/origwidth - newwidth/origwidth) = LPgain * origwidth / (oldwidth - newwidth). 874 * Then an expected improvement in the LP value by a reduction of the domain width 875 * from x% to y% of its original width can be computed by pseudocost * (oldwidth - newwidth) / origwidth. 876 * Since the original width cancels out, we can also define the pseudocosts as average of LPgain / (oldwidth - newwidth) 877 * and compute the expected improvement as pseudocost * (oldwidth - newwidth). 878 * 879 * Let var have bounds [a,c] before the branching and assume we branched on some value b. 880 * b is given by updates[i]->newbound. 881 * 882 * If updates[i]->boundtype = upper, then node corresponds to the child [a,b]. 883 * Thus, we have oldwidth = c-a, newwidth = b-a, and oldwidth - newwidth = c-b. 884 * To get c (the previous upper bound), we look into the var->ubchginfos array. 885 * 886 * If updates[i]->boundtype = lower, then node corresponds to the child [b,c]. 887 * Thus, we have oldwidth = c-a, newwidth = c-b, and oldwidth - newwidth = b-a. 888 * To get c (the previous lower bound), we look into the var->lbchginfos array. 889 */ 890 SCIP_BDCHGINFO* bdchginfo; 891 SCIP_Real oldbound; 892 SCIP_Real delta; 893 int j; 894 int nbdchginfos; 895 896 assert(set->branch_lpgainnorm == 'd' || set->branch_lpgainnorm == 's'); 897 898 oldbound = SCIP_INVALID; 899 900 if( set->branch_lpgainnorm == 'd' ) 901 { 902 assert(!updates[i]->redundant); 903 904 if( (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ) 905 { 906 nbdchginfos = SCIPvarGetNBdchgInfosUb(var); 907 908 /* walk backwards through bound change information array to find the bound change corresponding to branching in updates[i] 909 * usually it will be the first one we look at */ 910 for( j = nbdchginfos-1; j >= 0; --j ) 911 { 912 bdchginfo = SCIPvarGetBdchgInfoUb(var, j); 913 914 if( bdchginfo->oldbound > updates[i]->newbound ) 915 { 916 /* first boundchange which upper bound is above the upper bound set by the branching in updates[i] 917 * if bdchginfo->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING, then this should be exactly the bound change that we are looking for 918 * if bdchginfo->boundchgtype != SCIP_BOUNDCHGTYPE_BRANCHING, then this should be because the branching domain change has not been applied to the variable due to redundancy 919 * in this case, i.e., if there was another boundchange coming from somewhere else, I am not sure whether oldbound is an accurate value to compute the old domain size, so we skip the pseudocosts update 920 */ 921 if( (SCIP_BOUNDCHGTYPE)bdchginfo->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING ) 922 { 923 assert(bdchginfo->newbound == updates[i]->newbound); /*lint !e777*/ 924 oldbound = bdchginfo->oldbound; 925 } 926 else 927 assert(updates[i]->redundant); 928 929 break; 930 } 931 } 932 /* if the bound change was redundant (e.g., due to a change in the global bound), then it was not applied, so there exists no corresponding bound change info 933 * if it is not redundant, then we should have found at least one corresponding boundchange */ 934 assert(j >= 0 || updates[i]->redundant); 935 if( oldbound != SCIP_INVALID ) /*lint !e777*/ 936 { 937 assert(!SCIPsetIsInfinity(set, -oldbound)); /* branching on a variable fixed to -infinity does not make sense */ 938 assert(!SCIPsetIsInfinity(set, updates[i]->newbound)); /* branching to infinity does not make sense */ 939 940 /* if the old upper bound is at infinity or the new upper bound is at -infinity, then we say the delta (c-b) is infinity */ 941 if( SCIPsetIsInfinity(set, oldbound) || SCIPsetIsInfinity(set, -updates[i]->newbound) ) 942 delta = SCIP_INVALID; 943 else 944 delta = updates[i]->newbound - oldbound; 945 } 946 else 947 delta = SCIP_INVALID; 948 } 949 else 950 { 951 assert((SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_LOWER); 952 nbdchginfos = SCIPvarGetNBdchgInfosLb(var); 953 954 /* walk backwards through bound change information array to find the bound change corresponding to branching in updates[i] 955 * usually it will be the first one we look at */ 956 for( j = nbdchginfos-1; j >= 0; --j ) 957 { 958 bdchginfo = SCIPvarGetBdchgInfoLb(var, j); 959 960 if( bdchginfo->oldbound < updates[i]->newbound ) 961 { 962 /* first boundchange which lower bound is below the lower bound set by the branching in updates[i] 963 * if bdchginfo->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING, then this should be exactly the bound change that we are looking for 964 * if bdchginfo->boundchgtype != SCIP_BOUNDCHGTYPE_BRANCHING, then this should be because the branching domain change has not been applied to the variable due to redundancy 965 * in this case, i.e., if there was another boundchange coming from somewhere else, I am not sure whether oldbound is an accurate value to compute the old domain size, so we skip the pseudocosts update 966 */ 967 if( (SCIP_BOUNDCHGTYPE)bdchginfo->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING ) 968 { 969 assert(bdchginfo->newbound == updates[i]->newbound); /*lint !e777*/ 970 oldbound = bdchginfo->oldbound; 971 } 972 else 973 assert(updates[i]->redundant); 974 975 break; 976 } 977 } 978 /* if the bound change was redundant (e.g., due to a change in the global bound), then it was not applied, so there exists no corresponding bound change info 979 * if it is not redundant, then we should have found at least one corresponding boundchange */ 980 assert(j >= 0 || updates[i]->redundant); 981 if( oldbound != SCIP_INVALID ) /*lint !e777*/ 982 { 983 assert(!SCIPsetIsInfinity(set, oldbound)); /* branching on a variable fixed to +infinity does not make sense */ 984 assert(!SCIPsetIsInfinity(set, -updates[i]->newbound)); /* branching to infinity does not make sense */ 985 986 /* if the old lower bound is at -infinity or the new lower bound is at +infinity, then we say the delta (b-a) is infinity */ 987 if( SCIPsetIsInfinity(set, -oldbound) || SCIPsetIsInfinity(set, updates[i]->newbound) ) 988 delta = SCIP_INVALID; 989 else 990 delta = updates[i]->newbound - oldbound; 991 } 992 else 993 delta = SCIP_INVALID; 994 } 995 } 996 else 997 { 998 /* set->branch_lpgainnorm == 's': 999 * Here, we divide the LPgain by the reduction in the sibling node. 1000 * 1001 * If updates[i]->boundtype = upper, then node corresponds to the child [a,b]. 1002 * Thus, we have oldwidth = c-a, newwidth = c-b, and oldwidth - newwidth = b-a. 1003 * Conveniently, we just use the current lower bound for a (it may have been tightened, though). 1004 * 1005 * If updates[i]->boundtype = lower, then node corresponds to the child [b,a]. 1006 * Thus, we have oldwidth = c-a, newwidth = b-a, and oldwidth - newwidth = c-b. 1007 * Conveniently, we just use the current upper bound for c (it may have been tightened, though). 1008 */ 1009 if( (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ) 1010 { 1011 assert(!SCIPsetIsInfinity(set, updates[i]->newbound)); /* branching on a variable fixed to +infinity does not make sense */ 1012 assert(!SCIPsetIsInfinity(set, SCIPvarGetLbLocal(var))); /* branching to infinity does not make sense */ 1013 if( SCIPsetIsInfinity(set, -updates[i]->newbound) || SCIPsetIsInfinity(set, -SCIPvarGetLbLocal(var)) ) 1014 delta = SCIP_INVALID; 1015 else 1016 delta = updates[i]->newbound - SCIPvarGetLbLocal(var); 1017 } 1018 else 1019 { 1020 assert((SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_LOWER); 1021 assert(!SCIPsetIsInfinity(set, -updates[i]->newbound)); /* branching on a variable fixed to -infinity does not make sense */ 1022 assert(!SCIPsetIsInfinity(set, -SCIPvarGetUbLocal(var))); /* branching to -infinity does not make sense */ 1023 if( SCIPsetIsInfinity(set, updates[i]->newbound) || SCIPsetIsInfinity(set, SCIPvarGetUbLocal(var)) ) 1024 delta = SCIP_INVALID; 1025 else 1026 delta = -(SCIPvarGetUbLocal(var) - updates[i]->newbound); 1027 } 1028 } 1029 1030 if( delta != SCIP_INVALID ) /*lint !e777*/ 1031 { 1032 SCIPsetDebugMsg(set, "updating pseudocosts of <%s> with strategy %c: domain: [%g,%g] -> [%g,%g], LP: %e -> %e => " 1033 "delta = %g, gain=%g, weight: %g\n", 1034 SCIPvarGetName(var), set->branch_lpgainnorm, 1035 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? SCIPvarGetLbLocal(var) : oldbound, 1036 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? oldbound : SCIPvarGetUbLocal(var), 1037 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? SCIPvarGetLbLocal(var) : updates[i]->newbound, 1038 (SCIP_BOUNDTYPE)updates[i]->boundtype == SCIP_BOUNDTYPE_UPPER ? updates[i]->newbound : SCIPvarGetUbLocal(var), 1039 tree->focuslpstatefork->lowerbound, SCIPlpGetObjval(lp, set, prob), 1040 delta, lpgain, weight); 1041 1042 SCIP_CALL( SCIPvarUpdatePseudocost(var, set, stat, delta, lpgain, weight) ); 1043 } 1044 } 1045 } 1046 var->pseudocostflag = PSEUDOCOST_NONE; /*lint !e641*/ 1047 } 1048 1049 /* free the buffer for the collected bound changes */ 1050 SCIPsetFreeBufferArray(set, &updates); 1051 } 1052 1053 return SCIP_OKAY; 1054 } 1055 1056 /** updates the estimated value of a primal feasible solution for the focus node after the LP was solved */ 1057 static 1058 SCIP_RETCODE updateEstimate( 1059 SCIP_SET* set, /**< global SCIP settings */ 1060 SCIP_STAT* stat, /**< problem statistics */ 1061 SCIP_TREE* tree, /**< branch and bound tree */ 1062 SCIP_LP* lp, /**< current LP data */ 1063 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 1064 ) 1065 { 1066 SCIP_NODE* focusnode; 1067 SCIP_VAR** lpcands; 1068 SCIP_Real* lpcandsfrac; 1069 SCIP_Real estimate; 1070 int nlpcands; 1071 int i; 1072 1073 /* estimate is only available if LP was solved to optimality */ 1074 if( !SCIPtreeHasFocusNodeLP(tree) || SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL || !SCIPlpIsRelax(lp) ) 1075 return SCIP_OKAY; 1076 1077 focusnode = SCIPtreeGetFocusNode(tree); 1078 assert(focusnode != NULL); 1079 1080 /* get the fractional variables */ 1081 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, &lpcands, NULL, &lpcandsfrac, &nlpcands, NULL, NULL) ); 1082 1083 /* calculate the estimate: lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) */ 1084 estimate = SCIPnodeGetLowerbound(focusnode); 1085 1086 /* an infinite lower bound implies an infinite estimate */ 1087 if( SCIPsetIsInfinity(set, estimate) ) 1088 { 1089 SCIPnodeSetEstimate(focusnode, set, estimate); 1090 return SCIP_OKAY; 1091 } 1092 1093 for( i = 0; i < nlpcands; ++i ) 1094 { 1095 SCIP_Real pscdown; 1096 SCIP_Real pscup; 1097 1098 pscdown = SCIPvarGetPseudocost(lpcands[i], stat, 0.0-lpcandsfrac[i]); 1099 pscup = SCIPvarGetPseudocost(lpcands[i], stat, 1.0-lpcandsfrac[i]); 1100 estimate += MIN(pscdown, pscup); 1101 } 1102 SCIPnodeSetEstimate(focusnode, set, estimate); 1103 1104 return SCIP_OKAY; 1105 } 1106 1107 /** puts all constraints with initial flag TRUE into the LP */ 1108 SCIP_RETCODE SCIPinitConssLP( 1109 BMS_BLKMEM* blkmem, /**< block memory buffers */ 1110 SCIP_SET* set, /**< global SCIP settings */ 1111 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1112 SCIP_CUTPOOL* cutpool, /**< global cutpool */ 1113 SCIP_STAT* stat, /**< dynamic problem statistics */ 1114 SCIP_PROB* transprob, /**< transformed problem */ 1115 SCIP_PROB* origprob, /**< original problem */ 1116 SCIP_TREE* tree, /**< branch and bound tree */ 1117 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1118 SCIP_LP* lp, /**< LP data */ 1119 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 1120 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1121 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 1122 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 1123 SCIP_Bool root, /**< is this the initial root LP? */ 1124 SCIP_Bool firstsubtreeinit, /**< is this the first call in the current subtree after jumping through the tree? */ 1125 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 1126 ) 1127 { 1128 int h; 1129 1130 assert(set != NULL); 1131 assert(lp != NULL); 1132 assert(cutoff != NULL); 1133 1134 *cutoff = FALSE; 1135 1136 /* inform separation storage, that LP is now filled with initial data */ 1137 SCIPsepastoreStartInitialLP(sepastore); 1138 1139 /* add LP relaxations of all initial constraints to LP */ 1140 SCIPsetDebugMsg(set, "init LP: initial rows\n"); 1141 for( h = 0; h < set->nconshdlrs && !(*cutoff); ++h ) 1142 { 1143 SCIP_CALL( SCIPconshdlrInitLP(set->conshdlrs[h], blkmem, set, stat, tree, firstsubtreeinit, cutoff) ); 1144 } 1145 1146 if( set->reopt_enable && set->reopt_usecuts && firstsubtreeinit && !(*cutoff) ) 1147 { 1148 /* add stored cuts from last reoptimization run */ 1149 SCIP_CALL( SCIPreoptApplyCuts(reopt, tree->focusnode, sepastore, cutpool, blkmem, set, stat, eventqueue, 1150 eventfilter, lp, root) ); 1151 } 1152 1153 if( !(*cutoff) ) 1154 { 1155 /* apply cuts */ 1156 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, 1157 eventqueue, eventfilter, cliquetable, root, SCIP_EFFICIACYCHOICE_LP, cutoff) ); 1158 } 1159 else 1160 { 1161 /* the current node will be cut off; we clear the sepastore */ 1162 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) ); 1163 } 1164 1165 /* inform separation storage, that initial LP setup is now finished */ 1166 SCIPsepastoreEndInitialLP(sepastore); 1167 1168 return SCIP_OKAY; 1169 } 1170 1171 /** constructs the initial LP of the current node */ 1172 static 1173 SCIP_RETCODE initLP( 1174 BMS_BLKMEM* blkmem, /**< block memory buffers */ 1175 SCIP_SET* set, /**< global SCIP settings */ 1176 SCIP_STAT* stat, /**< dynamic problem statistics */ 1177 SCIP_PROB* transprob, /**< transformed problem */ 1178 SCIP_PROB* origprob, /**< original problem */ 1179 SCIP_TREE* tree, /**< branch and bound tree */ 1180 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1181 SCIP_LP* lp, /**< LP data */ 1182 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 1183 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1184 SCIP_CUTPOOL* cutpool, /**< global cut pool */ 1185 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 1186 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1187 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 1188 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 1189 SCIP_Bool root, /**< is this the initial root LP? */ 1190 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 1191 ) 1192 { 1193 SCIP_VAR* var; 1194 int oldnvars = 0; 1195 int v; 1196 1197 assert(set != NULL); 1198 assert(transprob != NULL); 1199 assert(lp != NULL); 1200 assert(cutoff != NULL); 1201 1202 *cutoff = FALSE; 1203 1204 /* at the root node, we have to add the initial variables as columns */ 1205 if( root ) 1206 { 1207 assert(SCIPlpGetNCols(lp) == 0); 1208 assert(SCIPlpGetNRows(lp) == 0); 1209 assert(lp->nremovablecols == 0); 1210 assert(lp->nremovablerows == 0); 1211 1212 /* store number of variables for later */ 1213 oldnvars = transprob->nvars; 1214 1215 /* inform pricing storage, that LP is now filled with initial data */ 1216 SCIPpricestoreStartInitialLP(pricestore); 1217 1218 /* add all initial variables to LP */ 1219 SCIPsetDebugMsg(set, "init LP: initial columns\n"); 1220 for( v = 0; v < transprob->nvars && !(*cutoff); ++v ) 1221 { 1222 var = transprob->vars[v]; 1223 assert(SCIPvarGetProbindex(var) >= 0); 1224 1225 if( SCIPvarIsInitial(var) ) 1226 { 1227 SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, 0.0, TRUE) ); 1228 } 1229 1230 /* check for empty domains (necessary if no presolving was performed) */ 1231 if( SCIPsetIsGT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ) 1232 *cutoff = TRUE; 1233 } 1234 assert(lp->nremovablecols == 0); 1235 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) ); 1236 1237 /* inform pricing storage, that initial LP setup is now finished */ 1238 SCIPpricestoreEndInitialLP(pricestore); 1239 } 1240 1241 if( *cutoff ) 1242 return SCIP_OKAY; 1243 1244 /* put all initial constraints into the LP */ 1245 /* @todo check whether we jumped through the tree */ 1246 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, 1247 eventfilter, cliquetable, root, TRUE, cutoff) ); 1248 1249 /* putting all initial constraints into the LP might have added new variables */ 1250 if( root && !(*cutoff) && transprob->nvars > oldnvars ) 1251 { 1252 /* inform pricing storage, that LP is now filled with initial data */ 1253 SCIPpricestoreStartInitialLP(pricestore); 1254 1255 /* check all initial variables */ 1256 for( v = 0; v < transprob->nvars && !(*cutoff); ++v ) 1257 { 1258 var = transprob->vars[v]; 1259 assert(SCIPvarGetProbindex(var) >= 0); 1260 1261 if( SCIPvarIsInitial(var) && (SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN || !SCIPcolIsInLP(SCIPvarGetCol(var))) ) 1262 { 1263 SCIP_CALL( SCIPpricestoreAddVar(pricestore, blkmem, set, eventqueue, lp, var, 0.0, TRUE) ); 1264 } 1265 1266 /* check for empty domains (necessary if no presolving was performed) */ 1267 if( SCIPsetIsGT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ) 1268 *cutoff = TRUE; 1269 } 1270 assert(lp->nremovablecols == 0); 1271 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) ); 1272 1273 /* inform pricing storage, that initial LP setup is now finished */ 1274 SCIPpricestoreEndInitialLP(pricestore); 1275 } 1276 1277 return SCIP_OKAY; 1278 } 1279 1280 /** constructs the LP of the current node, but does not load the LP state and warmstart information */ 1281 SCIP_RETCODE SCIPconstructCurrentLP( 1282 BMS_BLKMEM* blkmem, /**< block memory buffers */ 1283 SCIP_SET* set, /**< global SCIP settings */ 1284 SCIP_STAT* stat, /**< dynamic problem statistics */ 1285 SCIP_PROB* transprob, /**< transformed problem */ 1286 SCIP_PROB* origprob, /**< original problem */ 1287 SCIP_TREE* tree, /**< branch and bound tree */ 1288 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1289 SCIP_LP* lp, /**< LP data */ 1290 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 1291 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1292 SCIP_CUTPOOL* cutpool, /**< global cutpool */ 1293 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 1294 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1295 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 1296 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 1297 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */ 1298 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 1299 ) 1300 { 1301 SCIP_Bool initroot = FALSE; 1302 1303 assert(tree != NULL); 1304 assert(cutoff != NULL); 1305 1306 *cutoff = FALSE; 1307 1308 if( !SCIPtreeIsFocusNodeLPConstructed(tree) ) 1309 { 1310 /* inform separation storage, that LP is now filled with initial data */ 1311 SCIPsepastoreStartInitialLP(sepastore); 1312 1313 if( tree->correctlpdepth >= 0 ) 1314 { 1315 int i; 1316 1317 for( i = tree->pathnlprows[tree->correctlpdepth]; i < lp->nrows; ++i ) 1318 { 1319 /* keep all active global cuts that where applied in the previous node in the lp */ 1320 if( !lp->rows[i]->local && lp->rows[i]->age == 0 ) 1321 { 1322 lp->rows[i]->fromcutpool = TRUE; /* this has no effect inside initial LP, but is set for consistency */ 1323 SCIP_CALL( SCIPsepastoreAddCut(sepastore, blkmem, set, stat, eventqueue, eventfilter, lp, lp->rows[i], 1324 TRUE, (SCIPtreeGetCurrentDepth(tree) == 0), cutoff) ); 1325 } 1326 } 1327 } 1328 1329 if( !(*cutoff) ) 1330 { 1331 /* load the LP into the solver and load the LP state */ 1332 SCIPsetDebugMsg(set, "loading LP\n"); 1333 SCIP_CALL( SCIPtreeLoadLP(tree, blkmem, set, eventqueue, eventfilter, lp, &initroot) ); 1334 assert(initroot || SCIPnodeGetDepth(SCIPtreeGetFocusNode(tree)) > 0); 1335 assert(SCIPtreeIsFocusNodeLPConstructed(tree)); 1336 1337 /* apply cuts */ 1338 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, 1339 eventqueue, eventfilter, cliquetable, (SCIPtreeGetCurrentDepth(tree) == 0), SCIP_EFFICIACYCHOICE_LP, cutoff) ); 1340 } 1341 else 1342 { 1343 /* the current node will be cut off; we clear the sepastore */ 1344 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) ); 1345 } 1346 1347 /* inform separation storage, that initial LP setup is now finished */ 1348 SCIPsepastoreEndInitialLP(sepastore); 1349 1350 if( !(*cutoff) ) 1351 { 1352 /* setup initial LP relaxation of node */ 1353 SCIP_CALL( initLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, pricestore, sepastore, cutpool, branchcand, 1354 eventqueue, eventfilter, cliquetable, initroot, cutoff) ); 1355 } 1356 } 1357 else if( newinitconss ) 1358 { 1359 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, 1360 origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, 1361 cutoff) ); 1362 } 1363 1364 return SCIP_OKAY; 1365 } 1366 1367 /** updates the primal ray stored in primal data 1368 * clears previously stored primal ray, if existing and there was no LP error 1369 * stores current primal ray, if LP is unbounded and there has been no error 1370 */ 1371 static 1372 SCIP_RETCODE updatePrimalRay( 1373 BMS_BLKMEM* blkmem, /**< block memory buffers */ 1374 SCIP_SET* set, /**< global SCIP settings */ 1375 SCIP_STAT* stat, /**< dynamic problem statistics */ 1376 SCIP_PROB* prob, /**< transformed problem after presolve */ 1377 SCIP_PRIMAL* primal, /**< primal data */ 1378 SCIP_TREE* tree, /**< branch and bound tree */ 1379 SCIP_LP* lp, /**< LP data */ 1380 SCIP_Bool lperror /**< has there been an LP error? */ 1381 ) 1382 { 1383 assert(blkmem != NULL); 1384 assert(set != NULL); 1385 assert(stat != NULL); 1386 assert(prob != NULL); 1387 assert(primal != NULL); 1388 assert(tree != NULL); 1389 assert(lp != NULL); 1390 1391 if( lperror ) 1392 return SCIP_OKAY; 1393 1394 /* clear previously stored primal ray, if any */ 1395 if( primal->primalray != NULL ) 1396 { 1397 SCIP_CALL( SCIPsolFree(&primal->primalray, blkmem, primal) ); 1398 } 1399 1400 /* store unbounded ray, if LP is unbounded */ 1401 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 1402 { 1403 SCIP_VAR** vars; 1404 SCIP_Real* ray; 1405 int nvars; 1406 int i; 1407 1408 SCIPsetDebugMsg(set, "LP is unbounded, store primal ray\n"); 1409 1410 vars = prob->vars; 1411 nvars = prob->nvars; 1412 1413 /* get buffer memory for storing the ray and load the ray values into it */ 1414 SCIP_CALL( SCIPsetAllocBufferArray(set, &ray, nvars) ); 1415 BMSclearMemoryArray(ray, nvars); 1416 SCIP_CALL( SCIPlpGetPrimalRay(lp, set, ray) ); 1417 1418 /* create solution to store the primal ray in */ 1419 assert(primal->primalray == NULL); 1420 SCIP_CALL( SCIPsolCreate(&primal->primalray, blkmem, set, stat, primal, tree, NULL) ); 1421 1422 /* set values of all active variable in the solution that represents the primal ray */ 1423 for( i = 0; i < nvars; i++ ) 1424 { 1425 SCIP_CALL( SCIPsolSetVal(primal->primalray, set, stat, tree, vars[i], ray[i]) ); 1426 } 1427 1428 SCIPdebug( SCIP_CALL( SCIPprintRay(set->scip, primal->primalray, NULL, FALSE) ) ); 1429 1430 /* free memory for buffering the ray values */ 1431 SCIPsetFreeBufferArray(set, &ray); 1432 } 1433 1434 return SCIP_OKAY; 1435 } 1436 1437 /** load and solve the initial LP of a node */ 1438 static 1439 SCIP_RETCODE solveNodeInitialLP( 1440 BMS_BLKMEM* blkmem, /**< block memory buffers */ 1441 SCIP_SET* set, /**< global SCIP settings */ 1442 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1443 SCIP_STAT* stat, /**< dynamic problem statistics */ 1444 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1445 SCIP_PROB* origprob, /**< original problem */ 1446 SCIP_PRIMAL* primal, /**< primal data */ 1447 SCIP_TREE* tree, /**< branch and bound tree */ 1448 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1449 SCIP_LP* lp, /**< LP data */ 1450 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 1451 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1452 SCIP_CUTPOOL* cutpool, /**< global cutpool */ 1453 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 1454 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 1455 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1456 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 1457 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */ 1458 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */ 1459 SCIP_Bool* lperror /**< pointer to store whether an unresolved error in LP solving occured */ 1460 ) 1461 { 1462 /* initializing variables for compiler warnings, which are not correct */ 1463 SCIP_Real starttime = 0.0; 1464 SCIP_Longint nlpiterations = 0; 1465 SCIP_NODE* focusnode; 1466 1467 assert(stat != NULL); 1468 assert(tree != NULL); 1469 assert(lp != NULL); 1470 assert(cutoff != NULL); 1471 assert(lperror != NULL); 1472 assert(SCIPtreeGetFocusNode(tree) != NULL); 1473 assert(SCIPnodeGetType(SCIPtreeGetFocusNode(tree)) == SCIP_NODETYPE_FOCUSNODE); 1474 1475 *cutoff = FALSE; 1476 *lperror = FALSE; 1477 1478 /* load the LP into the solver */ 1479 SCIP_CALL( SCIPconstructCurrentLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, pricestore, sepastore, cutpool, 1480 branchcand, eventqueue, eventfilter, cliquetable, newinitconss, cutoff) ); 1481 1482 if( *cutoff ) 1483 return SCIP_OKAY; 1484 1485 /* load the LP state */ 1486 SCIP_CALL( SCIPtreeLoadLPState(tree, blkmem, set, transprob, stat, eventqueue, lp) ); 1487 1488 focusnode = SCIPtreeGetFocusNode(tree); 1489 1490 /* store current LP iteration count and solving time if we are at the root node */ 1491 if( focusnode->depth == 0 ) 1492 { 1493 nlpiterations = stat->nlpiterations; 1494 starttime = SCIPclockGetTime(stat->solvingtime); 1495 } 1496 1497 /* solve initial LP */ 1498 SCIPsetDebugMsg(set, "node: solve initial LP\n"); 1499 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, 1500 SCIPnodeGetDepth(SCIPtreeGetFocusNode(tree)) == 0 ? set->lp_rootiterlim : set->lp_iterlim, TRUE, TRUE, FALSE, lperror) ); 1501 assert(lp->flushed); 1502 assert(lp->solved || *lperror); 1503 1504 /* save time for very first LP in root node */ 1505 if ( stat->nnodelps == 0 && focusnode->depth == 0 ) 1506 { 1507 stat->firstlptime = SCIPclockGetTime(stat->solvingtime) - starttime; 1508 } 1509 1510 /* remove previous primal ray, store new one if LP is unbounded */ 1511 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) ); 1512 1513 if( !(*lperror) ) 1514 { 1515 /* cppcheck-suppress unassignedVariable */ 1516 SCIP_EVENT event; 1517 1518 if( SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_ITERLIMIT && SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_TIMELIMIT ) 1519 { 1520 /* issue FIRSTLPSOLVED event */ 1521 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_FIRSTLPSOLVED) ); 1522 SCIP_CALL( SCIPeventChgNode(&event, SCIPtreeGetFocusNode(tree)) ); 1523 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) ); 1524 } 1525 1526 /* update pseudo cost values for integer variables (always) and for continuous variables (if not delayed) */ 1527 SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, TRUE, !set->branch_delaypscost) ); 1528 1529 /* update lower bound of current node w.r.t. initial lp */ 1530 assert(!(*cutoff)); 1531 if( (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY 1532 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT) 1533 && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) ) 1534 { 1535 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) ); 1536 1537 /* if this is the first LP solved at the root, store its iteration count and solution value */ 1538 if( stat->nnodelps == 0 && focusnode->depth == 0 ) 1539 { 1540 SCIP_Real lowerbound; 1541 1542 assert(stat->nrootfirstlpiterations == 0); 1543 stat->nrootfirstlpiterations = stat->nlpiterations - nlpiterations; 1544 1545 if( set->misc_exactsolve ) 1546 { 1547 SCIP_CALL( SCIPlpGetProvedLowerbound(lp, set, &lowerbound) ); 1548 } 1549 else 1550 lowerbound = SCIPlpGetObjval(lp, set, transprob); 1551 1552 stat->firstlpdualbound = SCIPprobExternObjval(transprob, origprob, set, lowerbound); 1553 } 1554 } 1555 } 1556 1557 return SCIP_OKAY; 1558 } 1559 1560 /** makes sure the LP is flushed and solved */ 1561 static 1562 SCIP_RETCODE separationRoundResolveLP( 1563 BMS_BLKMEM* blkmem, /**< block memory buffers */ 1564 SCIP_SET* set, /**< global SCIP settings */ 1565 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1566 SCIP_STAT* stat, /**< dynamic problem statistics */ 1567 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1568 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 1569 SCIP_PROB* prob, /**< transformed problem after presolve */ 1570 SCIP_PRIMAL* primal, /**< primal data */ 1571 SCIP_TREE* tree, /**< branch and bound tree */ 1572 SCIP_LP* lp, /**< LP data */ 1573 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */ 1574 SCIP_Bool* mustsepa, /**< pointer to store TRUE if additional separation rounds should be performed */ 1575 SCIP_Bool* mustprice /**< pointer to store TRUE if additional pricing rounds should be performed */ 1576 ) 1577 { 1578 assert(lp != NULL); 1579 assert(lperror != NULL); 1580 assert(mustsepa != NULL); 1581 assert(mustprice != NULL); 1582 1583 /* if bound changes were applied in the separation round, we have to resolve the LP */ 1584 if( !lp->flushed ) 1585 { 1586 /* solve LP (with dual simplex) */ 1587 SCIPsetDebugMsg(set, "separation: resolve LP\n"); 1588 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, prob, set->lp_iterlim, FALSE, TRUE, FALSE, lperror) ); 1589 assert(lp->flushed); 1590 assert(lp->solved || *lperror); 1591 *mustsepa = TRUE; 1592 *mustprice = TRUE; 1593 1594 /* remove previous primal ray, store new one if LP is unbounded */ 1595 SCIP_CALL( updatePrimalRay(blkmem, set, stat, prob, primal, tree, lp, *lperror) ); 1596 } 1597 1598 return SCIP_OKAY; 1599 } 1600 1601 /** applies one round of LP separation */ 1602 static 1603 SCIP_RETCODE separationRoundLP( 1604 BMS_BLKMEM* blkmem, /**< block memory buffers */ 1605 SCIP_SET* set, /**< global SCIP settings */ 1606 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1607 SCIP_STAT* stat, /**< dynamic problem statistics */ 1608 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1609 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 1610 SCIP_PROB* prob, /**< transformed problem after presolve */ 1611 SCIP_PRIMAL* primal, /**< primal data */ 1612 SCIP_TREE* tree, /**< branch and bound tree */ 1613 SCIP_LP* lp, /**< LP data */ 1614 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1615 int actdepth, /**< current depth in the tree */ 1616 SCIP_Real bounddist, /**< current relative distance of local dual bound to global dual bound */ 1617 SCIP_Bool allowlocal, /**< should the separators be asked to separate local cuts */ 1618 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */ 1619 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */ 1620 SCIP_Bool* enoughcuts, /**< pointer to store whether enough cuts have been found this round */ 1621 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */ 1622 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */ 1623 SCIP_Bool* mustsepa, /**< pointer to store TRUE if additional separation rounds should be performed */ 1624 SCIP_Bool* mustprice /**< pointer to store TRUE if additional pricing rounds should be performed */ 1625 ) 1626 { 1627 SCIP_RESULT result; 1628 int i; 1629 SCIP_Bool consadded; 1630 SCIP_Bool root; 1631 1632 assert(set != NULL); 1633 assert(lp != NULL); 1634 assert(set->conshdlrs_sepa != NULL); 1635 assert(delayed != NULL); 1636 assert(enoughcuts != NULL); 1637 assert(cutoff != NULL); 1638 assert(lperror != NULL); 1639 1640 root = (actdepth == 0); 1641 *delayed = FALSE; 1642 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 1643 *enoughcuts = TRUE; 1644 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 1645 *enoughcuts = FALSE; 1646 else 1647 *enoughcuts = (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 1648 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))); 1649 *lperror = FALSE; 1650 consadded = FALSE; 1651 1652 SCIPsetDebugMsg(set, "calling separators on LP solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed); 1653 1654 /* sort separators by priority */ 1655 SCIPsetSortSepas(set); 1656 1657 /* call LP separators with nonnegative priority */ 1658 for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved 1659 && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 1660 ++i ) 1661 { 1662 #ifndef NDEBUG 1663 size_t nusedbuffer = BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)); 1664 #endif 1665 1666 if( SCIPsepaGetPriority(set->sepas[i]) < 0 ) 1667 continue; 1668 1669 if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) ) 1670 continue; 1671 1672 SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n", 1673 SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i])); 1674 SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) ); 1675 #ifndef NDEBUG 1676 if( BMSgetNUsedBufferMemory(SCIPbuffer(set->scip)) > nusedbuffer ) 1677 { 1678 SCIPerrorMessage("Buffer not completely freed after executing separator <%s>\n", SCIPsepaGetName(set->sepas[i])); 1679 SCIPABORT(); 1680 } 1681 #endif 1682 *cutoff = *cutoff || (result == SCIP_CUTOFF); 1683 consadded = consadded || (result == SCIP_CONSADDED); 1684 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 1685 *enoughcuts = TRUE; 1686 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 1687 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND); 1688 else 1689 { 1690 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 1691 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))) 1692 || (result == SCIP_NEWROUND); 1693 } 1694 *delayed = *delayed || (result == SCIP_DELAYED); 1695 1696 if( !(*cutoff) ) 1697 { 1698 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */ 1699 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) ); 1700 } 1701 else 1702 { 1703 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i])); 1704 } 1705 1706 /* if we work off the delayed separators, we stop immediately if a cut was found */ 1707 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) ) 1708 { 1709 SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i])); 1710 *delayed = TRUE; 1711 return SCIP_OKAY; 1712 } 1713 } 1714 1715 /* try separating constraints of the constraint handlers */ 1716 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved 1717 && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 1718 ++i ) 1719 { 1720 if( onlydelayed && !SCIPconshdlrWasLPSeparationDelayed(set->conshdlrs_sepa[i]) ) 1721 continue; 1722 1723 SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n", 1724 SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i])); 1725 SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed, 1726 &result) ); 1727 1728 *cutoff = *cutoff || (result == SCIP_CUTOFF); 1729 consadded = consadded || (result == SCIP_CONSADDED); 1730 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 1731 *enoughcuts = TRUE; 1732 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 1733 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND); 1734 else 1735 { 1736 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 1737 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))) 1738 || (result == SCIP_NEWROUND); 1739 } 1740 *delayed = *delayed || (result == SCIP_DELAYED); 1741 1742 if( !(*cutoff) ) 1743 { 1744 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */ 1745 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) ); 1746 } 1747 else 1748 { 1749 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[i])); 1750 } 1751 1752 /* if we work off the delayed separators, we stop immediately if a cut was found */ 1753 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) ) 1754 { 1755 SCIPsetDebugMsg(set, " -> delayed constraint handler <%s> found a cut\n", 1756 SCIPconshdlrGetName(set->conshdlrs_sepa[i])); 1757 *delayed = TRUE; 1758 return SCIP_OKAY; 1759 } 1760 } 1761 1762 /* call LP separators with negative priority */ 1763 for( i = 0; i < set->nsepas && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved 1764 && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 1765 ++i ) 1766 { 1767 if( SCIPsepaGetPriority(set->sepas[i]) >= 0 ) 1768 continue; 1769 1770 if( onlydelayed && !SCIPsepaWasLPDelayed(set->sepas[i]) ) 1771 continue; 1772 1773 SCIPsetDebugMsg(set, " -> executing separator <%s> with priority %d\n", 1774 SCIPsepaGetName(set->sepas[i]), SCIPsepaGetPriority(set->sepas[i])); 1775 SCIP_CALL( SCIPsepaExecLP(set->sepas[i], set, stat, sepastore, actdepth, bounddist, allowlocal, onlydelayed, &result) ); 1776 1777 *cutoff = *cutoff || (result == SCIP_CUTOFF); 1778 consadded = consadded || (result == SCIP_CONSADDED); 1779 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 1780 *enoughcuts = TRUE; 1781 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 1782 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND); 1783 else 1784 { 1785 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 1786 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))) 1787 || (result == SCIP_NEWROUND); 1788 } 1789 *delayed = *delayed || (result == SCIP_DELAYED); 1790 1791 if( !(*cutoff) ) 1792 { 1793 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */ 1794 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) ); 1795 } 1796 else 1797 { 1798 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i])); 1799 } 1800 1801 /* if we work off the delayed separators, we stop immediately if a cut was found */ 1802 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) ) 1803 { 1804 SCIPsetDebugMsg(set, " -> delayed separator <%s> found a cut\n", SCIPsepaGetName(set->sepas[i])); 1805 *delayed = TRUE; 1806 return SCIP_OKAY; 1807 } 1808 } 1809 1810 /* process the constraints that were added during this separation round */ 1811 while( consadded ) 1812 { 1813 assert(!onlydelayed); 1814 consadded = FALSE; 1815 1816 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*lperror) && !(*enoughcuts) && lp->flushed && lp->solved 1817 && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 1818 ++i ) 1819 { 1820 SCIPsetDebugMsg(set, " -> executing separation of constraint handler <%s> with priority %d\n", 1821 SCIPconshdlrGetName(set->conshdlrs_sepa[i]), SCIPconshdlrGetSepaPriority(set->conshdlrs_sepa[i])); 1822 SCIP_CALL( SCIPconshdlrSeparateLP(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, actdepth, onlydelayed, 1823 &result) ); 1824 1825 *cutoff = *cutoff || (result == SCIP_CUTOFF); 1826 consadded = consadded || (result == SCIP_CONSADDED); 1827 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 1828 *enoughcuts = TRUE; 1829 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 1830 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND); 1831 else 1832 { 1833 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 1834 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))) 1835 || (result == SCIP_NEWROUND); 1836 } 1837 *delayed = *delayed || (result == SCIP_DELAYED); 1838 1839 if( !(*cutoff) ) 1840 { 1841 /* make sure the LP is solved (after adding bound changes, LP has to be flushed and resolved) */ 1842 SCIP_CALL( separationRoundResolveLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, lperror, mustsepa, mustprice) ); 1843 } 1844 else 1845 { 1846 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", SCIPconshdlrGetName(set->conshdlrs_sepa[i])); 1847 } 1848 } 1849 } 1850 1851 SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, lpflushed=%u, cutoff=%u\n", 1852 *delayed, *enoughcuts, lp->flushed, *cutoff); 1853 1854 return SCIP_OKAY; 1855 } 1856 1857 /** applies one round of separation on the given primal solution */ 1858 static 1859 SCIP_RETCODE separationRoundSol( 1860 BMS_BLKMEM* blkmem, /**< block memory buffers */ 1861 SCIP_SET* set, /**< global SCIP settings */ 1862 SCIP_STAT* stat, /**< dynamic problem statistics */ 1863 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1864 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */ 1865 int actdepth, /**< current depth in the tree */ 1866 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */ 1867 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */ 1868 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */ 1869 SCIP_Bool* enoughcuts, /**< pointer to store whether enough cuts have been found this round */ 1870 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 1871 ) 1872 { 1873 SCIP_RESULT result; 1874 int i; 1875 SCIP_Bool consadded; 1876 SCIP_Bool root; 1877 1878 assert(set != NULL); 1879 assert(set->conshdlrs_sepa != NULL); 1880 assert(delayed != NULL); 1881 assert(enoughcuts != NULL); 1882 assert(cutoff != NULL); 1883 1884 *delayed = FALSE; 1885 *enoughcuts = FALSE; 1886 consadded = FALSE; 1887 root = (actdepth == 0); 1888 1889 SCIPsetDebugMsg(set, "calling separators on primal solution in depth %d (onlydelayed: %u)\n", actdepth, onlydelayed); 1890 1891 /* sort separators by priority */ 1892 SCIPsetSortSepas(set); 1893 1894 /* call separators with nonnegative priority */ 1895 for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i ) 1896 { 1897 if( SCIPsepaGetPriority(set->sepas[i]) < 0 ) 1898 continue; 1899 1900 if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) ) 1901 continue; 1902 1903 SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) ); 1904 *cutoff = *cutoff || (result == SCIP_CUTOFF); 1905 consadded = consadded || (result == SCIP_CONSADDED); 1906 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 1907 *enoughcuts = TRUE; 1908 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 1909 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND); 1910 else 1911 { 1912 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 1913 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))) 1914 || (result == SCIP_NEWROUND); 1915 } 1916 *delayed = *delayed || (result == SCIP_DELAYED); 1917 if( *cutoff ) 1918 { 1919 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i])); 1920 } 1921 1922 /* if we work off the delayed separators, we stop immediately if a cut was found */ 1923 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) ) 1924 { 1925 *delayed = TRUE; 1926 return SCIP_OKAY; 1927 } 1928 } 1929 1930 /* try separating constraints of the constraint handlers */ 1931 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i ) 1932 { 1933 if( onlydelayed && !SCIPconshdlrWasSolSeparationDelayed(set->conshdlrs_sepa[i]) ) 1934 continue; 1935 1936 SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed, 1937 &result) ); 1938 *cutoff = *cutoff || (result == SCIP_CUTOFF); 1939 consadded = consadded || (result == SCIP_CONSADDED); 1940 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 1941 *enoughcuts = TRUE; 1942 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 1943 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND); 1944 else 1945 { 1946 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 1947 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))) 1948 || (result == SCIP_NEWROUND); 1949 } 1950 *delayed = *delayed || (result == SCIP_DELAYED); 1951 if( *cutoff ) 1952 { 1953 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", 1954 SCIPconshdlrGetName(set->conshdlrs_sepa[i])); 1955 } 1956 1957 /* if we work off the delayed separators, we stop immediately if a cut was found */ 1958 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) ) 1959 { 1960 *delayed = TRUE; 1961 return SCIP_OKAY; 1962 } 1963 } 1964 1965 /* call separators with negative priority */ 1966 for( i = 0; i < set->nsepas && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i ) 1967 { 1968 if( SCIPsepaGetPriority(set->sepas[i]) >= 0 ) 1969 continue; 1970 1971 if( onlydelayed && !SCIPsepaWasSolDelayed(set->sepas[i]) ) 1972 continue; 1973 1974 SCIP_CALL( SCIPsepaExecSol(set->sepas[i], set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, &result) ); 1975 *cutoff = *cutoff || (result == SCIP_CUTOFF); 1976 consadded = consadded || (result == SCIP_CONSADDED); 1977 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 1978 *enoughcuts = TRUE; 1979 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 1980 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND); 1981 else 1982 { 1983 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 1984 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))) 1985 || (result == SCIP_NEWROUND); 1986 } 1987 *delayed = *delayed || (result == SCIP_DELAYED); 1988 if( *cutoff ) 1989 { 1990 SCIPsetDebugMsg(set, " -> separator <%s> detected cutoff\n", SCIPsepaGetName(set->sepas[i])); 1991 } 1992 1993 /* if we work off the delayed separators, we stop immediately if a cut was found */ 1994 if( onlydelayed && (result == SCIP_CONSADDED || result == SCIP_REDUCEDDOM || result == SCIP_SEPARATED || result == SCIP_NEWROUND) ) 1995 { 1996 *delayed = TRUE; 1997 return SCIP_OKAY; 1998 } 1999 } 2000 2001 /* process the constraints that were added during this separation round */ 2002 while( consadded ) 2003 { 2004 assert(!onlydelayed); 2005 consadded = FALSE; 2006 2007 for( i = 0; i < set->nconshdlrs && !(*cutoff) && !(*enoughcuts) && !SCIPsolveIsStopped(set, stat, FALSE); ++i ) 2008 { 2009 SCIP_CALL( SCIPconshdlrSeparateSol(set->conshdlrs_sepa[i], blkmem, set, stat, sepastore, sol, actdepth, onlydelayed, &result) ); 2010 *cutoff = *cutoff || (result == SCIP_CUTOFF); 2011 consadded = consadded || (result == SCIP_CONSADDED); 2012 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 2013 *enoughcuts = TRUE; 2014 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 2015 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND); 2016 else 2017 { 2018 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 2019 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))) 2020 || (result == SCIP_NEWROUND); 2021 } 2022 *delayed = *delayed || (result == SCIP_DELAYED); 2023 if( *cutoff ) 2024 { 2025 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in separation\n", 2026 SCIPconshdlrGetName(set->conshdlrs_sepa[i])); 2027 } 2028 } 2029 } 2030 2031 SCIPsetDebugMsg(set, " -> separation round finished: delayed=%u, enoughcuts=%u, cutoff=%u\n", 2032 *delayed, *enoughcuts, *cutoff); 2033 2034 return SCIP_OKAY; 2035 } 2036 2037 /** applies one round of separation on the given primal solution or on the LP solution */ 2038 SCIP_RETCODE SCIPseparationRound( 2039 BMS_BLKMEM* blkmem, /**< block memory buffers */ 2040 SCIP_SET* set, /**< global SCIP settings */ 2041 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 2042 SCIP_STAT* stat, /**< dynamic problem statistics */ 2043 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2044 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 2045 SCIP_PROB* prob, /**< transformed problem after presolve */ 2046 SCIP_PRIMAL* primal, /**< primal data */ 2047 SCIP_TREE* tree, /**< branch and bound tree */ 2048 SCIP_LP* lp, /**< LP data */ 2049 SCIP_SEPASTORE* sepastore, /**< separation storage */ 2050 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */ 2051 int actdepth, /**< current depth in the tree */ 2052 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */ 2053 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */ 2054 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */ 2055 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 2056 ) 2057 { 2058 SCIP_Bool enoughcuts; 2059 2060 assert(delayed != NULL); 2061 assert(cutoff != NULL); 2062 2063 *delayed = FALSE; 2064 *cutoff = FALSE; 2065 enoughcuts = FALSE; 2066 2067 if( sol == NULL ) 2068 { 2069 SCIP_Bool lperror; 2070 SCIP_Bool mustsepa; 2071 SCIP_Bool mustprice; 2072 2073 /* apply a separation round on the LP solution */ 2074 lperror = FALSE; 2075 mustsepa = FALSE; 2076 mustprice = FALSE; 2077 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, prob, primal, tree, lp, sepastore, \ 2078 actdepth, 0.0, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff, \ 2079 &lperror, &mustsepa, &mustprice) ); 2080 } 2081 else 2082 { 2083 /* apply a separation round on the given primal solution */ 2084 SCIP_CALL( separationRoundSol(blkmem, set, stat, sepastore, sol, actdepth, allowlocal, onlydelayed, delayed, &enoughcuts, cutoff) ); 2085 } 2086 2087 return SCIP_OKAY; 2088 } 2089 2090 /** solves the current LP completely with pricing in new variables */ 2091 SCIP_RETCODE SCIPpriceLoop( 2092 BMS_BLKMEM* blkmem, /**< block memory buffers */ 2093 SCIP_SET* set, /**< global SCIP settings */ 2094 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 2095 SCIP_STAT* stat, /**< dynamic problem statistics */ 2096 SCIP_PROB* transprob, /**< transformed problem */ 2097 SCIP_PROB* origprob, /**< original problem */ 2098 SCIP_PRIMAL* primal, /**< primal data */ 2099 SCIP_TREE* tree, /**< branch and bound tree */ 2100 SCIP_REOPT* reopt, /**< reoptimization data structure */ 2101 SCIP_LP* lp, /**< LP data */ 2102 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 2103 SCIP_SEPASTORE* sepastore, /**< separation storage */ 2104 SCIP_CUTPOOL* cutpool, /**< global cutpool */ 2105 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 2106 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2107 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 2108 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 2109 SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */ 2110 SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */ 2111 int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit); 2112 * a finite limit means that the LP might not be solved to optimality! */ 2113 int* npricedcolvars, /**< pointer to store number of column variables after problem vars were priced */ 2114 SCIP_Bool* mustsepa, /**< pointer to store TRUE if a separation round should follow */ 2115 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */ 2116 SCIP_Bool* aborted /**< pointer to store whether the pricing was aborted and the lower bound must 2117 * not be used */ 2118 ) 2119 { 2120 SCIP_NODE* currentnode; 2121 int npricerounds; 2122 SCIP_Bool mustprice; 2123 SCIP_Bool cutoff; 2124 SCIP_Bool unbounded; 2125 2126 assert(transprob != NULL); 2127 assert(lp != NULL); 2128 assert(lp->flushed); 2129 assert(lp->solved); 2130 assert(npricedcolvars != NULL); 2131 assert(mustsepa != NULL); 2132 assert(lperror != NULL); 2133 assert(aborted != NULL); 2134 2135 currentnode = SCIPtreeGetCurrentNode(tree); 2136 assert(currentnode == SCIPtreeGetFocusNode(tree) || SCIPtreeProbing(tree)); 2137 *npricedcolvars = transprob->ncolvars; 2138 *lperror = FALSE; 2139 *aborted = FALSE; 2140 2141 /* if the LP is unbounded, we don't need to price */ 2142 mustprice = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL 2143 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE 2144 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT); 2145 2146 /* if all the variables are already in the LP, we don't need to price */ 2147 mustprice = mustprice && !SCIPprobAllColsInLP(transprob, set, lp); 2148 2149 /* check if infinite number of pricing rounds should be used */ 2150 if( maxpricerounds == -1 ) 2151 maxpricerounds = INT_MAX; 2152 2153 /* pricing (has to be done completely to get a valid lower bound) */ 2154 npricerounds = 0; 2155 while( !(*lperror) && mustprice && npricerounds < maxpricerounds ) 2156 { 2157 SCIP_Bool enoughvars; 2158 SCIP_RESULT result; 2159 SCIP_Real lb; 2160 SCIP_Bool foundsol; 2161 SCIP_Bool stopearly; 2162 SCIP_Bool stoppricing; 2163 int p; 2164 2165 assert(lp->flushed); 2166 assert(lp->solved); 2167 assert(SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY); 2168 2169 /* check if pricing loop should be aborted */ 2170 if( SCIPsolveIsStopped(set, stat, FALSE) ) 2171 { 2172 /* do not print the warning message if we stopped because the problem is solved */ 2173 if( !SCIPsetIsLE(set, SCIPgetUpperbound(set->scip), SCIPgetLowerbound(set->scip)) ) 2174 SCIPmessagePrintWarning(messagehdlr, "pricing has been interrupted -- LP of current node is invalid\n"); 2175 2176 *aborted = TRUE; 2177 break; 2178 } 2179 2180 /* call primal heuristics which are callable during pricing */ 2181 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGPRICINGLOOP, 2182 FALSE, &foundsol, &unbounded) ); 2183 2184 /* price problem variables */ 2185 SCIPsetDebugMsg(set, "problem variable pricing\n"); 2186 assert(SCIPpricestoreGetNVars(pricestore) == 0); 2187 assert(SCIPpricestoreGetNBoundResets(pricestore) == 0); 2188 SCIP_CALL( SCIPpricestoreAddProbVars(pricestore, blkmem, set, stat, transprob, tree, lp, branchcand, eventqueue) ); 2189 *npricedcolvars = transprob->ncolvars; 2190 2191 /* call external pricers to create additional problem variables */ 2192 SCIPsetDebugMsg(set, "external variable pricing\n"); 2193 2194 /* sort pricer algorithms by priority */ 2195 SCIPsetSortPricers(set); 2196 2197 /* call external pricer algorithms, that are active for the current problem */ 2198 enoughvars = (SCIPsetGetPriceMaxvars(set, pretendroot) == INT_MAX ? 2199 FALSE : SCIPpricestoreGetNVars(pricestore) >= SCIPsetGetPriceMaxvars(set, pretendroot) + 1); 2200 stoppricing = FALSE; 2201 for( p = 0; p < set->nactivepricers && !enoughvars; ++p ) 2202 { 2203 SCIP_CALL( SCIPpricerExec(set->pricers[p], set, transprob, lp, pricestore, &lb, &stopearly, &result) ); 2204 assert(result == SCIP_DIDNOTRUN || result == SCIP_SUCCESS); 2205 SCIPsetDebugMsg(set, "pricing: pricer %s returned result = %s, lowerbound = %f\n", 2206 SCIPpricerGetName(set->pricers[p]), (result == SCIP_DIDNOTRUN ? "didnotrun" : "success"), lb); 2207 enoughvars = enoughvars || (SCIPsetGetPriceMaxvars(set, pretendroot) == INT_MAX ? 2208 FALSE : SCIPpricestoreGetNVars(pricestore) >= SCIPsetGetPriceMaxvars(set, pretendroot) + 1); 2209 *aborted = ( (*aborted) || (result == SCIP_DIDNOTRUN) ); 2210 2211 /* set stoppricing to TRUE, if the first pricer wants to stop pricing */ 2212 if( p == 0 && stopearly ) 2213 stoppricing = TRUE; 2214 2215 /* stoppricing only remains TRUE, if all other pricers want to stop pricing as well */ 2216 if( stoppricing && !stopearly ) 2217 stoppricing = FALSE; 2218 2219 /* update lower bound w.r.t. the lower bound given by the pricer */ 2220 SCIPnodeUpdateLowerbound(currentnode, stat, set, tree, transprob, origprob, lb); 2221 SCIPsetDebugMsg(set, " -> new lower bound given by pricer %s: %g\n", SCIPpricerGetName(set->pricers[p]), lb); 2222 } 2223 2224 /* apply the priced variables to the LP */ 2225 SCIP_CALL( SCIPpricestoreApplyVars(pricestore, blkmem, set, stat, eventqueue, transprob, tree, lp) ); 2226 assert(SCIPpricestoreGetNVars(pricestore) == 0); 2227 assert(!lp->flushed || lp->solved); 2228 mustprice = !lp->flushed || (transprob->ncolvars != *npricedcolvars); 2229 *mustsepa = *mustsepa || !lp->flushed; 2230 2231 /* after adding columns, the LP should be primal feasible such that the primal simplex is applicable; 2232 * if LP was infeasible, we have to use dual simplex 2233 */ 2234 SCIPsetDebugMsg(set, "pricing: solve LP\n"); 2235 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, TRUE, FALSE, lperror) ); 2236 assert(lp->flushed); 2237 assert(lp->solved || *lperror); 2238 2239 /* reset bounds temporarily set by pricer to their original values */ 2240 SCIPsetDebugMsg(set, "pricing: reset bounds\n"); 2241 SCIP_CALL( SCIPpricestoreResetBounds(pricestore, blkmem, set, stat, lp, branchcand, eventqueue) ); 2242 assert(SCIPpricestoreGetNVars(pricestore) == 0); 2243 assert(SCIPpricestoreGetNBoundResets(pricestore) == 0); 2244 assert(!lp->flushed || lp->solved || *lperror); 2245 2246 /* put all initial constraints into the LP */ 2247 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, 2248 eventfilter, cliquetable, FALSE, FALSE, &cutoff) ); 2249 assert(cutoff == FALSE); 2250 2251 mustprice = mustprice || !lp->flushed || (transprob->ncolvars != *npricedcolvars); 2252 *mustsepa = *mustsepa || !lp->flushed; 2253 2254 /* if all pricers wanted to stop pricing, do not do another pricing round (LP value is no valid dual bound in this case) */ 2255 if( stoppricing ) 2256 { 2257 SCIPsetDebugMsg(set, "pricing: stop pricing and perform early branching\n"); 2258 mustprice = FALSE; 2259 *aborted = TRUE; 2260 } 2261 2262 /* solve LP again after resetting bounds and adding new initial constraints (with dual simplex) */ 2263 SCIPsetDebugMsg(set, "pricing: solve LP after resetting bounds and adding new initial constraints\n"); 2264 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) ); 2265 assert(lp->flushed); 2266 assert(lp->solved || *lperror); 2267 2268 /* remove previous primal ray, store new one if LP is unbounded */ 2269 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) ); 2270 2271 /* increase pricing round counter */ 2272 stat->npricerounds++; 2273 npricerounds++; 2274 2275 /* display node information line */ 2276 if( displayinfo && mustprice ) 2277 { 2278 if( (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_FULL 2279 || ((SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH && npricerounds % 100 == 1) ) 2280 { 2281 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) ); 2282 } 2283 } 2284 2285 /* if the LP is unbounded, we can stop pricing */ 2286 mustprice = mustprice && 2287 (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL 2288 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE 2289 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT ); 2290 2291 /* if the lower bound is already higher than the cutoff bound, we can stop pricing */ 2292 mustprice = mustprice && SCIPsetIsLT(set, SCIPnodeGetLowerbound(currentnode), primal->cutoffbound); 2293 } /*lint !e438*/ 2294 assert(lp->flushed); 2295 assert(lp->solved || *lperror); 2296 2297 *aborted = ( (*aborted) || (*lperror) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_NOTSOLVED 2298 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ERROR || npricerounds == maxpricerounds ); 2299 2300 /* set information, whether the current lp is a valid relaxation of the current problem */ 2301 SCIPlpSetIsRelax(lp, !(*aborted)); 2302 2303 return SCIP_OKAY; /*lint !e438*/ 2304 } 2305 2306 /** separates cuts of the cut pool */ 2307 static 2308 SCIP_RETCODE cutpoolSeparate( 2309 SCIP_CUTPOOL* cutpool, /**< cut pool */ 2310 BMS_BLKMEM* blkmem, /**< block memory */ 2311 SCIP_SET* set, /**< global SCIP settings */ 2312 SCIP_STAT* stat, /**< problem statistics data */ 2313 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2314 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */ 2315 SCIP_LP* lp, /**< current LP data */ 2316 SCIP_SEPASTORE* sepastore, /**< separation storage */ 2317 SCIP_Bool cutpoolisdelayed, /**< is the cutpool delayed (count cuts found)? */ 2318 SCIP_Bool root, /**< are we at the root node? */ 2319 int actdepth, /**< the depth of the focus node */ 2320 SCIP_Bool* enoughcuts, /**< pointer to store if enough cuts were found in current separation round */ 2321 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */ 2322 ) 2323 { 2324 if( (set->sepa_poolfreq == 0 && actdepth == 0) 2325 || (set->sepa_poolfreq > 0 && actdepth % set->sepa_poolfreq == 0) ) 2326 { 2327 SCIP_RESULT result; 2328 2329 SCIP_CALL( SCIPcutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, NULL, cutpoolisdelayed, root, &result) ); 2330 *cutoff = *cutoff || (result == SCIP_CUTOFF); 2331 if( SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)) ) 2332 *enoughcuts = TRUE; 2333 else if( SCIPsetIsNegative(set, SCIPsetGetSepaMaxcutsGenFactor(set, root)) ) 2334 *enoughcuts = *enoughcuts || (result == SCIP_NEWROUND); 2335 else 2336 { 2337 *enoughcuts = *enoughcuts || (SCIPsepastoreGetNCuts(sepastore) >= (SCIP_Longint)SCIPsetCeil(set, 2338 SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root))) 2339 || (result == SCIP_NEWROUND); 2340 } 2341 } 2342 2343 return SCIP_OKAY; 2344 } 2345 2346 /** solve the current LP of a node with a price-and-cut loop */ 2347 static 2348 SCIP_RETCODE priceAndCutLoop( 2349 BMS_BLKMEM* blkmem, /**< block memory buffers */ 2350 SCIP_SET* set, /**< global SCIP settings */ 2351 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 2352 SCIP_STAT* stat, /**< dynamic problem statistics */ 2353 SCIP_MEM* mem, /**< block memory pools */ 2354 SCIP_PROB* transprob, /**< transformed problem */ 2355 SCIP_PROB* origprob, /**< original problem */ 2356 SCIP_PRIMAL* primal, /**< primal data */ 2357 SCIP_TREE* tree, /**< branch and bound tree */ 2358 SCIP_REOPT* reopt, /**< reoptimization data structure */ 2359 SCIP_LP* lp, /**< LP data */ 2360 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 2361 SCIP_SEPASTORE* sepastore, /**< separation storage */ 2362 SCIP_CUTPOOL* cutpool, /**< global cut pool */ 2363 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */ 2364 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 2365 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 2366 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 2367 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 2368 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2369 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 2370 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */ 2371 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */ 2372 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */ 2373 SCIP_Bool* unbounded, /**< pointer to store whether an unbounded ray was found in the LP */ 2374 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */ 2375 SCIP_Bool* pricingaborted /**< pointer to store whether the pricing was aborted and the lower bound must 2376 * not be used */ 2377 ) 2378 { 2379 SCIP_NODE* focusnode; 2380 /* cppcheck-suppress unassignedVariable */ 2381 SCIP_EVENT event; 2382 SCIP_LPSOLSTAT stalllpsolstat; 2383 SCIP_Real loclowerbound; 2384 SCIP_Real glblowerbound; 2385 SCIP_Real bounddist; 2386 SCIP_Real stalllpobjval; 2387 SCIP_Bool separate; 2388 SCIP_Bool mustprice; 2389 SCIP_Bool mustsepa; 2390 SCIP_Bool delayedsepa; 2391 SCIP_Bool root; 2392 SCIP_Bool allowlocal; 2393 int maxseparounds; 2394 int nsepastallrounds; 2395 int maxnsepastallrounds; 2396 int stallnfracs; 2397 int actdepth; 2398 int npricedcolvars; 2399 2400 assert(set != NULL); 2401 assert(blkmem != NULL); 2402 assert(stat != NULL); 2403 assert(transprob != NULL); 2404 assert(tree != NULL); 2405 assert(lp != NULL); 2406 assert(pricestore != NULL); 2407 assert(sepastore != NULL); 2408 assert(cutpool != NULL); 2409 assert(delayedcutpool != NULL); 2410 assert(primal != NULL); 2411 assert(cutoff != NULL); 2412 assert(unbounded != NULL); 2413 assert(lperror != NULL); 2414 2415 focusnode = SCIPtreeGetFocusNode(tree); 2416 assert(focusnode != NULL); 2417 assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE); 2418 actdepth = SCIPnodeGetDepth(focusnode); 2419 root = (actdepth == 0); 2420 2421 /* check, if we want to separate at this node */ 2422 loclowerbound = SCIPnodeGetLowerbound(focusnode); 2423 glblowerbound = SCIPtreeGetLowerbound(tree, set); 2424 assert(primal->cutoffbound > glblowerbound); 2425 bounddist = (loclowerbound - glblowerbound)/(primal->cutoffbound - glblowerbound); 2426 allowlocal = SCIPsetIsLE(set, bounddist, set->sepa_maxlocalbounddist); 2427 separate = (set->sepa_maxruns == -1 || stat->nruns < set->sepa_maxruns); 2428 2429 /* get maximal number of separation rounds */ 2430 maxseparounds = (root ? set->sepa_maxroundsroot : set->sepa_maxrounds); 2431 if( maxseparounds == -1 ) 2432 maxseparounds = INT_MAX; 2433 if( stat->nruns > 1 && root && set->sepa_maxroundsrootsubrun >= 0 ) 2434 maxseparounds = MIN(maxseparounds, set->sepa_maxroundsrootsubrun); 2435 if( !fullseparation && set->sepa_maxaddrounds >= 0 ) 2436 maxseparounds = MIN(maxseparounds, stat->nseparounds + set->sepa_maxaddrounds); 2437 maxnsepastallrounds = root ? set->sepa_maxstallroundsroot : set->sepa_maxstallrounds; 2438 if( maxnsepastallrounds == -1 ) 2439 maxnsepastallrounds = INT_MAX; 2440 2441 /* solve initial LP of price-and-cut loop */ 2442 SCIPsetDebugMsg(set, "node: solve LP with price and cut\n"); 2443 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, 2444 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) ); 2445 assert(lp->flushed); 2446 assert(lp->solved || *lperror); 2447 2448 /* remove previous primal ray, store new one if LP is unbounded */ 2449 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) ); 2450 2451 /* price-and-cut loop */ 2452 npricedcolvars = transprob->ncolvars; 2453 mustprice = TRUE; 2454 mustsepa = separate; 2455 delayedsepa = FALSE; 2456 *cutoff = FALSE; 2457 *unbounded = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 2458 nsepastallrounds = 0; 2459 stalllpsolstat = SCIP_LPSOLSTAT_NOTSOLVED; 2460 stalllpobjval = SCIP_REAL_MIN; 2461 stallnfracs = INT_MAX; 2462 lp->installing = FALSE; 2463 while( !(*cutoff) && !(*unbounded) && !(*lperror) && (mustprice || mustsepa || delayedsepa) ) 2464 { 2465 SCIPsetDebugMsg(set, "-------- node solving loop --------\n"); 2466 assert(lp->flushed); 2467 assert(lp->solved); 2468 2469 /* solve the LP with pricing in new variables */ 2470 while( mustprice && !(*lperror) ) 2471 { 2472 SCIP_CALL( SCIPpriceLoop(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp, 2473 pricestore, sepastore, cutpool, branchcand, eventqueue, eventfilter, cliquetable, root, root, -1, &npricedcolvars, 2474 &mustsepa, lperror, pricingaborted) ); 2475 2476 mustprice = FALSE; 2477 2478 assert(lp->flushed); 2479 assert(lp->solved || *lperror); 2480 2481 /* update lower bound w.r.t. the LP solution */ 2482 if( !(*lperror) && !(*pricingaborted) && SCIPlpIsRelax(lp) ) 2483 { 2484 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) ); 2485 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n", 2486 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob)); 2487 2488 /* update node estimate */ 2489 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) ); 2490 2491 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL ) 2492 SCIPprobUpdateBestRootSol(transprob, set, stat, lp); 2493 } 2494 else 2495 { 2496 SCIPsetDebugMsg(set, " -> error solving LP or pricing aborted. keeping old bound: %g\n", SCIPnodeGetLowerbound(focusnode)); 2497 } 2498 2499 /* display node information line for root node */ 2500 if( root && (SCIP_VERBLEVEL)set->disp_verblevel >= SCIP_VERBLEVEL_HIGH ) 2501 { 2502 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) ); 2503 } 2504 2505 if( !(*lperror) ) 2506 { 2507 /* call propagators that are applicable during LP solving loop only if the node is not cut off */ 2508 if( SCIPsetIsLT(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound) ) 2509 { 2510 SCIP_Longint oldnboundchgs; 2511 SCIP_Longint oldninitconssadded; 2512 SCIP_Bool postpone; 2513 2514 oldnboundchgs = stat->nboundchgs; 2515 oldninitconssadded = stat->ninitconssadded; 2516 2517 SCIPsetDebugMsg(set, " -> LP solved: call propagators that are applicable during LP solving loop\n"); 2518 2519 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, FALSE, 2520 SCIP_PROPTIMING_DURINGLPLOOP, cutoff, &postpone) ); 2521 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 2522 assert(!postpone); 2523 2524 if( stat->ninitconssadded != oldninitconssadded ) 2525 { 2526 SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n", oldninitconssadded, stat->ninitconssadded); 2527 2528 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, 2529 branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) ); 2530 } 2531 2532 if( !(*cutoff) && !(*unbounded) ) 2533 { 2534 /* if we found something, solve LP again */ 2535 if( !lp->flushed ) 2536 { 2537 SCIPsetDebugMsg(set, " -> found reduction: resolve LP\n"); 2538 2539 /* in the root node, remove redundant rows permanently from the LP */ 2540 if( root ) 2541 { 2542 SCIP_CALL( SCIPlpFlush(lp, blkmem, set, transprob, eventqueue) ); 2543 SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) ); 2544 } 2545 2546 /* resolve LP */ 2547 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, 2548 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) ); 2549 assert(lp->flushed); 2550 assert(lp->solved || *lperror); 2551 2552 /* remove previous primal ray, store new one if LP is unbounded */ 2553 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) ); 2554 2555 mustprice = TRUE; 2556 *propagateagain = TRUE; 2557 } 2558 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective 2559 * value which is added to the LP value; because of the loose status, the LP might not be reoptimized, 2560 * but the lower bound of the node needs to be updated 2561 */ 2562 else if( stat->nboundchgs > oldnboundchgs ) 2563 { 2564 *propagateagain = TRUE; 2565 2566 if( lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) ) 2567 { 2568 assert(lp->flushed); 2569 assert(lp->solved); 2570 2571 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) ); 2572 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n", 2573 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob)); 2574 2575 /* update node estimate */ 2576 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) ); 2577 2578 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL ) 2579 SCIPprobUpdateBestRootSol(transprob, set, stat, lp); 2580 } 2581 } 2582 } 2583 } 2584 } 2585 2586 /* call primal heuristics that are applicable during node LP solving loop */ 2587 if( !*cutoff && !(*unbounded) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL ) 2588 { 2589 SCIP_Bool foundsol; 2590 2591 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_DURINGLPLOOP, 2592 FALSE, &foundsol, unbounded) ); 2593 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 2594 2595 *lperror = *lperror || lp->resolvelperror; 2596 } /*lint !e438*/ 2597 } 2598 assert(lp->flushed || *cutoff || *unbounded); 2599 assert(lp->solved || *lperror || *cutoff || *unbounded); 2600 2601 /* check, if we exceeded the separation round limit */ 2602 mustsepa = mustsepa 2603 && stat->nseparounds < maxseparounds 2604 && nsepastallrounds < maxnsepastallrounds 2605 && !(*cutoff); 2606 2607 /* if separators were delayed, we want to apply a final separation round with the delayed separators */ 2608 delayedsepa = delayedsepa && !mustsepa && !(*cutoff); /* if regular separation applies, we ignore delayed separators */ 2609 mustsepa = mustsepa || delayedsepa; 2610 2611 if( mustsepa ) 2612 { 2613 /* if the LP is infeasible, unbounded, exceeded the objective limit or a global performance limit was reached, 2614 * we don't need to separate cuts 2615 * (the global limits are only checked at the root node in order to not query system time too often) 2616 */ 2617 if( !separate || (*cutoff) || (*unbounded) 2618 || (SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY) 2619 || SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound) 2620 || (root && SCIPsolveIsStopped(set, stat, FALSE)) ) 2621 { 2622 mustsepa = FALSE; 2623 delayedsepa = FALSE; 2624 } 2625 else 2626 assert(!(*lperror)); 2627 } 2628 2629 /* separation (needs not to be done completely, because we just want to increase the lower bound) */ 2630 if( mustsepa ) 2631 { 2632 SCIP_Longint olddomchgcount; 2633 SCIP_Longint oldninitconssadded; 2634 SCIP_Bool enoughcuts; 2635 2636 assert(lp->flushed); 2637 assert(lp->solved); 2638 assert(SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 2639 assert(!(*lperror)); 2640 assert(!(*cutoff)); 2641 2642 olddomchgcount = stat->domchgcount; 2643 oldninitconssadded = stat->ninitconssadded; 2644 2645 mustsepa = FALSE; 2646 enoughcuts = SCIPsetIsZero(set, SCIPsetGetSepaMaxcutsGenFactor(set, root) * SCIPsetGetSepaMaxcuts(set, root)); 2647 2648 /* global cut pool separation */ 2649 if( !enoughcuts && !delayedsepa ) 2650 { 2651 SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root, 2652 actdepth, &enoughcuts, cutoff) ); 2653 2654 if( *cutoff ) 2655 { 2656 SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n"); 2657 } 2658 } 2659 assert(lp->flushed); 2660 assert(lp->solved); 2661 assert(SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 2662 assert(!(*lperror)); 2663 2664 /* separate constraints and LP */ 2665 if( !(*cutoff) && !enoughcuts ) 2666 { 2667 /* constraint and LP separation */ 2668 SCIPsetDebugMsg(set, "constraint and LP separation\n"); 2669 2670 /* apply a separation round */ 2671 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal, tree, 2672 lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa, 2673 &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) ); 2674 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 2675 2676 /* if we are close to the stall round limit, also call the delayed separators */ 2677 if( !(*cutoff) && !(*lperror) && !enoughcuts && lp->solved 2678 && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY) 2679 && nsepastallrounds >= maxnsepastallrounds-1 && delayedsepa ) 2680 { 2681 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal, 2682 tree, lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa, 2683 &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) ); 2684 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 2685 } 2686 } 2687 2688 /* call global cut pool separation again since separators may add cuts to the pool instead of the sepastore */ 2689 if( !(*cutoff) && !(*lperror) && lp->solved && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && !enoughcuts ) 2690 { 2691 SCIP_CALL( cutpoolSeparate(cutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, FALSE, root, 2692 actdepth, &enoughcuts, cutoff) ); 2693 2694 if( *cutoff ) 2695 { 2696 SCIPsetDebugMsg(set, " -> global cut pool detected cutoff\n"); 2697 } 2698 } 2699 2700 /* delayed global cut pool separation */ 2701 if( !(*cutoff) && !(*lperror) && lp->solved && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && SCIPsepastoreGetNCuts(sepastore) == 0 && !enoughcuts ) 2702 { 2703 SCIP_CALL( cutpoolSeparate(delayedcutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, TRUE, 2704 root, actdepth, &enoughcuts, cutoff) ); 2705 2706 if( *cutoff ) 2707 { 2708 SCIPsetDebugMsg(set, " -> delayed global cut pool detected cutoff\n"); 2709 } 2710 assert(lp->solved); 2711 assert(SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL); 2712 assert(lp->flushed); 2713 } 2714 2715 /* delayed separation if no cuts where produced */ 2716 if( !(*cutoff) && !(*lperror) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && SCIPsepastoreGetNCuts(sepastore) == 0 && delayedsepa ) 2717 { 2718 SCIP_CALL( separationRoundLP(blkmem, set, messagehdlr, stat, eventqueue, eventfilter, transprob, primal, 2719 tree, lp, sepastore, actdepth, bounddist, allowlocal, delayedsepa, 2720 &delayedsepa, &enoughcuts, cutoff, lperror, &mustsepa, &mustprice) ); 2721 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 2722 2723 /* call delayed cut pool separation again, since separators may add cuts to the pool instead of the sepastore */ 2724 if( !(*cutoff) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL ) 2725 { 2726 assert( !(*lperror) ); 2727 2728 SCIP_CALL( cutpoolSeparate(delayedcutpool, blkmem, set, stat, eventqueue, eventfilter, lp, sepastore, TRUE, 2729 root, actdepth, &enoughcuts, cutoff) ); 2730 2731 if( *cutoff ) 2732 { 2733 SCIPsetDebugMsg(set, " -> delayed global cut pool detected cutoff\n"); 2734 } 2735 assert(SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL); 2736 assert(lp->flushed); 2737 assert(lp->solved); 2738 } 2739 } 2740 2741 assert(*cutoff || *lperror || SCIPlpIsSolved(lp)); 2742 assert(!SCIPlpIsSolved(lp) 2743 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL 2744 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY 2745 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE 2746 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT 2747 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ITERLIMIT 2748 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT); 2749 2750 if( *cutoff || *lperror 2751 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT 2752 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT ) 2753 { 2754 /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */ 2755 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) ); 2756 } 2757 else 2758 { 2759 /* apply found cuts */ 2760 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, 2761 branchcand, eventqueue, eventfilter, cliquetable, root, SCIP_EFFICIACYCHOICE_LP, cutoff) ); 2762 2763 if( !(*cutoff) ) 2764 { 2765 mustprice = mustprice || !lp->flushed || (transprob->ncolvars != npricedcolvars); 2766 mustsepa = mustsepa || !lp->flushed; 2767 2768 /* if a new bound change (e.g. a cut with only one column) was found, propagate domains again */ 2769 if( stat->domchgcount != olddomchgcount ) 2770 { 2771 SCIPsetDebugMsg(set, " -> separation changed bound: propagate again\n"); 2772 2773 *propagateagain = TRUE; 2774 2775 /* in the root node, remove redundant rows permanently from the LP */ 2776 if( root ) 2777 { 2778 SCIP_CALL( SCIPlpFlush(lp, blkmem, set, transprob, eventqueue) ); 2779 SCIP_CALL( SCIPlpRemoveRedundantRows(lp, blkmem, set, stat, eventqueue, eventfilter) ); 2780 } 2781 } 2782 2783 if( stat->ninitconssadded != oldninitconssadded ) 2784 { 2785 SCIPsetDebugMsg(set, "new initial constraints added during propagation: old=%" SCIP_LONGINT_FORMAT ", new=%" SCIP_LONGINT_FORMAT "\n", 2786 oldninitconssadded, stat->ninitconssadded); 2787 2788 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, origprob, tree, reopt, lp, 2789 branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, cutoff) ); 2790 } 2791 2792 if( !(*cutoff) ) 2793 { 2794 SCIP_Real lpobjval; 2795 2796 /* solve LP (with dual simplex) */ 2797 SCIPsetDebugMsg(set, "separation: solve LP\n"); 2798 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, 2799 set->lp_iterlim, FALSE, TRUE, FALSE, lperror) ); 2800 assert(lp->flushed); 2801 assert(lp->solved || *lperror); 2802 2803 /* remove previous primal ray, store new one if LP is unbounded */ 2804 SCIP_CALL( updatePrimalRay(blkmem, set, stat, transprob, primal, tree, lp, *lperror) ); 2805 2806 if( !(*lperror) ) 2807 { 2808 SCIP_Bool stalling; 2809 2810 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value 2811 * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower 2812 * bound of the node needs to be updated 2813 */ 2814 if( stat->domchgcount != olddomchgcount && (!mustprice || mustsepa) && !(*cutoff) 2815 && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) ) 2816 { 2817 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) ); 2818 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n", 2819 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob)); 2820 2821 /* update node estimate */ 2822 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) ); 2823 2824 if( root && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL ) 2825 SCIPprobUpdateBestRootSol(transprob, set, stat, lp); 2826 } 2827 2828 /* check if we are stalling 2829 * If we have an LP solution, then we are stalling if 2830 * we had an LP solution before and 2831 * the LP value did not improve and 2832 * the number of fractional variables did not decrease. 2833 * If we do not have an LP solution, then we are stalling if the solution status of the LP did not change. 2834 */ 2835 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL ) 2836 { 2837 SCIP_Real objreldiff; 2838 int nfracs; 2839 2840 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nfracs, NULL, 2841 NULL) ); 2842 lpobjval = SCIPlpGetObjval(lp, set, transprob); 2843 2844 objreldiff = SCIPrelDiff(lpobjval, stalllpobjval); 2845 SCIPsetDebugMsg(set, " -> LP bound moved from %g to %g (reldiff: %g)\n", 2846 stalllpobjval, lpobjval, objreldiff); 2847 2848 stalling = (stalllpsolstat == SCIP_LPSOLSTAT_OPTIMAL && 2849 objreldiff <= 1e-04 && 2850 nfracs >= (0.9 - 0.1 * nsepastallrounds) * stallnfracs); 2851 2852 stalllpobjval = lpobjval; 2853 stallnfracs = nfracs; 2854 } /*lint !e438*/ 2855 else 2856 { 2857 stalling = (stalllpsolstat == SCIPlpGetSolstat(lp)); 2858 } 2859 2860 if( !stalling ) 2861 { 2862 nsepastallrounds = 0; 2863 lp->installing = FALSE; 2864 } 2865 else 2866 { 2867 nsepastallrounds++; 2868 } 2869 stalllpsolstat = SCIPlpGetSolstat(lp); 2870 2871 /* tell LP that we are (close to) stalling */ 2872 if( nsepastallrounds >= maxnsepastallrounds-2 ) 2873 lp->installing = TRUE; 2874 SCIPsetDebugMsg(set, " -> nsepastallrounds=%d/%d\n", nsepastallrounds, maxnsepastallrounds); 2875 } 2876 } 2877 } 2878 } 2879 assert(*cutoff || *lperror || (lp->flushed && lp->solved)); /* cutoff: LP may be unsolved due to bound changes */ 2880 2881 SCIPsetDebugMsg(set, "separation round %d/%d finished (%d/%d stall rounds): mustprice=%u, mustsepa=%u, delayedsepa=%u, propagateagain=%u\n", 2882 stat->nseparounds, maxseparounds, nsepastallrounds, maxnsepastallrounds, mustprice, mustsepa, delayedsepa, *propagateagain); 2883 2884 /* increase separation round counter */ 2885 stat->nseparounds++; 2886 } 2887 } 2888 2889 if( root && nsepastallrounds >= maxnsepastallrounds ) 2890 { 2891 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL, 2892 "Truncate separation round because of stalling (%d stall rounds).\n", maxnsepastallrounds); 2893 } 2894 2895 if( !*lperror ) 2896 { 2897 /* update pseudo cost values for continuous variables, if it should be delayed */ 2898 SCIP_CALL( updatePseudocost(set, stat, transprob, tree, lp, FALSE, set->branch_delaypscost) ); 2899 } 2900 2901 /* update lower bound w.r.t. the LP solution */ 2902 if( *cutoff ) 2903 { 2904 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set)); 2905 } 2906 else if( !(*lperror) ) 2907 { 2908 assert(lp->flushed); 2909 assert(lp->solved); 2910 2911 if( SCIPlpIsRelax(lp) ) 2912 { 2913 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) ); 2914 } 2915 2916 /* update node estimate */ 2917 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) ); 2918 2919 /* issue LPSOLVED event */ 2920 if( SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_ITERLIMIT && SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_TIMELIMIT ) 2921 { 2922 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_LPSOLVED) ); 2923 SCIP_CALL( SCIPeventChgNode(&event, focusnode) ); 2924 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) ); 2925 } 2926 2927 /* if the LP is a relaxation and we are not solving exactly, then we may analyze an infeasible or bound exceeding 2928 * LP (not necessary in the root node) and cut off the current node 2929 */ 2930 if( !set->misc_exactsolve && !root && SCIPlpIsRelax(lp) && SCIPprobAllColsInLP(transprob, set, lp) 2931 && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT) ) 2932 { 2933 SCIP_CALL( SCIPconflictAnalyzeLP(conflict, conflictstore, blkmem, set, stat, transprob, origprob, tree, reopt, 2934 lp, branchcand, eventqueue, cliquetable, NULL) ); 2935 *cutoff = TRUE; 2936 } 2937 } 2938 /* check for unboundedness */ 2939 if( !(*lperror) ) 2940 { 2941 *unbounded = (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 2942 /* assert(!(*unbounded) || root); */ /* unboundedness can only happen in the root node; no, of course it can also happens in the tree if a branching did not help to resolve unboundedness */ 2943 } 2944 2945 lp->installing = FALSE; 2946 2947 SCIPsetDebugMsg(set, " -> final lower bound: %g (LP status: %d, LP obj: %g)\n", 2948 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), 2949 (*cutoff || *unbounded) ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob)); 2950 2951 return SCIP_OKAY; /*lint !e438*/ 2952 } 2953 2954 /** updates the current lower bound with the pseudo objective value, cuts off node by bounding, and applies conflict 2955 * analysis if the pseudo objective lead to the cutoff 2956 */ 2957 static 2958 SCIP_RETCODE applyBounding( 2959 BMS_BLKMEM* blkmem, /**< block memory buffers */ 2960 SCIP_SET* set, /**< global SCIP settings */ 2961 SCIP_STAT* stat, /**< dynamic problem statistics */ 2962 SCIP_PROB* transprob, /**< tranformed problem after presolve */ 2963 SCIP_PROB* origprob, /**< original problem */ 2964 SCIP_PRIMAL* primal, /**< primal data */ 2965 SCIP_TREE* tree, /**< branch and bound tree */ 2966 SCIP_REOPT* reopt, /**< reoptimization data structure */ 2967 SCIP_LP* lp, /**< LP data */ 2968 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 2969 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2970 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 2971 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 2972 SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */ 2973 ) 2974 { 2975 assert(transprob != NULL); 2976 assert(origprob != NULL); 2977 assert(primal != NULL); 2978 assert(cutoff != NULL); 2979 2980 if( !(*cutoff) ) 2981 { 2982 SCIP_NODE* focusnode; 2983 SCIP_Real pseudoobjval; 2984 2985 /* get current focus node */ 2986 focusnode = SCIPtreeGetFocusNode(tree); 2987 2988 /* update lower bound w.r.t. the pseudo solution */ 2989 pseudoobjval = SCIPlpGetPseudoObjval(lp, set, transprob); 2990 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, pseudoobjval); 2991 SCIPsetDebugMsg(set, " -> lower bound: %g [%g] (pseudoobj: %g [%g]), cutoff bound: %g [%g]\n", 2992 SCIPnodeGetLowerbound(focusnode), SCIPprobExternObjval(transprob, origprob, set, SCIPnodeGetLowerbound(focusnode)) + SCIPgetOrigObjoffset(set->scip), 2993 pseudoobjval, SCIPprobExternObjval(transprob, origprob, set, pseudoobjval) + SCIPgetOrigObjoffset(set->scip), 2994 primal->cutoffbound, SCIPprobExternObjval(transprob, origprob, set, primal->cutoffbound) + SCIPgetOrigObjoffset(set->scip)); 2995 2996 /* check for infeasible node by bounding */ 2997 if( (set->misc_exactsolve && SCIPnodeGetLowerbound(focusnode) >= primal->cutoffbound) 2998 || (!set->misc_exactsolve && SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), primal->cutoffbound)) ) 2999 { 3000 SCIPsetDebugMsg(set, "node is cut off by bounding (lower=%g, upper=%g)\n", 3001 SCIPnodeGetLowerbound(focusnode), primal->cutoffbound); 3002 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set)); 3003 *cutoff = TRUE; 3004 3005 /* call pseudo conflict analysis, if the node is cut off due to the pseudo objective value */ 3006 if( pseudoobjval >= primal->cutoffbound && !SCIPsetIsInfinity(set, primal->cutoffbound) && !SCIPsetIsInfinity(set, -pseudoobjval) ) 3007 { 3008 SCIP_CALL( SCIPconflictAnalyzePseudo(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, NULL) ); 3009 } 3010 } 3011 } 3012 3013 return SCIP_OKAY; 3014 } 3015 3016 /** marks all relaxators to be unsolved */ 3017 static 3018 void markRelaxsUnsolved( 3019 SCIP_SET* set, /**< global SCIP settings */ 3020 SCIP_RELAXATION* relaxation /**< global relaxation data */ 3021 ) 3022 { 3023 int r; 3024 3025 assert(set != NULL); 3026 assert(relaxation != NULL); 3027 3028 SCIPrelaxationSetSolValid(relaxation, FALSE, FALSE); 3029 3030 for( r = 0; r < set->nrelaxs; ++r ) 3031 SCIPrelaxMarkUnsolved(set->relaxs[r]); 3032 } 3033 3034 /** solves the current node's LP in a price-and-cut loop */ 3035 static 3036 SCIP_RETCODE solveNodeLP( 3037 BMS_BLKMEM* blkmem, /**< block memory buffers */ 3038 SCIP_SET* set, /**< global SCIP settings */ 3039 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 3040 SCIP_STAT* stat, /**< dynamic problem statistics */ 3041 SCIP_MEM* mem, /**< block memory pools */ 3042 SCIP_PROB* origprob, /**< original problem */ 3043 SCIP_PROB* transprob, /**< transformed problem after presolve */ 3044 SCIP_PRIMAL* primal, /**< primal data */ 3045 SCIP_TREE* tree, /**< branch and bound tree */ 3046 SCIP_REOPT* reopt, /**< reoptimization data structure */ 3047 SCIP_LP* lp, /**< LP data */ 3048 SCIP_RELAXATION* relaxation, /**< relaxators */ 3049 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 3050 SCIP_SEPASTORE* sepastore, /**< separation storage */ 3051 SCIP_CUTPOOL* cutpool, /**< global cut pool */ 3052 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */ 3053 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 3054 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 3055 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 3056 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 3057 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 3058 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 3059 SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */ 3060 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */ 3061 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */ 3062 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */ 3063 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */ 3064 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 3065 SCIP_Bool* unbounded, /**< pointer to store TRUE, if an unbounded ray was found in the LP */ 3066 SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */ 3067 SCIP_Bool* pricingaborted /**< pointer to store TRUE, if the pricing was aborted and the lower bound 3068 * must not be used */ 3069 ) 3070 { 3071 SCIP_Longint nlpiterations; 3072 SCIP_Longint nlps; 3073 SCIP_Longint nzeroitlps; 3074 3075 assert(stat != NULL); 3076 assert(tree != NULL); 3077 assert(SCIPtreeHasFocusNodeLP(tree)); 3078 assert(cutoff != NULL); 3079 assert(unbounded != NULL); 3080 assert(lperror != NULL); 3081 assert(*cutoff == FALSE); 3082 assert(*unbounded == FALSE); 3083 assert(*lperror == FALSE); 3084 3085 nlps = stat->nlps; 3086 nzeroitlps = stat->ndualzeroitlps + stat->nprimalzeroitlps + stat->nbarrierzeroitlps; 3087 nlpiterations = stat->nlpiterations; 3088 3089 if( !initiallpsolved ) 3090 { 3091 /* load and solve the initial LP of the node */ 3092 SCIP_CALL( solveNodeInitialLP(blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp, 3093 pricestore, sepastore, cutpool, branchcand, eventfilter, eventqueue, cliquetable, newinitconss, cutoff, lperror) ); 3094 3095 assert(*cutoff || *lperror || (lp->flushed && lp->solved)); 3096 SCIPsetDebugMsg(set, "price-and-cut-loop: initial LP status: %d, LP obj: %g\n", 3097 SCIPlpGetSolstat(lp), 3098 *cutoff ? SCIPsetInfinity(set) : *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob)); 3099 3100 /* update initial LP iteration counter */ 3101 stat->ninitlps += stat->nlps - nlps; 3102 stat->ninitlpiterations += stat->nlpiterations - nlpiterations; 3103 3104 /* In the root node, we try if the initial LP solution is feasible to avoid expensive setup of data structures in 3105 * separators; in case the root LP is aborted, e.g., by hitting the time limit, we do not check the LP solution 3106 * since the corresponding data structures have not been updated. 3107 */ 3108 if( SCIPtreeGetCurrentDepth(tree) == 0 && !(*cutoff) && !(*lperror) 3109 && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY) 3110 && !SCIPsolveIsStopped(set, stat, FALSE) ) 3111 { 3112 SCIP_Bool checklprows; 3113 SCIP_Bool stored; 3114 SCIP_SOL* sol; 3115 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound; 3116 3117 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) ); 3118 3119 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 3120 checklprows = FALSE; 3121 else 3122 checklprows = TRUE; 3123 3124 #ifndef NDEBUG 3125 /* in the debug mode we want to explicitly check if the solution is feasible if it was stored */ 3126 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 3127 eventqueue, eventfilter, sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) ); 3128 3129 if( stored ) 3130 { 3131 SCIP_Bool feasible; 3132 3133 SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, FALSE, FALSE, TRUE, TRUE, 3134 checklprows, &feasible) ); 3135 assert(feasible); 3136 } 3137 3138 SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) ); 3139 #else 3140 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 3141 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, checklprows, &stored) ); 3142 #endif 3143 if( stored ) 3144 { 3145 stat->nlpsolsfound++; 3146 3147 if( primal->nbestsolsfound != oldnbestsolsfound ) 3148 { 3149 stat->nlpbestsolsfound++; 3150 SCIPstoreSolutionGap(set->scip); 3151 } 3152 3153 if( set->reopt_enable ) 3154 { 3155 assert(reopt != NULL); 3156 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, tree->focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp, 3157 SCIPlpGetSolstat(lp), tree->root == tree->focusnode, TRUE, tree->focusnode->lowerbound, 3158 tree->effectiverootdepth) ); 3159 } 3160 } 3161 3162 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 3163 *unbounded = TRUE; 3164 } 3165 } 3166 else 3167 { 3168 SCIP_CALL( SCIPinitConssLP(blkmem, set, sepastore, cutpool, stat, transprob, 3169 origprob, tree, reopt, lp, branchcand, eventqueue, eventfilter, cliquetable, FALSE, FALSE, 3170 cutoff) ); 3171 } 3172 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 3173 3174 /* check for infeasible node by bounding */ 3175 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) ); 3176 #ifdef SCIP_DEBUG 3177 if( *cutoff ) 3178 { 3179 if( SCIPtreeGetCurrentDepth(tree) == 0 ) 3180 { 3181 SCIPsetDebugMsg(set, "solution cuts off root node, stop solution process\n"); 3182 } 3183 else 3184 { 3185 SCIPsetDebugMsg(set, "solution cuts off node\n"); 3186 } 3187 } 3188 #endif 3189 3190 if( !(*cutoff) && !(*lperror) ) 3191 { 3192 SCIP_Longint oldninitconssadded; 3193 SCIP_Longint oldnboundchgs; 3194 SCIP_Longint olddomchgcount; 3195 int oldnpricedvars; 3196 int oldncutsapplied; 3197 3198 oldnpricedvars = transprob->ncolvars; 3199 oldninitconssadded = stat->ninitconssadded; 3200 oldncutsapplied = SCIPsepastoreGetNCutsApplied(sepastore); 3201 oldnboundchgs = stat->nboundchgs; 3202 olddomchgcount = stat->domchgcount; 3203 3204 /* solve the LP with price-and-cut*/ 3205 SCIP_CALL( priceAndCutLoop(blkmem, set, messagehdlr, stat, mem, transprob, origprob, primal, tree, reopt, lp, 3206 pricestore, sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter, 3207 eventqueue, cliquetable, fullseparation, propagateagain, cutoff, unbounded, lperror, pricingaborted) ); 3208 3209 /* check if the problem was changed and the relaxation needs to be resolved */ 3210 if( (transprob->ncolvars != oldnpricedvars) || (stat->ninitconssadded != oldninitconssadded) || 3211 (SCIPsepastoreGetNCutsApplied(sepastore) != oldncutsapplied) || (stat->nboundchgs != oldnboundchgs) || 3212 (stat->domchgcount != olddomchgcount) ) 3213 { 3214 *solverelaxagain = TRUE; 3215 markRelaxsUnsolved(set, relaxation); 3216 } 3217 } 3218 assert(*cutoff || *lperror || (lp->flushed && lp->solved)); 3219 3220 /* if there is no LP error, then *unbounded should be TRUE, iff the LP solution status is unboundedray */ 3221 assert(*lperror || ((SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY) == *unbounded)); 3222 3223 /* If pricing was aborted while solving the LP of the node and the node cannot be cut off due to the lower bound computed by the pricer, 3224 * the solving of the LP might be stopped due to the objective limit, but the node may not be cut off, since the LP objective 3225 * is not a feasible lower bound for the solutions in the current subtree. 3226 * In this case, the LP has to be solved to optimality by temporarily removing the cutoff bound. 3227 */ 3228 if( (*pricingaborted) && (SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ITERLIMIT) 3229 && !(*cutoff) ) 3230 { 3231 SCIP_Real tmpcutoff; 3232 3233 /* temporarily disable cutoffbound, which also disables the objective limit */ 3234 tmpcutoff = lp->cutoffbound; 3235 lp->cutoffbound = SCIPlpiInfinity(SCIPlpGetLPI(lp)); 3236 3237 lp->solved = FALSE; 3238 SCIP_CALL( SCIPlpSolveAndEval(lp, set, messagehdlr, blkmem, stat, eventqueue, eventfilter, transprob, -1LL, FALSE, FALSE, FALSE, lperror) ); 3239 3240 /* reinstall old cutoff bound */ 3241 lp->cutoffbound = tmpcutoff; 3242 3243 SCIPsetDebugMsg(set, "re-optimized LP without cutoff bound: LP status: %d, LP obj: %g\n", 3244 SCIPlpGetSolstat(lp), *lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob)); 3245 3246 /* lp solstat should not be objlimit, since the cutoff bound was removed temporarily */ 3247 assert(SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OBJLIMIT); 3248 /* lp solstat should not be unboundedray, since the lp was dual feasible */ 3249 assert(SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY); 3250 /* there should be no primal ray, since the lp was dual feasible */ 3251 assert(primal->primalray == NULL); 3252 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE ) 3253 { 3254 *cutoff = TRUE; 3255 } 3256 } 3257 3258 assert(!(*pricingaborted) || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL /* cppcheck-suppress assertWithSideEffect */ 3259 || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_NOTSOLVED || SCIPsolveIsStopped(set, stat, FALSE) || (*cutoff)); 3260 3261 assert(*cutoff || *lperror || (lp->flushed && lp->solved)); 3262 3263 /* update node's LP iteration counter */ 3264 stat->nnodelps += stat->nlps - nlps; 3265 stat->nnodezeroitlps += stat->ndualzeroitlps + stat->nprimalzeroitlps + stat->nbarrierzeroitlps - nzeroitlps; 3266 stat->nnodelpiterations += stat->nlpiterations - nlpiterations; 3267 3268 /* update number of root node LPs and iterations if the root node was processed */ 3269 if( SCIPnodeGetDepth(tree->focusnode) == 0 ) 3270 { 3271 stat->nrootlps += stat->nlps - nlps; 3272 stat->nrootlpiterations += stat->nlpiterations - nlpiterations; 3273 } 3274 3275 return SCIP_OKAY; 3276 } 3277 3278 /** calls relaxators */ 3279 static 3280 SCIP_RETCODE solveNodeRelax( 3281 SCIP_SET* set, /**< global SCIP settings */ 3282 SCIP_STAT* stat, /**< dynamic problem statistics */ 3283 SCIP_TREE* tree, /**< branch and bound tree */ 3284 SCIP_RELAXATION* relaxation, /**< relaxators */ 3285 SCIP_PROB* transprob, /**< transformed problem */ 3286 SCIP_PROB* origprob, /**< original problem */ 3287 int depth, /**< depth of current node */ 3288 SCIP_Bool beforelp, /**< should the relaxators with non-negative or negative priority be called? */ 3289 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 3290 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */ 3291 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */ 3292 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called 3293 * again */ 3294 SCIP_Bool* relaxcalled /**< pointer to store TRUE, if at least one relaxator was called (unmodified 3295 * otherwise) */ 3296 ) 3297 { 3298 SCIP_RESULT result; 3299 SCIP_Real lowerbound; 3300 int r; 3301 3302 assert(set != NULL); 3303 assert(relaxation != NULL); 3304 assert(cutoff != NULL); 3305 assert(solvelpagain != NULL); 3306 assert(propagateagain != NULL); 3307 assert(solverelaxagain != NULL); 3308 assert(relaxcalled != NULL); 3309 assert(!(*cutoff)); 3310 3311 /* sort by priority */ 3312 SCIPsetSortRelaxs(set); 3313 3314 for( r = 0; r < set->nrelaxs && !(*cutoff); ++r ) 3315 { 3316 if( beforelp != (SCIPrelaxGetPriority(set->relaxs[r]) >= 0) ) 3317 continue; 3318 3319 *relaxcalled = TRUE; 3320 3321 lowerbound = -SCIPsetInfinity(set); 3322 3323 SCIP_CALL( SCIPrelaxExec(set->relaxs[r], set, tree, stat, depth, &lowerbound, &result) ); 3324 3325 switch( result ) 3326 { 3327 case SCIP_CUTOFF: 3328 *cutoff = TRUE; 3329 SCIPsetDebugMsg(set, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(set->relaxs[r])); 3330 /* @todo does it make sense to proceed if the node is proven to be infeasible? */ 3331 return SCIP_OKAY; 3332 3333 case SCIP_CONSADDED: 3334 *solvelpagain = TRUE; /* the separation for new constraints should be called */ 3335 *propagateagain = TRUE; /* the propagation for new constraints should be called */ 3336 break; 3337 3338 case SCIP_REDUCEDDOM: 3339 *solvelpagain = TRUE; 3340 *propagateagain = TRUE; 3341 break; 3342 3343 case SCIP_SEPARATED: 3344 *solvelpagain = TRUE; 3345 break; 3346 3347 case SCIP_SUSPENDED: 3348 *solverelaxagain = TRUE; 3349 break; 3350 3351 case SCIP_SUCCESS: 3352 case SCIP_DIDNOTRUN: 3353 break; 3354 3355 default: 3356 SCIPerrorMessage("invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(set->relaxs[r])); 3357 return SCIP_INVALIDRESULT; 3358 } /*lint !e788*/ 3359 3360 if( result != SCIP_CUTOFF && result != SCIP_DIDNOTRUN && result != SCIP_SUSPENDED ) 3361 { 3362 SCIP_NODE* focusnode; 3363 3364 focusnode = SCIPtreeGetFocusNode(tree); 3365 assert(focusnode != NULL); 3366 assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE); 3367 3368 /* update lower bound w.r.t. the lower bound given by the relaxator */ 3369 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, lowerbound); 3370 SCIPsetDebugMsg(set, " -> new lower bound given by relaxator %s: %g\n", 3371 SCIPrelaxGetName(set->relaxs[r]), lowerbound); 3372 } 3373 } 3374 3375 return SCIP_OKAY; 3376 } 3377 3378 /** enforces constraints by branching, separation, or domain reduction */ 3379 static 3380 SCIP_RETCODE enforceConstraints( 3381 BMS_BLKMEM* blkmem, /**< block memory buffers */ 3382 SCIP_SET* set, /**< global SCIP settings */ 3383 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 3384 SCIP_STAT* stat, /**< dynamic problem statistics */ 3385 SCIP_PROB* prob, /**< transformed problem after presolve */ 3386 SCIP_PRIMAL* primal, /**< primal data */ 3387 SCIP_TREE* tree, /**< branch and bound tree */ 3388 SCIP_LP* lp, /**< LP data */ 3389 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 3390 SCIP_SEPASTORE* sepastore, /**< separation storage */ 3391 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 3392 SCIP_Bool* branched, /**< pointer to store whether a branching was created */ 3393 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 3394 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the LP/pseudo solution is infeasible */ 3395 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */ 3396 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */ 3397 SCIP_Bool* solverelaxagain, /**< pointer to store TRUE, if the external relaxators should be called again */ 3398 SCIP_Bool forced /**< should enforcement of pseudo solution be forced? */ 3399 ) 3400 { 3401 SCIP_RESULT result; 3402 SCIP_SOL* relaxsol = NULL; 3403 SCIP_Real pseudoobjval; 3404 SCIP_Bool resolved; 3405 SCIP_Bool objinfeasible; 3406 SCIP_Bool enforcerelaxsol; 3407 int h; 3408 3409 assert(set != NULL); 3410 assert(stat != NULL); 3411 assert(tree != NULL); 3412 assert(SCIPtreeGetFocusNode(tree) != NULL); 3413 assert(branched != NULL); 3414 assert(cutoff != NULL); 3415 assert(infeasible != NULL); 3416 assert(propagateagain != NULL); 3417 assert(solvelpagain != NULL); 3418 assert(solverelaxagain != NULL); 3419 assert(!(*cutoff)); 3420 assert(!(*propagateagain)); 3421 assert(!(*solvelpagain)); 3422 assert(!(*solverelaxagain)); 3423 3424 *branched = FALSE; 3425 /**@todo avoid checking the same pseudosolution twice */ 3426 3427 /* enforce (best) relaxation solution if the LP has a worse objective value */ 3428 enforcerelaxsol = SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree) 3429 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, prob))); 3430 3431 /* check if all constraint handlers implement the enforelax callback, otherwise enforce the LP solution */ 3432 for( h = 0; h < set->nconshdlrs && enforcerelaxsol; ++h ) 3433 { 3434 if( set->conshdlrs_enfo[h]->consenforelax == NULL && ((! set->conshdlrs_enfo[h]->needscons) || 3435 (set->conshdlrs_enfo[h]->nconss > 0)) ) 3436 { 3437 SCIP_VERBLEVEL verblevel; 3438 3439 enforcerelaxsol = FALSE; 3440 3441 verblevel = SCIP_VERBLEVEL_FULL; 3442 3443 if( !stat->disableenforelaxmsg && set->disp_verblevel == SCIP_VERBLEVEL_HIGH ) 3444 { 3445 verblevel = SCIP_VERBLEVEL_HIGH; 3446 3447 /* remember that the disable relaxation enforcement message was posted and only post it again if the 3448 * verblevel is SCIP_VERBLEVEL_FULL 3449 */ 3450 stat->disableenforelaxmsg = TRUE; 3451 } 3452 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel, "Disable enforcement of relaxation solutions" 3453 " since constraint handler %s does not implement enforelax-callback\n", 3454 SCIPconshdlrGetName(set->conshdlrs_enfo[h])); 3455 } 3456 } 3457 3458 /* enforce constraints by branching, applying additional cutting planes (if LP is being processed), 3459 * introducing new constraints, or tighten the domains 3460 */ 3461 #ifndef SCIP_NDEBUG 3462 if( enforcerelaxsol ) 3463 { 3464 SCIPsetDebugMsg(set, "enforcing constraints on relaxation solution\n"); 3465 } 3466 else 3467 { 3468 SCIPsetDebugMsg(set, "enforcing constraints on %s solution\n", SCIPtreeHasFocusNodeLP(tree) ? "LP" : "pseudo"); 3469 } 3470 #endif 3471 3472 /* check, if the solution is infeasible anyway due to it's objective value */ 3473 if( SCIPtreeHasFocusNodeLP(tree) || enforcerelaxsol ) 3474 objinfeasible = FALSE; 3475 else 3476 { 3477 pseudoobjval = SCIPlpGetPseudoObjval(lp, set, prob); 3478 objinfeasible = SCIPsetIsFeasLT(set, pseudoobjval, SCIPnodeGetLowerbound(SCIPtreeGetFocusNode(tree))); 3479 } 3480 3481 /* during constraint enforcement, generated cuts should enter the LP in any case; otherwise, a constraint handler 3482 * would fail to enforce its constraints if it relies on the modification of the LP relaxation 3483 */ 3484 SCIPsepastoreStartForceCuts(sepastore); 3485 3486 /* enforce constraints until a handler resolved an infeasibility with cutting off the node, branching, 3487 * reducing a domain, or separating a cut 3488 * if a constraint handler introduced new constraints to enforce his constraints, the newly added constraints 3489 * have to be enforced themselves 3490 */ 3491 resolved = FALSE; 3492 3493 /* in case the relaxation solution should be enforced, we need to create the corresponding solution for the enforelax callbacks */ 3494 if( enforcerelaxsol ) 3495 { 3496 SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) ); 3497 } 3498 3499 for( h = 0; h < set->nconshdlrs && !resolved; ++h ) 3500 { 3501 assert(SCIPsepastoreGetNCuts(sepastore) == 0); /* otherwise, the LP should have been resolved first */ 3502 3503 /* enforce LP, pseudo, or relaxation solution */ 3504 if( enforcerelaxsol ) 3505 { 3506 SCIPsetDebugMsg(set, "enforce relaxation solution with value %g\n", SCIPrelaxationGetSolObj(relaxation)); 3507 3508 SCIP_CALL( SCIPconshdlrEnforceRelaxSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore, 3509 relaxsol, *infeasible, &result) ); 3510 } 3511 else if( SCIPtreeHasFocusNodeLP(tree) ) 3512 { 3513 SCIPsetDebugMsg(set, "enforce LP solution with value %g\n", SCIPlpGetObjval(lp, set, prob)); 3514 3515 assert(lp->flushed); 3516 assert(lp->solved); 3517 assert(SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 3518 SCIP_CALL( SCIPconshdlrEnforceLPSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, sepastore, *infeasible, 3519 &result) ); 3520 } 3521 else 3522 { 3523 SCIP_CALL( SCIPconshdlrEnforcePseudoSol(set->conshdlrs_enfo[h], blkmem, set, stat, tree, branchcand, *infeasible, 3524 objinfeasible, forced, &result) ); 3525 if( SCIPsepastoreGetNCuts(sepastore) != 0 ) 3526 { 3527 SCIPerrorMessage("pseudo enforcing method of constraint handler <%s> separated cuts\n", 3528 SCIPconshdlrGetName(set->conshdlrs_enfo[h])); 3529 return SCIP_INVALIDRESULT; 3530 } 3531 } 3532 SCIPsetDebugMsg(set, "enforcing of <%s> returned result %d\n", SCIPconshdlrGetName(set->conshdlrs_enfo[h]), result); 3533 3534 switch( result ) 3535 { 3536 case SCIP_CUTOFF: 3537 assert(tree->nchildren == 0); 3538 *cutoff = TRUE; 3539 *infeasible = TRUE; 3540 resolved = TRUE; 3541 SCIPsetDebugMsg(set, " -> constraint handler <%s> detected cutoff in enforcement\n", 3542 SCIPconshdlrGetName(set->conshdlrs_enfo[h])); 3543 break; 3544 3545 case SCIP_CONSADDED: 3546 assert(tree->nchildren == 0); 3547 *infeasible = TRUE; 3548 *propagateagain = TRUE; /* the propagation for new constraints should be called */ 3549 *solvelpagain = TRUE; /* the separation for new constraints should be called */ 3550 *solverelaxagain = TRUE; 3551 markRelaxsUnsolved(set, relaxation); 3552 resolved = TRUE; 3553 break; 3554 3555 case SCIP_REDUCEDDOM: 3556 assert(tree->nchildren == 0); 3557 *infeasible = TRUE; 3558 *propagateagain = TRUE; 3559 *solvelpagain = TRUE; 3560 *solverelaxagain = TRUE; 3561 markRelaxsUnsolved(set, relaxation); 3562 resolved = TRUE; 3563 break; 3564 3565 case SCIP_SEPARATED: 3566 assert(tree->nchildren == 0); 3567 assert(SCIPsepastoreGetNCuts(sepastore) > 0); 3568 *infeasible = TRUE; 3569 *solvelpagain = TRUE; 3570 *solverelaxagain = TRUE; 3571 markRelaxsUnsolved(set, relaxation); 3572 resolved = TRUE; 3573 break; 3574 3575 case SCIP_BRANCHED: 3576 assert(tree->nchildren >= 1); 3577 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved)); 3578 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 3579 *infeasible = TRUE; 3580 *branched = TRUE; 3581 resolved = TRUE; 3582 3583 /* increase the number of internal nodes */ 3584 stat->ninternalnodes++; 3585 stat->ntotalinternalnodes++; 3586 break; 3587 3588 case SCIP_SOLVELP: 3589 /* either LP was not solved, or it is not solved anymore (e.g., because feastol has been tightened by some constraint handler) */ 3590 assert(!SCIPtreeHasFocusNodeLP(tree) || !lp->solved); 3591 assert(tree->nchildren == 0); 3592 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 3593 *infeasible = TRUE; 3594 *solvelpagain = TRUE; 3595 resolved = TRUE; 3596 SCIPtreeSetFocusNodeLP(tree, TRUE); /* the node's LP must be solved */ 3597 break; 3598 3599 case SCIP_INFEASIBLE: 3600 assert(tree->nchildren == 0); 3601 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved)); 3602 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 3603 *infeasible = TRUE; 3604 break; 3605 3606 case SCIP_FEASIBLE: 3607 assert(tree->nchildren == 0); 3608 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved)); 3609 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 3610 break; 3611 3612 case SCIP_DIDNOTRUN: 3613 assert(tree->nchildren == 0); 3614 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved)); 3615 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 3616 assert(objinfeasible); 3617 *infeasible = TRUE; 3618 break; 3619 3620 default: 3621 SCIPerrorMessage("invalid result code <%d> from enforcing method of constraint handler <%s>\n", 3622 result, SCIPconshdlrGetName(set->conshdlrs_enfo[h])); 3623 return SCIP_INVALIDRESULT; 3624 } /*lint !e788*/ 3625 3626 /* the enforcement method may add a primal solution, after which the LP status could be set to 3627 * objective limit reached 3628 */ 3629 if( SCIPtreeHasFocusNodeLP(tree) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT ) 3630 { 3631 *cutoff = TRUE; 3632 *infeasible = TRUE; 3633 resolved = TRUE; 3634 SCIPsetDebugMsg(set, " -> LP exceeded objective limit\n"); 3635 3636 /* If we used the probing mode during branching, it might happen that we added a constraint or global bound 3637 * and returned SCIP_CONSADDED or SCIP_REDUCEDDOM, but when reoptimizing the LP after ending the probing mode, 3638 * this leads to hitting the objective limit. In this case, we do not need to propagate or solve the LP again. 3639 */ 3640 *propagateagain = FALSE; 3641 *solvelpagain = FALSE; 3642 } 3643 3644 assert(!(*branched) || (resolved && !(*cutoff) && *infeasible && !(*propagateagain) && !(*solvelpagain))); 3645 assert(!(*cutoff) || (resolved && !(*branched) && *infeasible && !(*propagateagain) && !(*solvelpagain))); 3646 assert(*infeasible || (!resolved && !(*branched) && !(*cutoff) && !(*propagateagain) && !(*solvelpagain))); 3647 assert(!(*propagateagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible)); 3648 assert(!(*solvelpagain) || (resolved && !(*branched) && !(*cutoff) && *infeasible)); 3649 } 3650 assert(!objinfeasible || *infeasible); 3651 assert(resolved == (*branched || *cutoff || *propagateagain || *solvelpagain)); 3652 assert(*cutoff || *solvelpagain || SCIPsepastoreGetNCuts(sepastore) == 0); 3653 3654 /* in case the relaxation solution was enforced, free the created solution */ 3655 if( enforcerelaxsol ) 3656 { 3657 SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) ); 3658 } 3659 3660 /* deactivate the cut forcing of the constraint enforcement */ 3661 SCIPsepastoreEndForceCuts(sepastore); 3662 3663 SCIPsetDebugMsg(set, " -> enforcing result: branched=%u, cutoff=%u, infeasible=%u, propagateagain=%u, solvelpagain=%u, resolved=%u\n", 3664 *branched, *cutoff, *infeasible, *propagateagain, *solvelpagain, resolved); 3665 3666 return SCIP_OKAY; 3667 } 3668 3669 /** applies the cuts stored in the separation store, or clears the store if the node can be cut off */ 3670 static 3671 SCIP_RETCODE applyCuts( 3672 BMS_BLKMEM* blkmem, /**< block memory buffers */ 3673 SCIP_SET* set, /**< global SCIP settings */ 3674 SCIP_STAT* stat, /**< dynamic problem statistics */ 3675 SCIP_PROB* transprob, /**< transformed problem */ 3676 SCIP_PROB* origprob, /**< original problem */ 3677 SCIP_TREE* tree, /**< branch and bound tree */ 3678 SCIP_REOPT* reopt, /**< reotimization data structure */ 3679 SCIP_LP* lp, /**< LP data */ 3680 SCIP_RELAXATION* relaxation, /**< relaxators */ 3681 SCIP_SEPASTORE* sepastore, /**< separation storage */ 3682 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 3683 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 3684 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 3685 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 3686 SCIP_Bool root, /**< is this the initial root LP? */ 3687 SCIP_EFFICIACYCHOICE efficiacychoice, /**< type of solution to base efficiacy computation on */ 3688 SCIP_Bool* cutoff, /**< pointer to whether the node can be cut off */ 3689 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */ 3690 SCIP_Bool* solvelpagain, /**< pointer to store TRUE, if the node's LP has to be solved again */ 3691 SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if the node's relaxation has to be solved again */ 3692 ) 3693 { 3694 assert(stat != NULL); 3695 assert(cutoff != NULL); 3696 assert(propagateagain != NULL); 3697 assert(solvelpagain != NULL); 3698 3699 if( *cutoff ) 3700 { 3701 /* the found cuts are of no use, because the node is infeasible anyway (or we have an error in the LP) */ 3702 SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) ); 3703 } 3704 else if( SCIPsepastoreGetNCuts(sepastore) > 0 ) 3705 { 3706 SCIP_Longint olddomchgcount; 3707 int oldncutsapplied; 3708 3709 olddomchgcount = stat->domchgcount; 3710 oldncutsapplied = SCIPsepastoreGetNCutsApplied(sepastore); 3711 SCIP_CALL( SCIPsepastoreApplyCuts(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, 3712 eventqueue, eventfilter, cliquetable, root, efficiacychoice, cutoff) ); 3713 *propagateagain = *propagateagain || (stat->domchgcount != olddomchgcount); 3714 *solvelpagain = TRUE; 3715 if( (stat->domchgcount != olddomchgcount) || (SCIPsepastoreGetNCutsApplied(sepastore) != oldncutsapplied) ) 3716 { 3717 *solverelaxagain = TRUE; 3718 markRelaxsUnsolved(set, relaxation); 3719 } 3720 } 3721 3722 return SCIP_OKAY; 3723 } 3724 3725 /** updates the cutoff, propagateagain, and solverelaxagain status of the current solving loop */ 3726 static 3727 void updateLoopStatus( 3728 SCIP_SET* set, /**< global SCIP settings */ 3729 SCIP_STAT* stat, /**< dynamic problem statistics */ 3730 SCIP_TREE* tree, /**< branch and bound tree */ 3731 int depth, /**< depth of current node */ 3732 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 3733 SCIP_Bool* propagateagain, /**< pointer to store TRUE, if domain propagation should be applied again */ 3734 SCIP_Bool* solverelaxagain /**< pointer to store TRUE, if at least one relaxator should be called again */ 3735 ) 3736 { 3737 SCIP_NODE* focusnode; 3738 int r; 3739 3740 assert(set != NULL); 3741 assert(stat != NULL); 3742 assert(cutoff != NULL); 3743 assert(propagateagain != NULL); 3744 assert(solverelaxagain != NULL); 3745 3746 /* check, if the path was cutoff */ 3747 *cutoff = *cutoff || (tree->cutoffdepth <= depth); 3748 3749 /* check if branching was already performed */ 3750 if( tree->nchildren == 0 ) 3751 { 3752 /* check, if the focus node should be repropagated */ 3753 focusnode = SCIPtreeGetFocusNode(tree); 3754 *propagateagain = *propagateagain || SCIPnodeIsPropagatedAgain(focusnode); 3755 3756 /* check, if one of the external relaxations should be solved again */ 3757 for( r = 0; r < set->nrelaxs && !(*solverelaxagain); ++r ) 3758 *solverelaxagain = *solverelaxagain || ( !SCIPrelaxIsSolved(set->relaxs[r], stat) ); 3759 } 3760 else 3761 { 3762 /* if branching was performed, avoid another node loop iteration */ 3763 *propagateagain = FALSE; 3764 *solverelaxagain = FALSE; 3765 } 3766 } 3767 3768 /** propagate domains and solve relaxation and lp */ 3769 static 3770 SCIP_RETCODE propAndSolve( 3771 BMS_BLKMEM* blkmem, /**< block memory buffers */ 3772 SCIP_SET* set, /**< global SCIP settings */ 3773 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 3774 SCIP_STAT* stat, /**< dynamic problem statistics */ 3775 SCIP_MEM* mem, /**< block memory pools */ 3776 SCIP_PROB* origprob, /**< original problem */ 3777 SCIP_PROB* transprob, /**< transformed problem after presolve */ 3778 SCIP_PRIMAL* primal, /**< primal data */ 3779 SCIP_TREE* tree, /**< branch and bound tree */ 3780 SCIP_REOPT* reopt, /**< reoptimization data structure */ 3781 SCIP_LP* lp, /**< LP data */ 3782 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 3783 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 3784 SCIP_SEPASTORE* sepastore, /**< separation storage */ 3785 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 3786 SCIP_CUTPOOL* cutpool, /**< global cut pool */ 3787 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */ 3788 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 3789 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 3790 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 3791 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 3792 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 3793 SCIP_NODE* focusnode, /**< focused node */ 3794 int actdepth, /**< depth in the b&b tree */ 3795 SCIP_Bool propagate, /**< should we propagate */ 3796 SCIP_Bool solvelp, /**< should we solve the lp */ 3797 SCIP_Bool solverelax, /**< should we solve the relaxation */ 3798 SCIP_Bool forcedlpsolve, /**< is there a need for a solve lp */ 3799 SCIP_Bool initiallpsolved, /**< was the initial LP already solved? */ 3800 SCIP_Bool fullseparation, /**< are we in the first prop-and-cut-and-price loop? */ 3801 SCIP_Longint* afterlpproplps, /**< pointer to store the last LP count for which AFTERLP propagation was performed */ 3802 SCIP_HEURTIMING* heurtiming, /**< timing for running heuristics after propagation call */ 3803 int* nlperrors, /**< pointer to store the number of lp errors */ 3804 SCIP_Bool* fullpropagation, /**< pointer to store whether we want to do a fullpropagation next time */ 3805 SCIP_Bool* propagateagain, /**< pointer to store whether we want to propagate again */ 3806 SCIP_Bool* lpsolved, /**< pointer to store whether the lp was solved */ 3807 SCIP_Bool* relaxcalled, /**< pointer to store whether a relaxator was called; initialized with last loop's result */ 3808 SCIP_Bool* solvelpagain, /**< pointer to store whether we want to solve the lp again */ 3809 SCIP_Bool* solverelaxagain, /**< pointer to store whether we want to solve the relaxation again */ 3810 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */ 3811 SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */ 3812 SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */ 3813 SCIP_Bool* stopped, /**< pointer to store whether solving was interrupted */ 3814 SCIP_Bool* lperror, /**< pointer to store TRUE, if an unresolved error in LP solving occured */ 3815 SCIP_Bool* pricingaborted, /**< pointer to store TRUE, if the pricing was aborted and the lower bound must not be used */ 3816 SCIP_Bool* forcedenforcement /**< pointer to store whether the enforcement of pseudo solution should be forced */ 3817 ) 3818 { 3819 SCIP_Bool newinitconss; 3820 3821 assert(set != NULL); 3822 assert(stat != NULL); 3823 assert(origprob != NULL); 3824 assert(transprob != NULL); 3825 assert(tree != NULL); 3826 assert(lp != NULL); 3827 assert(primal != NULL); 3828 assert(pricestore != NULL); 3829 assert(sepastore != NULL); 3830 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 3831 assert(branchcand != NULL); 3832 assert(cutpool != NULL); 3833 assert(delayedcutpool != NULL); 3834 assert(conflict != NULL); 3835 assert(SCIPconflictGetNConflicts(conflict) == 0); 3836 assert(eventfilter != NULL); 3837 assert(eventqueue != NULL); 3838 assert(focusnode != NULL); 3839 assert(heurtiming != NULL); 3840 assert(nlperrors != NULL); 3841 assert(fullpropagation != NULL); 3842 assert(propagateagain != NULL); 3843 assert(afterlpproplps != NULL); 3844 assert(lpsolved != NULL); 3845 assert(solvelpagain != NULL); 3846 assert(solverelaxagain != NULL); 3847 assert(cutoff != NULL); 3848 assert(postpone != NULL); 3849 assert(unbounded != NULL); 3850 assert(lperror != NULL); 3851 assert(pricingaborted != NULL); 3852 assert(forcedenforcement != NULL); 3853 3854 newinitconss = FALSE; 3855 3856 if( !(*cutoff) && !(*postpone) ) 3857 { 3858 SCIP_Longint oldninitconssadded; 3859 SCIP_Longint oldnboundchgs; 3860 SCIP_Bool lpwasflushed; 3861 3862 lpwasflushed = lp->flushed; 3863 oldnboundchgs = stat->nboundchgs; 3864 oldninitconssadded = stat->ninitconssadded; 3865 3866 /* call after LP propagators */ 3867 if( ((*afterlpproplps) < stat->nnodelps && (*lpsolved)) || (*relaxcalled) ) 3868 { 3869 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation, 3870 SCIP_PROPTIMING_AFTERLPLOOP, cutoff, postpone) ); 3871 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 3872 3873 /* check, if the path was cutoff */ 3874 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth); 3875 *afterlpproplps = stat->nnodelps; 3876 propagate = propagate || (stat->nboundchgs > oldnboundchgs); 3877 } 3878 3879 /* call before LP propagators */ 3880 if( propagate && !(*cutoff) ) 3881 { 3882 SCIP_CALL( propagateDomains(blkmem, set, stat, tree, SCIPtreeGetCurrentDepth(tree), 0, *fullpropagation, 3883 SCIP_PROPTIMING_BEFORELP, cutoff, postpone) ); 3884 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 3885 } 3886 3887 newinitconss = (stat->ninitconssadded != oldninitconssadded); 3888 *fullpropagation = FALSE; 3889 3890 /* check, if the path was cutoff */ 3891 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth); 3892 3893 /* if the LP was flushed and is now no longer flushed, a bound change occurred, and the LP has to be resolved; 3894 * we also have to solve the LP if new intial constraints were added which need to be added to the LP 3895 */ 3896 solvelp = solvelp || (lpwasflushed && (!lp->flushed || newinitconss)); 3897 solverelax = solverelax || newinitconss; 3898 3899 /* the number of bound changes was increased by the propagation call, thus the relaxation should be solved again */ 3900 if( stat->nboundchgs > oldnboundchgs ) 3901 { 3902 /* propagation might have changed the best bound of loose variables, thereby changing the loose objective value 3903 * which is added to the LP value; because of the loose status, the LP might not be reoptimized, but the lower 3904 * bound of the node needs to be updated 3905 */ 3906 if( !solvelp && lp->flushed && lp->solved && SCIPprobAllColsInLP(transprob, set, lp) && SCIPlpIsRelax(lp) ) 3907 { 3908 SCIP_CALL( SCIPnodeUpdateLowerboundLP(focusnode, set, stat, tree, transprob, origprob, lp) ); 3909 SCIPsetDebugMsg(set, " -> new lower bound: %g (LP status: %d, LP obj: %g)\n", 3910 SCIPnodeGetLowerbound(focusnode), SCIPlpGetSolstat(lp), SCIPlpGetObjval(lp, set, transprob)); 3911 3912 if( SCIPtreeHasFocusNodeLP(tree) ) 3913 { 3914 /* update node estimate */ 3915 SCIP_CALL( updateEstimate(set, stat, tree, lp, branchcand) ); 3916 3917 if( actdepth == 0 && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL ) 3918 SCIPprobUpdateBestRootSol(transprob, set, stat, lp); 3919 } 3920 } 3921 3922 solverelax = TRUE; 3923 markRelaxsUnsolved(set, relaxation); 3924 } 3925 3926 /* update lower bound with the pseudo objective value, and cut off node by bounding */ 3927 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, 3928 conflict, cliquetable, cutoff) ); 3929 } 3930 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 3931 3932 if( *postpone ) 3933 return SCIP_OKAY; 3934 3935 /* call primal heuristics that are applicable after propagation loop before lp solve; 3936 * the first time we go here, we call the before node heuristics instead 3937 */ 3938 if( !(*cutoff) && !SCIPtreeProbing(tree) ) 3939 { 3940 /* if the heuristics find a new incumbent solution, propagate again */ 3941 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, *heurtiming, 3942 FALSE, propagateagain, unbounded) ); 3943 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 3944 3945 *heurtiming = SCIP_HEURTIMING_AFTERPROPLOOP; 3946 3947 /* check if primal heuristics found a solution and we therefore reached a solution limit */ 3948 if( SCIPsolveIsStopped(set, stat, FALSE) ) 3949 { 3950 /* cppcheck-suppress unassignedVariable */ 3951 SCIP_NODE* node; 3952 3953 /* we reached a solution limit and do not want to continue the processing of the current node, but in order to 3954 * allow restarting the optimization process later, we need to create a "branching" with only one child node that 3955 * is a copy of the focusnode 3956 */ 3957 SCIPtreeSetFocusNodeLP(tree, FALSE); 3958 SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) ); 3959 assert(tree->nchildren >= 1); 3960 *stopped = TRUE; 3961 return SCIP_OKAY; 3962 } 3963 3964 /* if diving produced an LP error, switch back to non-LP node */ 3965 if( lp->resolvelperror ) 3966 { 3967 SCIPtreeSetFocusNodeLP(tree, FALSE); 3968 lp->resolvelperror = FALSE; 3969 } 3970 3971 if( *propagateagain ) 3972 { 3973 *solvelpagain = solvelp; 3974 *solverelaxagain = solverelax; 3975 3976 return SCIP_OKAY; 3977 } 3978 } 3979 3980 /* solve external relaxations with non-negative priority */ 3981 *relaxcalled = FALSE; 3982 if( solverelax && !(*cutoff) ) 3983 { 3984 /* clear the storage of external branching candidates */ 3985 SCIPbranchcandClearExternCands(branchcand); 3986 3987 SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, TRUE, 3988 cutoff, propagateagain, solvelpagain, solverelaxagain, relaxcalled) ); 3989 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 3990 3991 /* check, if the path was cutoff */ 3992 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth); 3993 3994 /* apply found cuts */ 3995 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand, 3996 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain, 3997 solvelpagain, solverelaxagain) ); 3998 3999 /* update lower bound with the pseudo objective value, and cut off node by bounding */ 4000 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) ); 4001 } 4002 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4003 4004 /* check, if we want to solve the LP at this node */ 4005 if( solvelp && !(*cutoff) && SCIPtreeHasFocusNodeLP(tree) ) 4006 { 4007 *lperror = FALSE; 4008 *unbounded = FALSE; 4009 4010 /* solve the node's LP */ 4011 SCIP_CALL( solveNodeLP(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation, pricestore, 4012 sepastore, cutpool, delayedcutpool, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, 4013 initiallpsolved, fullseparation, newinitconss, propagateagain, solverelaxagain, cutoff, unbounded, lperror, pricingaborted) ); 4014 4015 *lpsolved = TRUE; 4016 *solvelpagain = FALSE; 4017 SCIPsetDebugMsg(set, " -> LP status: %d, LP obj: %g, iter: %" SCIP_LONGINT_FORMAT ", count: %" SCIP_LONGINT_FORMAT "\n", 4018 SCIPlpGetSolstat(lp), 4019 *cutoff ? SCIPsetInfinity(set) : (*lperror ? -SCIPsetInfinity(set) : SCIPlpGetObjval(lp, set, transprob)), 4020 stat->nlpiterations, stat->lpcount); 4021 4022 /* check, if the path was cutoff */ 4023 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth); 4024 4025 /* if an error occured during LP solving, switch to pseudo solution */ 4026 if( *lperror ) 4027 { 4028 if( forcedlpsolve ) 4029 { 4030 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n", 4031 stat->nnodes, stat->nlps); 4032 return SCIP_LPERROR; 4033 } 4034 SCIPtreeSetFocusNodeLP(tree, FALSE); 4035 ++(*nlperrors); 4036 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL, 4037 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n", 4038 stat->nnodes, stat->nlps, *nlperrors); 4039 } 4040 4041 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ITERLIMIT ) 4042 { 4043 SCIPtreeSetFocusNodeLP(tree, FALSE); 4044 *forcedenforcement = TRUE; 4045 4046 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, actdepth == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL, 4047 "(node %" SCIP_LONGINT_FORMAT ") LP solver hit %s limit in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead\n", 4048 stat->nnodes, SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT ? "time" : "iteration", stat->nlps); 4049 } 4050 4051 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 4052 { 4053 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL, 4054 "(node %" SCIP_LONGINT_FORMAT ") LP relaxation is unbounded (LP %" SCIP_LONGINT_FORMAT ")\n", stat->nnodes, stat->nlps); 4055 } 4056 4057 /* if we solve exactly, the LP claims to be infeasible but the infeasibility could not be proved, 4058 * we have to forget about the LP and use the pseudo solution instead 4059 */ 4060 if( !(*cutoff) && !(*lperror) && (set->misc_exactsolve || *pricingaborted) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_INFEASIBLE 4061 && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound ) 4062 { 4063 if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 && transprob->ncontvars > 0 ) 4064 { 4065 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") could not prove infeasibility of LP %" SCIP_LONGINT_FORMAT " (exactsolve=%u, pricingaborted=%u), all variables are fixed, %d continuous vars\n", 4066 stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, transprob->ncontvars); 4067 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") -> have to call PerPlex() (feature not yet implemented)\n", stat->nnodes); 4068 /**@todo call PerPlex */ 4069 return SCIP_LPERROR; 4070 } 4071 else 4072 { 4073 SCIPtreeSetFocusNodeLP(tree, FALSE); 4074 *forcedenforcement = TRUE; 4075 4076 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL, 4077 "(node %" SCIP_LONGINT_FORMAT ") could not prove infeasibility of LP %" SCIP_LONGINT_FORMAT " (exactsolve=%u, pricingaborted=%u) -- using pseudo solution (%d unfixed vars) instead\n", 4078 stat->nnodes, stat->nlps, set->misc_exactsolve, *pricingaborted, SCIPbranchcandGetNPseudoCands(branchcand)); 4079 } 4080 } 4081 4082 /* update lower bound with the pseudo objective value, and cut off node by bounding */ 4083 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, 4084 cliquetable, cutoff) ); 4085 } 4086 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4087 assert(*cutoff || !SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved)); 4088 4089 /* reset solverelaxagain if no relaxations were solved up to this point (the LP-changes are already included in 4090 * relaxators called after the LP) 4091 */ 4092 *solverelaxagain = *solverelaxagain && *relaxcalled; 4093 4094 /* solve external relaxations with negative priority */ 4095 if( solverelax && !(*cutoff) ) 4096 { 4097 SCIP_CALL( solveNodeRelax(set, stat, tree, relaxation, transprob, origprob, actdepth, FALSE, cutoff, 4098 propagateagain, solvelpagain, solverelaxagain, relaxcalled) ); 4099 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 4100 4101 /* check, if the path was cutoff */ 4102 *cutoff = *cutoff || (tree->cutoffdepth <= actdepth); 4103 4104 /* apply found cuts */ 4105 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand, 4106 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_RELAX, cutoff, propagateagain, 4107 solvelpagain, solverelaxagain) ); 4108 4109 /* update lower bound with the pseudo objective value, and cut off node by bounding */ 4110 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, 4111 cliquetable, cutoff) ); 4112 } 4113 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4114 4115 return SCIP_OKAY; 4116 } 4117 4118 /** check if a restart can be performed */ 4119 #ifndef NDEBUG 4120 static 4121 SCIP_Bool restartAllowed( 4122 SCIP_SET* set, /**< global SCIP settings */ 4123 SCIP_STAT* stat /**< dynamic problem statistics */ 4124 ) 4125 { 4126 assert(set != NULL); 4127 assert(stat != NULL); 4128 4129 return (set->nactivepricers == 0 && !set->reopt_enable 4130 && (set->presol_maxrestarts == -1 || stat->nruns <= set->presol_maxrestarts) 4131 && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts)); 4132 } 4133 #else 4134 #define restartAllowed(set,stat) ((set)->nactivepricers == 0 && !set->reopt_enable && ((set)->presol_maxrestarts == -1 || (stat)->nruns <= (set)->presol_maxrestarts) \ 4135 && (set->limit_restarts == -1 || stat->nruns <= set->limit_restarts)) 4136 #endif 4137 4138 /** solves the focus node */ 4139 static 4140 SCIP_RETCODE solveNode( 4141 BMS_BLKMEM* blkmem, /**< block memory buffers */ 4142 SCIP_SET* set, /**< global SCIP settings */ 4143 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 4144 SCIP_STAT* stat, /**< dynamic problem statistics */ 4145 SCIP_MEM* mem, /**< block memory pools */ 4146 SCIP_PROB* origprob, /**< original problem */ 4147 SCIP_PROB* transprob, /**< transformed problem after presolve */ 4148 SCIP_PRIMAL* primal, /**< primal data */ 4149 SCIP_TREE* tree, /**< branch and bound tree */ 4150 SCIP_REOPT* reopt, /**< reoptimization data structure */ 4151 SCIP_LP* lp, /**< LP data */ 4152 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 4153 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 4154 SCIP_SEPASTORE* sepastore, /**< separation storage */ 4155 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 4156 SCIP_CUTPOOL* cutpool, /**< global cut pool */ 4157 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */ 4158 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 4159 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 4160 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 4161 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 4162 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 4163 SCIP_Bool* cutoff, /**< pointer to store whether the node can be cut off */ 4164 SCIP_Bool* postpone, /**< pointer to store whether the node should be postponed */ 4165 SCIP_Bool* unbounded, /**< pointer to store whether the focus node is unbounded */ 4166 SCIP_Bool* infeasible, /**< pointer to store whether the focus node's solution is infeasible */ 4167 SCIP_Bool* restart, /**< should solving process be started again with presolving? */ 4168 SCIP_Bool* afternodeheur, /**< pointer to store whether AFTERNODE heuristics were already called */ 4169 SCIP_Bool* stopped /**< pointer to store whether solving was interrupted */ 4170 ) 4171 { 4172 SCIP_NODE* focusnode; 4173 SCIP_Longint lastdomchgcount; 4174 SCIP_Longint afterlpproplps; 4175 SCIP_Real restartfac; 4176 SCIP_Longint lastlpcount; 4177 SCIP_HEURTIMING heurtiming; 4178 int actdepth; 4179 int nlperrors; 4180 int nloops; 4181 SCIP_Bool foundsol; 4182 SCIP_Bool focusnodehaslp; 4183 SCIP_Bool lpsolved; 4184 SCIP_Bool initiallpsolved; 4185 SCIP_Bool fullseparation; 4186 SCIP_Bool solverelaxagain; 4187 SCIP_Bool solvelpagain; 4188 SCIP_Bool propagateagain; 4189 SCIP_Bool fullpropagation; 4190 SCIP_Bool branched; 4191 SCIP_Bool forcedlpsolve; 4192 SCIP_Bool wasforcedlpsolve; 4193 SCIP_Bool pricingaborted; 4194 4195 assert(set != NULL); 4196 assert(stat != NULL); 4197 assert(origprob != NULL); 4198 assert(transprob != NULL); 4199 assert(tree != NULL); 4200 assert(primal != NULL); 4201 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4202 assert(SCIPconflictGetNConflicts(conflict) == 0); 4203 assert(cutoff != NULL); 4204 assert(postpone != NULL); 4205 assert(unbounded != NULL); 4206 assert(infeasible != NULL); 4207 assert(restart != NULL); 4208 assert(afternodeheur != NULL); 4209 4210 *cutoff = FALSE; 4211 *postpone = FALSE; 4212 *unbounded = FALSE; 4213 *infeasible = FALSE; 4214 *restart = FALSE; 4215 *afternodeheur = FALSE; 4216 *stopped = FALSE; 4217 pricingaborted = FALSE; 4218 4219 focusnode = SCIPtreeGetFocusNode(tree); 4220 assert(focusnode != NULL); 4221 assert(SCIPnodeGetType(focusnode) == SCIP_NODETYPE_FOCUSNODE); 4222 actdepth = SCIPnodeGetDepth(focusnode); 4223 4224 /* invalidate relaxation solution */ 4225 SCIPrelaxationSetSolValid(relaxation, FALSE, FALSE); 4226 4227 /* clear the storage of external branching candidates */ 4228 SCIPbranchcandClearExternCands(branchcand); 4229 4230 SCIPsetDebugMsg(set, "Processing node %" SCIP_LONGINT_FORMAT " in depth %d, %d siblings\n", 4231 stat->nnodes, actdepth, tree->nsiblings); 4232 SCIPsetDebugMsg(set, "current pseudosolution: obj=%g\n", SCIPlpGetPseudoObjval(lp, set, transprob)); 4233 /*debug(SCIPprobPrintPseudoSol(transprob, set));*/ 4234 4235 /* check, if we want to solve the LP at the selected node: 4236 * - solve the LP, if the lp solve depth and frequency demand solving 4237 * - solve the root LP, if the LP solve frequency is set to 0 4238 * - solve the root LP, if there are continuous variables present 4239 * - don't solve the node if its cut off by the pseudo objective value anyway 4240 */ 4241 focusnodehaslp = (set->lp_solvedepth == -1 || actdepth <= set->lp_solvedepth); 4242 focusnodehaslp = focusnodehaslp && (set->lp_solvefreq >= 1 && actdepth % set->lp_solvefreq == 0); 4243 focusnodehaslp = focusnodehaslp || (actdepth == 0 && set->lp_solvefreq == 0); 4244 focusnodehaslp = focusnodehaslp && SCIPsetIsLT(set, SCIPlpGetPseudoObjval(lp, set, transprob), primal->cutoffbound); 4245 focusnodehaslp = set->reopt_enable ? focusnodehaslp && SCIPreoptGetSolveLP(reopt, set, focusnode) : focusnodehaslp; 4246 SCIPtreeSetFocusNodeLP(tree, focusnodehaslp); 4247 4248 /* external node solving loop: 4249 * - propagate domains 4250 * - solve SCIP_LP 4251 * - enforce constraints 4252 * if a constraint handler adds constraints to enforce its own constraints, both, propagation and LP solving 4253 * is applied again (if applicable on current node); however, if the new constraints don't have the enforce flag set, 4254 * it is possible, that the current infeasible solution is not cut off; in this case, we have to declare the solution 4255 * infeasible and perform a branching 4256 */ 4257 lastdomchgcount = stat->domchgcount; 4258 lastlpcount = stat->lpcount; 4259 initiallpsolved = FALSE; 4260 fullseparation = TRUE; 4261 heurtiming = SCIP_HEURTIMING_BEFORENODE; 4262 nlperrors = 0; 4263 stat->npricerounds = 0; 4264 stat->nseparounds = 0; 4265 solverelaxagain = TRUE; 4266 solvelpagain = TRUE; 4267 propagateagain = TRUE; 4268 fullpropagation = TRUE; 4269 forcedlpsolve = FALSE; 4270 nloops = 0; 4271 4272 while( !(*cutoff) && !(*postpone) && (solverelaxagain || solvelpagain || propagateagain) && nlperrors < MAXNLPERRORS && !(*restart) ) 4273 { 4274 SCIP_Bool lperror; 4275 SCIP_Bool solverelax; 4276 SCIP_Bool solvelp; 4277 SCIP_Bool propagate; 4278 SCIP_Bool forcedenforcement; 4279 SCIP_Bool relaxcalled; 4280 4281 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4282 4283 *unbounded = FALSE; 4284 *infeasible = FALSE; 4285 foundsol = FALSE; 4286 4287 nloops++; 4288 lperror = FALSE; 4289 lpsolved = FALSE; 4290 relaxcalled = FALSE; 4291 forcedenforcement = FALSE; 4292 afterlpproplps = -1L; 4293 4294 while( !lperror && !(*cutoff) && (propagateagain || solvelpagain || solverelaxagain 4295 || (afterlpproplps < stat->nnodelps && lpsolved) || relaxcalled) ) 4296 { 4297 solverelax = solverelaxagain; 4298 solverelaxagain = FALSE; 4299 solvelp = solvelpagain; 4300 solvelpagain = FALSE; 4301 propagate = propagateagain; 4302 propagateagain = FALSE; 4303 4304 /* update lower bound with the pseudo objective value, and cut off node by bounding */ 4305 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, 4306 conflict, cliquetable, cutoff) ); 4307 4308 /* propagate domains before lp solving and solve relaxation and lp */ 4309 SCIPsetDebugMsg(set, " -> node solving loop: call propagators that are applicable before%s LP is solved\n", 4310 lpsolved ? " and after" : ""); 4311 SCIP_CALL( propAndSolve(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, 4312 relaxation, pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter, 4313 eventqueue, cliquetable, focusnode, actdepth, propagate, solvelp, solverelax, forcedlpsolve, initiallpsolved, 4314 fullseparation, &afterlpproplps, &heurtiming, &nlperrors, &fullpropagation, &propagateagain, &lpsolved, &relaxcalled, 4315 &solvelpagain, &solverelaxagain, cutoff, postpone, unbounded, stopped, &lperror, &pricingaborted, &forcedenforcement) ); 4316 initiallpsolved |= lpsolved; 4317 4318 /* time or solution limit was hit and we already created a dummy child node to terminate fast */ 4319 if( *stopped ) 4320 { 4321 /* reset LP feastol to normal value, in case someone tightened it during node solving */ 4322 SCIPlpResetFeastol(lp, set); 4323 return SCIP_OKAY; 4324 } 4325 } 4326 fullseparation = FALSE; 4327 4328 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */ 4329 updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain); 4330 4331 /* call primal heuristics that should be applied after the LP relaxation of the node was solved; 4332 * if this is the first loop of the root node, call also AFTERNODE heuristics already here, since they might help 4333 * to improve the primal bound, thereby producing additional reduced cost strengthenings and strong branching 4334 * bound fixings which also might lead to a restart 4335 */ 4336 if( !(*postpone) && (!(*cutoff) || SCIPtreeGetNNodes(tree) > 0) ) 4337 { 4338 if( actdepth == 0 && !(*afternodeheur) ) 4339 { 4340 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, 4341 SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE, *cutoff, &foundsol, unbounded) ); 4342 *afternodeheur = TRUE; /* the AFTERNODE heuristics should not be called again after the node */ 4343 } 4344 else if( lpsolved || SCIPrelaxationIsSolValid(relaxation) ) 4345 { 4346 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, NULL, SCIP_HEURTIMING_AFTERLPLOOP, 4347 *cutoff, &foundsol, unbounded) ); 4348 } 4349 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 4350 4351 /* heuristics might have found a solution or set the cutoff bound such that the current node is cut off */ 4352 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) ); 4353 } 4354 4355 /* check if heuristics leave us with an invalid LP */ 4356 if( lp->resolvelperror ) 4357 { 4358 if( forcedlpsolve ) 4359 { 4360 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n", 4361 stat->nnodes, stat->nlps); 4362 return SCIP_LPERROR; 4363 } 4364 SCIPtreeSetFocusNodeLP(tree, FALSE); 4365 lp->resolvelperror = FALSE; 4366 nlperrors++; 4367 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL, 4368 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n", 4369 stat->nnodes, stat->nlps, nlperrors); 4370 } 4371 4372 if( pricingaborted && !(*cutoff) && SCIPlpGetSolstat(lp) != SCIP_LPSOLSTAT_OPTIMAL ) 4373 { 4374 SCIPtreeSetFocusNodeLP(tree, FALSE); 4375 4376 /* if we just ran into the time limit this is not really a numerical trouble; 4377 * however, if this is not the case, we print messages about numerical troubles in the current LP 4378 */ 4379 if( !SCIPsolveIsStopped(set, stat, FALSE) ) 4380 { 4381 if( forcedlpsolve ) 4382 { 4383 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " cannot be dealt with\n", 4384 stat->nnodes, stat->nlps); 4385 return SCIP_LPERROR; 4386 } 4387 nlperrors++; 4388 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL, 4389 "(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- using pseudo solution instead (loop %d)\n", 4390 stat->nnodes, stat->nlps, nlperrors); 4391 } 4392 } 4393 4394 /* if an improved solution was found, propagate and solve the relaxations again */ 4395 if( foundsol && !(*cutoff) ) 4396 { 4397 propagateagain = TRUE; 4398 solvelpagain = TRUE; 4399 solverelaxagain = TRUE; 4400 markRelaxsUnsolved(set, relaxation); 4401 } 4402 4403 /* check for immediate restart */ 4404 *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart 4405 || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars) 4406 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) ); 4407 4408 /* enforce constraints */ 4409 branched = FALSE; 4410 if( !(*postpone) && !(*restart) && !(*cutoff) && !solverelaxagain && !solvelpagain && !propagateagain ) 4411 { 4412 /* if the solution changed since the last enforcement, we have to completely reenforce it; otherwise, we 4413 * only have to enforce the additional constraints added in the last enforcement, but keep the infeasible 4414 * flag TRUE in order to not declare the infeasible solution feasible due to disregarding the already 4415 * enforced constraints 4416 */ 4417 if( lastdomchgcount != stat->domchgcount || lastlpcount != stat->lpcount ) 4418 { 4419 lastdomchgcount = stat->domchgcount; 4420 lastlpcount = stat->lpcount; 4421 *infeasible = FALSE; 4422 } 4423 4424 /* call constraint enforcement */ 4425 SCIP_CALL( enforceConstraints(blkmem, set, messagehdlr, stat, transprob, primal, tree, lp, relaxation, sepastore, 4426 branchcand, &branched, cutoff, infeasible, &propagateagain, &solvelpagain, &solverelaxagain, 4427 forcedenforcement) ); 4428 assert(branched == (tree->nchildren > 0)); 4429 assert(!branched || (!(*cutoff) && *infeasible && !propagateagain && !solvelpagain)); 4430 assert(!(*cutoff) || (!branched && *infeasible && !propagateagain && !solvelpagain)); 4431 assert(*infeasible || (!branched && !(*cutoff) && !propagateagain && !solvelpagain)); 4432 assert(!propagateagain || (!branched && !(*cutoff) && *infeasible)); 4433 assert(!solvelpagain || (!branched && !(*cutoff) && *infeasible)); 4434 4435 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 4436 4437 /* apply found cuts */ 4438 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand, 4439 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain, 4440 &solvelpagain, &solverelaxagain) ); 4441 4442 /* update lower bound with the pseudo objective value, and cut off node by bounding */ 4443 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) ); 4444 4445 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */ 4446 updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain); 4447 } 4448 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4449 4450 /* The enforcement detected no infeasibility, so, no branching was performed, 4451 * but the pricing was aborted and the current feasible solution does not have to be the 4452 * best solution in the current subtree --> we have to do a pseudo branching, 4453 * so we set infeasible TRUE and add the current solution to the solution pool 4454 */ 4455 if( pricingaborted && !(*infeasible) && !(*cutoff) && !(*postpone) && !(*restart) ) 4456 { 4457 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound; 4458 SCIP_SOL* sol; 4459 SCIP_Bool stored; 4460 4461 /* in case the relaxation was enforced add this solution, otherwise decide between LP and pseudosol */ 4462 if( SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree) 4463 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) ) 4464 { 4465 SCIP_SOL* relaxsol; 4466 4467 SCIP_CALL( SCIPsolCreateRelaxSol(&relaxsol, blkmem, set, stat, primal, tree, relaxation, NULL) ); 4468 4469 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 4470 eventqueue, eventfilter, relaxsol, FALSE, FALSE, TRUE, TRUE, TRUE, 4471 &stored) ); 4472 4473 SCIP_CALL( SCIPsolFree(&relaxsol, blkmem, primal) ); 4474 4475 if( stored ) 4476 { 4477 stat->nrelaxsolsfound++; 4478 4479 if( primal->nbestsolsfound != oldnbestsolsfound ) 4480 { 4481 stat->nrelaxbestsolsfound++; 4482 SCIPstoreSolutionGap(set->scip); 4483 } 4484 } 4485 } 4486 else 4487 { 4488 SCIP_CALL( SCIPsolCreateCurrentSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) ); 4489 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 4490 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) ); 4491 4492 if( stored ) 4493 { 4494 stat->nlpsolsfound++; 4495 4496 if( primal->nbestsolsfound != oldnbestsolsfound ) 4497 { 4498 stat->nlpbestsolsfound++; 4499 SCIPstoreSolutionGap(set->scip); 4500 } 4501 } 4502 } 4503 4504 *infeasible = TRUE; 4505 } 4506 4507 /* if the node is infeasible, but no constraint handler could resolve the infeasibility 4508 * -> branch on LP, external candidates, or the pseudo solution 4509 * -> e.g. select non-fixed binary or integer variable x with value x', create three 4510 * sons: x <= x'-1, x = x', and x >= x'+1. 4511 * In the left and right branch, the current solution is cut off. In the middle 4512 * branch, the constraints can hopefully reduce domains of other variables to cut 4513 * off the current solution. 4514 * In LP branching, we cannot allow adding constraints, because this does not necessary change the LP and can 4515 * therefore lead to an infinite loop. 4516 */ 4517 wasforcedlpsolve = forcedlpsolve; 4518 forcedlpsolve = FALSE; 4519 if( (*infeasible) && !(*cutoff) && !(*postpone) && !(*restart) 4520 && (!(*unbounded) || SCIPbranchcandGetNExternCands(branchcand) > 0 || SCIPbranchcandGetNPseudoCands(branchcand) > 0) 4521 && !solverelaxagain && !solvelpagain && !propagateagain && !branched ) 4522 { 4523 SCIP_RESULT result = SCIP_DIDNOTRUN; 4524 int nlpcands = 0; 4525 4526 if( SCIPtreeHasFocusNodeLP(tree) ) 4527 { 4528 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpcands, NULL, NULL) ); 4529 } 4530 4531 if ( nlpcands > 0 || SCIPbranchcandGetNExternCands(branchcand) > 0 ) 4532 { 4533 /* If there are LP candidates and their maximal priority is at least the maximal priority of the external 4534 * candidates, then branch on the LP candidates. Note that due to implicit integer variables, 4535 * SCIPbranchcandGetLPMaxPrio(branchcand) might be finite and SCIPbranchcandGetNPrioLPCands(branchcand) > 0, 4536 * but nlpcands == 0. */ 4537 if ( SCIPbranchcandGetLPMaxPrio(branchcand) >= SCIPbranchcandGetExternMaxPrio(branchcand) && nlpcands > 0 ) 4538 { 4539 assert( SCIPbranchcandGetNPrioLPCands(branchcand) > 0 ); 4540 assert( nlpcands > 0 ); 4541 4542 /* branch on LP solution */ 4543 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on LP solution with %d fractionals\n", 4544 SCIPnodeGetDepth(focusnode), nlpcands); 4545 SCIP_CALL( SCIPbranchExecLP(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand, 4546 eventqueue, primal->cutoffbound, FALSE, &result) ); 4547 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 4548 assert(result != SCIP_DIDNOTRUN && result != SCIP_DIDNOTFIND); 4549 } 4550 else 4551 { 4552 assert( SCIPbranchcandGetNPrioExternCands(branchcand) > 0 ); 4553 assert( SCIPbranchcandGetNExternCands(branchcand) > 0 ); 4554 4555 /* branch on external candidates */ 4556 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on %d external branching candidates.\n", 4557 SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNExternCands(branchcand)); 4558 SCIP_CALL( SCIPbranchExecExtern(blkmem, set, stat, transprob, origprob, tree, reopt, lp, sepastore, branchcand, 4559 eventqueue, primal->cutoffbound, TRUE, &result) ); 4560 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 4561 } 4562 } 4563 4564 if( result == SCIP_DIDNOTRUN || result == SCIP_DIDNOTFIND ) 4565 { 4566 /* branch on pseudo solution */ 4567 SCIPsetDebugMsg(set, "infeasibility in depth %d was not resolved: branch on pseudo solution with %d unfixed integers\n", 4568 SCIPnodeGetDepth(focusnode), SCIPbranchcandGetNPseudoCands(branchcand)); 4569 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, 4570 primal->cutoffbound, TRUE, &result) ); 4571 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 4572 } 4573 4574 /* SCIP cannot guarantee convergence if it is necessary to branch on unbounded variables */ 4575 if( result == SCIP_BRANCHED ) 4576 { 4577 SCIP_VAR* var = stat->lastbranchvar; 4578 4579 if( var != NULL && !stat->branchedunbdvar && SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS 4580 && (SCIPsetIsInfinity(set, -SCIPvarGetLbLocal(var)) || SCIPsetIsInfinity(set, SCIPvarGetUbLocal(var))) ) 4581 { 4582 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_NORMAL, 4583 "Starting spatial branch-and-bound on unbounded variable <%s> ([%g,%g]) - cannot guarantee finite termination.\n", 4584 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 4585 stat->branchedunbdvar = TRUE; 4586 } 4587 } 4588 4589 switch( result ) 4590 { 4591 case SCIP_CUTOFF: 4592 assert(tree->nchildren == 0); 4593 *cutoff = TRUE; 4594 SCIPsetDebugMsg(set, " -> branching rule detected cutoff\n"); 4595 break; 4596 case SCIP_CONSADDED: 4597 assert(tree->nchildren == 0); 4598 if( nlpcands > 0 ) 4599 { 4600 SCIPerrorMessage("LP branching rule added constraint, which was not allowed this time\n"); 4601 return SCIP_INVALIDRESULT; 4602 } 4603 propagateagain = TRUE; 4604 solvelpagain = TRUE; 4605 solverelaxagain = TRUE; 4606 markRelaxsUnsolved(set, relaxation); 4607 break; 4608 case SCIP_REDUCEDDOM: 4609 assert(tree->nchildren == 0); 4610 propagateagain = TRUE; 4611 solvelpagain = TRUE; 4612 solverelaxagain = TRUE; 4613 markRelaxsUnsolved(set, relaxation); 4614 break; 4615 case SCIP_SEPARATED: 4616 assert(tree->nchildren == 0); 4617 assert(SCIPsepastoreGetNCuts(sepastore) > 0); 4618 solvelpagain = TRUE; 4619 solverelaxagain = TRUE; 4620 markRelaxsUnsolved(set, relaxation); 4621 break; 4622 case SCIP_BRANCHED: 4623 assert(tree->nchildren >= 1); 4624 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4625 branched = TRUE; 4626 4627 /* increase the number of internal nodes */ 4628 stat->ninternalnodes++; 4629 stat->ntotalinternalnodes++; 4630 break; 4631 case SCIP_DIDNOTFIND: /*lint -fallthrough*/ 4632 case SCIP_DIDNOTRUN: 4633 /* all integer variables in the infeasible solution are fixed, 4634 * - if no continuous variables exist and all variables are known, the infeasible pseudo solution is completely 4635 * fixed, and the node can be cut off 4636 * - if at least one continuous variable exists or we do not know all variables due to external pricers, we 4637 * cannot resolve the infeasibility by branching -> solve LP (and maybe price in additional variables) 4638 */ 4639 assert(tree->nchildren == 0); 4640 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4641 assert(SCIPbranchcandGetNPseudoCands(branchcand) == 0); 4642 4643 if( transprob->ncontvars == 0 && set->nactivepricers == 0 ) 4644 { 4645 *cutoff = TRUE; 4646 SCIPsetDebugMsg(set, " -> cutoff because all variables are fixed in current node\n"); 4647 } 4648 else 4649 { 4650 /* feasible LP solutions with all integers fixed must be feasible 4651 * if also no external branching candidates were available 4652 */ 4653 assert(!SCIPtreeHasFocusNodeLP(tree) || pricingaborted); 4654 4655 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_TIMELIMIT || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_ITERLIMIT || SCIPsolveIsStopped(set, stat, FALSE) ) 4656 { 4657 SCIP_NODE* node; 4658 4659 /* as we hit the time or iteration limit or another interrupt (e.g., gap limit), we do not want to solve the LP again. 4660 * in order to terminate correctly, we create a "branching" with only one child node 4661 * that is a copy of the focusnode 4662 */ 4663 SCIP_CALL( SCIPnodeCreateChild(&node, blkmem, set, stat, tree, 1.0, focusnode->estimate) ); 4664 assert(tree->nchildren >= 1); 4665 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4666 branched = TRUE; 4667 } 4668 else 4669 { 4670 SCIP_VERBLEVEL verblevel; 4671 4672 if( pricingaborted ) 4673 { 4674 SCIPerrorMessage("pricing was aborted, but no branching could be created!\n"); 4675 return SCIP_INVALIDRESULT; 4676 } 4677 4678 if( wasforcedlpsolve ) 4679 { 4680 assert(SCIPtreeHasFocusNodeLP(tree)); 4681 SCIPerrorMessage("LP was solved, all integers fixed, some constraint still infeasible, but no branching could be created!\n"); 4682 return SCIP_INVALIDRESULT; 4683 } 4684 4685 verblevel = SCIP_VERBLEVEL_FULL; 4686 4687 if( !tree->forcinglpmessage && set->disp_verblevel == SCIP_VERBLEVEL_HIGH ) 4688 { 4689 verblevel = SCIP_VERBLEVEL_HIGH; 4690 4691 /* remember that the forcing LP solving message was posted and do only post it again if the 4692 * verblevel is SCIP_VERBLEVEL_FULL 4693 */ 4694 tree->forcinglpmessage = TRUE; 4695 } 4696 4697 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, verblevel, 4698 "(node %" SCIP_LONGINT_FORMAT ") forcing the solution of an LP (last LP %" SCIP_LONGINT_FORMAT ")...\n", stat->nnodes, stat->nlps); 4699 4700 /* solve the LP in the next loop */ 4701 SCIPtreeSetFocusNodeLP(tree, TRUE); 4702 solvelpagain = TRUE; 4703 forcedlpsolve = TRUE; /* this LP must be solved without error - otherwise we have to abort */ 4704 } 4705 } 4706 break; 4707 default: 4708 SCIPerrorMessage("invalid result code <%d> from SCIPbranchLP(), SCIPbranchExt() or SCIPbranchPseudo()\n", result); 4709 return SCIP_INVALIDRESULT; 4710 } /*lint !e788*/ 4711 assert(*cutoff || solvelpagain || propagateagain || branched); /* something must have been done */ 4712 assert(!(*cutoff) || (!solvelpagain && !propagateagain && !branched)); 4713 assert(!solvelpagain || (!(*cutoff) && !branched)); 4714 assert(!propagateagain || (!(*cutoff) && !branched)); 4715 assert(!branched || (!solvelpagain && !propagateagain)); 4716 assert(branched == (tree->nchildren > 0)); 4717 4718 /* apply found cuts */ 4719 SCIP_CALL( applyCuts(blkmem, set, stat, transprob, origprob, tree, reopt, lp, relaxation, sepastore, branchcand, 4720 eventqueue, eventfilter, cliquetable, (actdepth == 0), SCIP_EFFICIACYCHOICE_LP, cutoff, &propagateagain, 4721 &solvelpagain, &solverelaxagain) ); 4722 4723 /* update lower bound with the pseudo objective value, and cut off node by bounding */ 4724 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, cutoff) ); 4725 4726 /* update the cutoff, propagateagain, and solverelaxagain status of current solving loop */ 4727 updateLoopStatus(set, stat, tree, actdepth, cutoff, &propagateagain, &solverelaxagain); 4728 } 4729 4730 /* check for immediate restart */ 4731 *restart = *restart || (actdepth == 0 && restartAllowed(set, stat) && (stat->userrestart 4732 || (stat->nrootintfixingsrun > set->presol_immrestartfac * (transprob->nvars - transprob->ncontvars) 4733 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) ); 4734 4735 SCIPsetDebugMsg(set, "node solving iteration %d finished: cutoff=%u, postpone=%u, propagateagain=%u, solverelaxagain=%u, solvelpagain=%u, nlperrors=%d, restart=%u\n", 4736 nloops, *cutoff, *postpone, propagateagain, solverelaxagain, solvelpagain, nlperrors, *restart); 4737 } 4738 assert(SCIPsepastoreGetNCuts(sepastore) == 0); 4739 assert(*cutoff || SCIPconflictGetNConflicts(conflict) == 0); 4740 4741 /* flush the conflict set storage */ 4742 SCIP_CALL( SCIPconflictFlushConss(conflict, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable) ); 4743 4744 /* check for too many LP errors */ 4745 if( nlperrors >= MAXNLPERRORS ) 4746 { 4747 SCIPerrorMessage("(node %" SCIP_LONGINT_FORMAT ") unresolved numerical troubles in LP %" SCIP_LONGINT_FORMAT " -- aborting\n", stat->nnodes, stat->nlps); 4748 return SCIP_LPERROR; 4749 } 4750 4751 /* check for final restart */ 4752 restartfac = set->presol_subrestartfac; 4753 if( actdepth == 0 ) 4754 restartfac = MIN(restartfac, set->presol_restartfac); 4755 *restart = *restart || (restartAllowed(set, stat) && (stat->userrestart 4756 || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars) 4757 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars))) ); 4758 4759 /* remember the last root LP solution */ 4760 if( actdepth == 0 && !(*cutoff) && !(*unbounded) && !(*postpone) ) 4761 { 4762 /* the root pseudo objective value and pseudo objective value should be equal in the root node */ 4763 assert(SCIPsetIsFeasEQ(set, SCIPlpGetGlobalPseudoObjval(lp, set, transprob), SCIPlpGetPseudoObjval(lp, set, transprob))); 4764 4765 SCIPprobStoreRootSol(transprob, set, stat, lp, SCIPtreeHasFocusNodeLP(tree)); 4766 } 4767 4768 /* check for cutoff */ 4769 if( *cutoff ) 4770 { 4771 SCIPsetDebugMsg(set, "node is cut off\n"); 4772 4773 SCIPnodeUpdateLowerbound(focusnode, stat, set, tree, transprob, origprob, SCIPsetInfinity(set)); 4774 *infeasible = TRUE; 4775 SCIP_CALL( SCIPdebugRemoveNode(blkmem, set, focusnode) ); /*lint !e506 !e774*/ 4776 4777 /* the LP might have been unbounded but not enforced, because the node is cut off anyway */ 4778 *unbounded = FALSE; 4779 } 4780 else if( !(*unbounded) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL && lp->looseobjvalinf == 0 ) 4781 { 4782 /* update the regression statistic nlpbranchcands and LP objective value */ 4783 int nlpbranchcands; 4784 SCIP_Real lpobjval; 4785 4786 /* get number of LP candidate variables */ 4787 SCIP_CALL( SCIPbranchcandGetLPCands(branchcand, set, stat, lp, NULL, NULL, NULL, &nlpbranchcands, NULL, NULL) ); 4788 4789 /* get LP objective value */ 4790 lpobjval = SCIPlpGetObjval(lp, set, transprob); 4791 assert(lpobjval != SCIP_INVALID); /*lint !e777*/ 4792 4793 /* add the observation to the regression */ 4794 SCIPregressionAddObservation(stat->regressioncandsobjval, (SCIP_Real)nlpbranchcands, lpobjval); 4795 } 4796 4797 /* reset LP feastol to normal value, in case someone tightened it during node solving */ 4798 SCIPlpResetFeastol(lp, set); 4799 4800 return SCIP_OKAY; 4801 } 4802 4803 /** if feasible, adds current solution to the solution storage */ 4804 static 4805 SCIP_RETCODE addCurrentSolution( 4806 BMS_BLKMEM* blkmem, /**< block memory buffers */ 4807 SCIP_SET* set, /**< global SCIP settings */ 4808 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 4809 SCIP_STAT* stat, /**< dynamic problem statistics */ 4810 SCIP_PROB* origprob, /**< original problem */ 4811 SCIP_PROB* transprob, /**< transformed problem after presolve */ 4812 SCIP_PRIMAL* primal, /**< primal data */ 4813 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 4814 SCIP_TREE* tree, /**< branch and bound tree */ 4815 SCIP_REOPT* reopt, /**< reoptimization data structure */ 4816 SCIP_LP* lp, /**< LP data */ 4817 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 4818 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 4819 SCIP_Bool checksol /**< should the solution be checked? */ 4820 ) 4821 { 4822 SCIP_Longint oldnbestsolsfound = primal->nbestsolsfound; 4823 SCIP_SOL* sol; 4824 SCIP_Bool foundsol; 4825 4826 /* found a feasible solution */ 4827 if( SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree) 4828 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) ) 4829 { 4830 /* start clock for relaxation solutions */ 4831 SCIPclockStart(stat->relaxsoltime, set); 4832 4833 SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) ); 4834 4835 SCIPsetDebugMsg(set, "found relaxation solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob)); 4836 4837 if( checksol || set->misc_exactsolve ) 4838 { 4839 /* if we want to solve exactly, we have to check the solution exactly again */ 4840 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 4841 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) ); 4842 } 4843 else 4844 { 4845 SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 4846 eventqueue, eventfilter, &sol, &foundsol) ); 4847 } 4848 4849 if( foundsol ) 4850 { 4851 stat->nrelaxsolsfound++; 4852 4853 if( primal->nbestsolsfound != oldnbestsolsfound ) 4854 { 4855 stat->nrelaxbestsolsfound++; 4856 SCIPstoreSolutionGap(set->scip); 4857 } 4858 } 4859 4860 /* stop clock for relaxation solutions */ 4861 SCIPclockStop(stat->relaxsoltime, set); 4862 } 4863 else if( SCIPtreeHasFocusNodeLP(tree) ) 4864 { 4865 assert(lp->primalfeasible); 4866 4867 /* start clock for LP solutions */ 4868 SCIPclockStart(stat->lpsoltime, set); 4869 4870 /* add solution to storage */ 4871 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) ); 4872 4873 SCIPsetDebugMsg(set, "found lp solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob)); 4874 4875 if( checksol || set->misc_exactsolve ) 4876 { 4877 /* if we want to solve exactly, we have to check the solution exactly again */ 4878 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 4879 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) ); 4880 } 4881 else 4882 { 4883 SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 4884 eventqueue, eventfilter, &sol, &foundsol) ); 4885 } 4886 4887 if( foundsol ) 4888 { 4889 stat->nlpsolsfound++; 4890 4891 if( primal->nbestsolsfound != oldnbestsolsfound ) 4892 { 4893 stat->nlpbestsolsfound++; 4894 SCIPstoreSolutionGap(set->scip); 4895 } 4896 } 4897 4898 /* stop clock for LP solutions */ 4899 SCIPclockStop(stat->lpsoltime, set); 4900 } 4901 else 4902 { 4903 /* start clock for pseudo solutions */ 4904 SCIPclockStart(stat->pseudosoltime, set); 4905 4906 /* add solution to storage */ 4907 SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) ); 4908 4909 SCIPsetDebugMsg(set, "found pseudo solution with objective %f\n", SCIPsolGetObj(sol, set, transprob, origprob)); 4910 4911 if( checksol || set->misc_exactsolve ) 4912 { 4913 /* if we want to solve exactly, we have to check the solution exactly again */ 4914 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 4915 eventqueue, eventfilter, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &foundsol) ); 4916 } 4917 else 4918 { 4919 SCIP_CALL( SCIPprimalAddSolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, lp, 4920 eventqueue, eventfilter, &sol, &foundsol) ); 4921 } 4922 4923 /* stop clock for pseudo solutions */ 4924 SCIPclockStop(stat->pseudosoltime, set); 4925 4926 if( foundsol ) 4927 { 4928 stat->npssolsfound++; 4929 4930 if( primal->nbestsolsfound != oldnbestsolsfound ) 4931 { 4932 stat->npsbestsolsfound++; 4933 SCIPstoreSolutionGap(set->scip); 4934 } 4935 } 4936 } 4937 4938 return SCIP_OKAY; 4939 } 4940 4941 /** main solving loop */ 4942 SCIP_RETCODE SCIPsolveCIP( 4943 BMS_BLKMEM* blkmem, /**< block memory buffers */ 4944 SCIP_SET* set, /**< global SCIP settings */ 4945 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 4946 SCIP_STAT* stat, /**< dynamic problem statistics */ 4947 SCIP_MEM* mem, /**< block memory pools */ 4948 SCIP_PROB* origprob, /**< original problem */ 4949 SCIP_PROB* transprob, /**< transformed problem after presolve */ 4950 SCIP_PRIMAL* primal, /**< primal data */ 4951 SCIP_TREE* tree, /**< branch and bound tree */ 4952 SCIP_REOPT* reopt, /**< reoptimization data structure */ 4953 SCIP_LP* lp, /**< LP data */ 4954 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 4955 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 4956 SCIP_SEPASTORE* sepastore, /**< separation storage */ 4957 SCIP_CUTPOOL* cutpool, /**< global cut pool */ 4958 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */ 4959 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 4960 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 4961 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 4962 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 4963 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 4964 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 4965 SCIP_Bool* restart /**< should solving process be started again with presolving? */ 4966 ) 4967 { 4968 SCIP_NODESEL* nodesel; 4969 SCIP_NODE* focusnode; 4970 SCIP_NODE* nextnode; 4971 SCIP_EVENT event; 4972 SCIP_Real restartfac; 4973 SCIP_Real restartconfnum; 4974 int nnodes; 4975 int depth; 4976 SCIP_Bool cutoff; 4977 SCIP_Bool postpone; 4978 SCIP_Bool unbounded; 4979 SCIP_Bool infeasible; 4980 SCIP_Bool foundsol; 4981 4982 assert(set != NULL); 4983 assert(blkmem != NULL); 4984 assert(stat != NULL); 4985 assert(transprob != NULL); 4986 assert(tree != NULL); 4987 assert(lp != NULL); 4988 assert(pricestore != NULL); 4989 assert(sepastore != NULL); 4990 assert(branchcand != NULL); 4991 assert(cutpool != NULL); 4992 assert(delayedcutpool != NULL); 4993 assert(primal != NULL); 4994 assert(eventfilter != NULL); 4995 assert(eventqueue != NULL); 4996 assert(restart != NULL); 4997 4998 /* check for immediate restart (if problem solving marked to be restarted was aborted) */ 4999 restartfac = set->presol_subrestartfac; 5000 if( SCIPtreeGetCurrentDepth(tree) == 0 ) 5001 restartfac = MIN(restartfac, set->presol_restartfac); 5002 *restart = restartAllowed(set, stat) && (stat->userrestart 5003 || (stat->nrootintfixingsrun > restartfac * (transprob->nvars - transprob->ncontvars) 5004 && (stat->nruns == 1 || transprob->nvars <= (1.0-set->presol_restartminred) * stat->prevrunnvars)) ); 5005 5006 /* calculate the number of successful conflict analysis calls that should trigger a restart */ 5007 if( set->conf_restartnum > 0 ) 5008 { 5009 int i; 5010 5011 restartconfnum = (SCIP_Real)set->conf_restartnum; 5012 for( i = 0; i < stat->nconfrestarts; ++i ) 5013 restartconfnum *= set->conf_restartfac; 5014 } 5015 else 5016 restartconfnum = SCIP_REAL_MAX; 5017 assert(restartconfnum >= 0.0); 5018 5019 /* switch status to UNKNOWN */ 5020 stat->status = SCIP_STATUS_UNKNOWN; 5021 5022 focusnode = NULL; 5023 nextnode = NULL; 5024 unbounded = FALSE; 5025 postpone = FALSE; 5026 5027 while( !SCIPsolveIsStopped(set, stat, TRUE) && !(*restart) ) 5028 { 5029 SCIP_Longint nsuccessconflicts; 5030 SCIP_Bool afternodeheur; 5031 SCIP_Bool stopped; 5032 SCIP_Bool branched; 5033 5034 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 5035 5036 foundsol = FALSE; 5037 infeasible = FALSE; 5038 5039 do 5040 { 5041 /* update the memory saving flag, switch algorithms respectively */ 5042 SCIPstatUpdateMemsaveMode(stat, set, messagehdlr, mem); 5043 5044 /* get the current node selector */ 5045 nodesel = SCIPsetGetNodesel(set, stat); 5046 5047 /* inform tree about the current node selector */ 5048 SCIP_CALL( SCIPtreeSetNodesel(tree, set, messagehdlr, stat, nodesel) ); 5049 5050 /* the next node was usually already selected in the previous solving loop before the primal heuristics were 5051 * called, because they need to know, if the next node will be a child/sibling (plunging) or not; 5052 * if the heuristics found a new best solution that cut off some of the nodes, the node selector must be called 5053 * again, because the selected next node may be invalid due to cut off 5054 */ 5055 if( nextnode == NULL ) 5056 { 5057 /* select next node to process */ 5058 SCIP_CALL( SCIPnodeselSelect(nodesel, set, &nextnode) ); 5059 } 5060 focusnode = nextnode; 5061 nextnode = NULL; 5062 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 5063 5064 /* start node activation timer */ 5065 SCIPclockStart(stat->nodeactivationtime, set); 5066 5067 /* focus selected node */ 5068 SCIP_CALL( SCIPnodeFocus(&focusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, 5069 lp, branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, FALSE, FALSE) ); 5070 if( cutoff ) 5071 stat->ndelayedcutoffs++; 5072 5073 /* stop node activation timer */ 5074 SCIPclockStop(stat->nodeactivationtime, set); 5075 5076 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 5077 } 5078 while( cutoff ); /* select new node, if the current one was located in a cut off subtree */ 5079 5080 assert(SCIPtreeGetCurrentNode(tree) == focusnode); 5081 assert(SCIPtreeGetFocusNode(tree) == focusnode); 5082 5083 /* if no more node was selected, we finished optimization */ 5084 if( focusnode == NULL ) 5085 { 5086 assert(SCIPtreeGetNNodes(tree) == 0); 5087 break; 5088 } 5089 5090 /* update maxdepth and node count statistics */ 5091 depth = SCIPnodeGetDepth(focusnode); 5092 stat->maxdepth = MAX(stat->maxdepth, depth); 5093 stat->maxtotaldepth = MAX(stat->maxtotaldepth, depth); 5094 stat->nnodes++; 5095 stat->ntotalnodes++; 5096 5097 /* update reference bound statistic, if available */ 5098 if( SCIPsetIsGE(set, SCIPnodeGetLowerbound(focusnode), stat->referencebound) ) 5099 stat->nnodesaboverefbound++; 5100 5101 /* issue NODEFOCUSED event */ 5102 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_NODEFOCUSED) ); 5103 SCIP_CALL( SCIPeventChgNode(&event, focusnode) ); 5104 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) ); 5105 5106 /* solve focus node */ 5107 SCIP_CALL( solveNode(blkmem, set, messagehdlr, stat, mem, origprob, transprob, primal, tree, reopt, lp, relaxation, 5108 pricestore, sepastore, branchcand, cutpool, delayedcutpool, conflict, conflictstore, eventfilter, eventqueue, 5109 cliquetable, &cutoff, &postpone, &unbounded, &infeasible, restart, &afternodeheur, &stopped) ); 5110 assert(!cutoff || infeasible); 5111 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 5112 assert(SCIPtreeGetCurrentNode(tree) == focusnode); 5113 assert(SCIPtreeGetFocusNode(tree) == focusnode); 5114 5115 branched = (tree->nchildren > 0); 5116 5117 if( stopped ) 5118 break; 5119 5120 /* check for restart */ 5121 if( !(*restart) && !postpone ) 5122 { 5123 /* change color of node in visualization */ 5124 SCIPvisualSolvedNode(stat->visual, set, stat, focusnode); 5125 5126 /* check, if the current solution is feasible */ 5127 if( !infeasible ) 5128 { 5129 SCIP_Bool feasible; 5130 5131 assert(!SCIPtreeHasFocusNodeLP(tree) || (lp->flushed && lp->solved)); 5132 assert(!cutoff); 5133 5134 /* in the unbounded case, we check the solution w.r.t. the original problem, because we do not want to rely 5135 * on the LP feasibility and integrality is not checked for unbounded solutions, anyway 5136 */ 5137 if( unbounded ) 5138 { 5139 SCIP_SOL* sol; 5140 5141 if( SCIPrelaxationIsSolValid(relaxation) && SCIPrelaxationIsLpIncludedForSol(relaxation) && (!SCIPtreeHasFocusNodeLP(tree) 5142 || SCIPsetIsGT(set, SCIPrelaxationGetSolObj(relaxation), SCIPlpGetObjval(lp, set, transprob))) ) 5143 { 5144 SCIP_CALL( SCIPsolCreateRelaxSol(&sol, blkmem, set, stat, primal, tree, relaxation, NULL) ); 5145 } 5146 else if( SCIPtreeHasFocusNodeLP(tree) ) 5147 { 5148 SCIP_CALL( SCIPsolCreateLPSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) ); 5149 } 5150 else 5151 { 5152 SCIP_CALL( SCIPsolCreatePseudoSol(&sol, blkmem, set, stat, transprob, primal, tree, lp, NULL) ); 5153 } 5154 SCIP_CALL( SCIPcheckSolOrig(set->scip, sol, &feasible, FALSE, FALSE) ); 5155 5156 SCIP_CALL( SCIPsolFree(&sol, blkmem, primal) ); 5157 } 5158 else 5159 feasible = TRUE; 5160 5161 /* node solution is feasible: add it to the solution store */ 5162 if( feasible ) 5163 { 5164 SCIP_CALL( addCurrentSolution(blkmem, set, messagehdlr, stat, origprob, transprob, primal, relaxation, tree, reopt, 5165 lp, eventqueue, eventfilter, FALSE) ); 5166 5167 /* update the cutoff pointer if the new solution made the cutoff bound equal to the lower bound */ 5168 SCIP_CALL( applyBounding(blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand, eventqueue, conflict, cliquetable, &cutoff) ); 5169 5170 /* increment number of feasible leaf nodes */ 5171 stat->nfeasleaves++; 5172 5173 /* issue NODEFEASIBLE event */ 5174 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_NODEFEASIBLE) ); 5175 SCIP_CALL( SCIPeventChgNode(&event, focusnode) ); 5176 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) ); 5177 5178 if( set->reopt_enable ) 5179 { 5180 assert(reopt != NULL); 5181 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp, 5182 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode, 5183 focusnode->lowerbound, tree->effectiverootdepth) ); 5184 } 5185 } 5186 } 5187 else if( !unbounded || branched ) 5188 { 5189 /* node solution is not feasible */ 5190 if( !branched ) 5191 { 5192 assert(tree->nchildren == 0); 5193 5194 /* change color of node in visualization output */ 5195 SCIPvisualCutoffNode(stat->visual, set, stat, focusnode, TRUE); 5196 5197 /* issue NODEINFEASIBLE event */ 5198 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_NODEINFEASIBLE) ); 5199 5200 /* we only increase the number of objective leaf nodes if we hit the LP objective limit; we might have also 5201 * hit the objective limit at a node that is actually infeasible, or a dual reduction led to an infeasibility prior 5202 * to LP solving such that the node will be marked as infeasible */ 5203 if( SCIPtreeHasCurrentNodeLP(tree) && SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OBJLIMIT ) 5204 stat->nobjleaves++; 5205 else 5206 stat->ninfeasleaves++; 5207 5208 if( set->reopt_enable ) 5209 { 5210 assert(reopt != NULL); 5211 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEINFEASIBLE, lp, 5212 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode, 5213 focusnode->lowerbound, tree->effectiverootdepth) ); 5214 } 5215 5216 /* increase the cutoff counter of the branching variable */ 5217 if( stat->lastbranchvar != NULL ) 5218 { 5219 SCIP_CALL( SCIPvarIncCutoffSum(stat->lastbranchvar, blkmem, set, stat, stat->lastbranchdir, stat->lastbranchvalue, 1.0) ); 5220 } 5221 /**@todo if last branching variable is unknown, retrieve it from the nodes' boundchg arrays */ 5222 } 5223 else 5224 { 5225 assert(tree->nchildren > 0); 5226 5227 /* issue NODEBRANCHED event */ 5228 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_NODEBRANCHED) ); 5229 5230 if( set->reopt_enable ) 5231 { 5232 assert(reopt != NULL); 5233 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEBRANCHED, lp, 5234 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode, 5235 focusnode->lowerbound, tree->effectiverootdepth) ); 5236 } 5237 } 5238 SCIP_CALL( SCIPeventChgNode(&event, focusnode) ); 5239 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) ); 5240 } 5241 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 5242 5243 /* if no branching was created, the node was not cut off, but its lower bound is still smaller than 5244 * the cutoff bound, we have to branch on a non-fixed variable; 5245 * this can happen, if we want to solve exactly, the current solution was declared feasible by the 5246 * constraint enforcement, but in exact solution checking it was found out to be infeasible; 5247 * in this case, no branching would have been generated by the enforcement of constraints, but we 5248 * have to further investigate the current sub tree; 5249 * note that we must not check tree->nchildren > 0 here to determine whether we branched, we rather 5250 * check it directly after solveNode() and store the result, because an event handler might impose a 5251 * new cutoff bound (as is the case in ParaSCIP) 5252 */ 5253 if( !cutoff && !unbounded && !branched && SCIPnodeGetLowerbound(focusnode) < primal->cutoffbound ) 5254 { 5255 SCIP_RESULT result; 5256 5257 assert(set->misc_exactsolve); 5258 5259 do 5260 { 5261 result = SCIP_DIDNOTRUN; 5262 if( SCIPbranchcandGetNPseudoCands(branchcand) == 0 ) 5263 { 5264 if( transprob->ncontvars > 0 ) 5265 { 5266 /**@todo call PerPlex */ 5267 SCIPerrorMessage("cannot branch on all-fixed LP -- have to call PerPlex instead\n"); 5268 } 5269 } 5270 else 5271 { 5272 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, 5273 eventqueue, primal->cutoffbound, FALSE, &result) ); 5274 assert(result != SCIP_DIDNOTRUN && result != SCIP_DIDNOTFIND); 5275 } 5276 } 5277 while( result == SCIP_REDUCEDDOM ); 5278 } 5279 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 5280 5281 /* select node to process in next solving loop; the primal heuristics need to know whether a child/sibling 5282 * (plunging) will be selected as next node or not 5283 */ 5284 SCIP_CALL( SCIPnodeselSelect(nodesel, set, &nextnode) ); 5285 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 5286 5287 /* call primal heuristics that should be applied after the node was solved */ 5288 nnodes = SCIPtreeGetNNodes(tree); 5289 stopped = SCIPsolveIsStopped(set, stat, FALSE); 5290 if( !afternodeheur && (!cutoff || nnodes > 0) && !stopped ) 5291 { 5292 SCIP_CALL( SCIPprimalHeuristics(set, stat, transprob, primal, tree, lp, nextnode, SCIP_HEURTIMING_AFTERNODE, 5293 cutoff, &foundsol, &unbounded) ); 5294 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 5295 5296 stopped = SCIPsolveIsStopped(set, stat, FALSE); 5297 } 5298 5299 /* if the heuristics found a new best solution that cut off some of the nodes, the node selector must be called 5300 * again, because the selected next node may be invalid due to cut off 5301 */ 5302 assert(!tree->cutoffdelayed); 5303 5304 if( nnodes != SCIPtreeGetNNodes(tree) || stopped ) 5305 nextnode = NULL; 5306 } 5307 else if( !infeasible && !postpone ) 5308 { 5309 /* The current solution was not proven to be infeasible, but due to the restart, this does not mean that it is 5310 * feasible, we might just have skipped the check. Thus, we try to add it to the solution store, but check it 5311 * again. 5312 */ 5313 SCIP_CALL( addCurrentSolution(blkmem, set, messagehdlr, stat, origprob, transprob, primal, relaxation, tree, reopt, lp, 5314 eventqueue, eventfilter, TRUE) ); 5315 5316 if( set->reopt_enable ) 5317 { 5318 assert(reopt != NULL); 5319 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, focusnode, SCIP_EVENTTYPE_NODEFEASIBLE, lp, 5320 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode, focusnode->lowerbound, 5321 tree->effectiverootdepth) ); 5322 } 5323 } 5324 /* we want to put the focusnode back into the leaf queue if it was postponed */ 5325 else if( postpone ) 5326 { 5327 SCIP_NODE* newfocusnode = NULL; 5328 5329 /* @todo should we re-install the old focus node in order to somehow set the forks more clever? */ 5330 SCIP_CALL( SCIPnodeFocus(&newfocusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp, 5331 branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, TRUE, FALSE) ); 5332 } 5333 /* compute number of successfully applied conflicts */ 5334 nsuccessconflicts = SCIPconflictGetNPropSuccess(conflict) + SCIPconflictGetNInfeasibleLPSuccess(conflict) 5335 + SCIPconflictGetNBoundexceedingLPSuccess(conflict) + SCIPconflictGetNStrongbranchSuccess(conflict) 5336 + SCIPconflictGetNPseudoSuccess(conflict); 5337 5338 /* trigger restart due to conflicts and the restart parameters allow another restart */ 5339 if( nsuccessconflicts >= restartconfnum && restartAllowed(set, stat) ) 5340 { 5341 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 5342 "(run %d, node %" SCIP_LONGINT_FORMAT ") restarting after %" SCIP_LONGINT_FORMAT " successful conflict analysis calls\n", 5343 stat->nruns, stat->nnodes, nsuccessconflicts); 5344 *restart = TRUE; 5345 5346 stat->nconfrestarts++; 5347 } 5348 5349 /* restart if the userrestart was set to true, we have still some nodes left and the restart parameters allow 5350 * another restart 5351 */ 5352 *restart = *restart || (stat->userrestart && SCIPtreeGetNNodes(tree) > 0 && restartAllowed(set, stat)); 5353 if( restartAllowed(set, stat) && set->limit_autorestartnodes == stat->nnodes && stat->ntotalnodes - stat->nruns + 1 == set->limit_autorestartnodes ) 5354 { 5355 SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_HIGH, 5356 "(run %d, node %" SCIP_LONGINT_FORMAT ") restarting: triggering parameter controlled restart)\n", 5357 stat->nruns, stat->nnodes); 5358 *restart = TRUE; 5359 } 5360 /* if restart limit was exceeded, change the status; if status is different from unknown, ie some other limit was 5361 * hit, leave it unchanged 5362 */ 5363 if( *restart && stat->status == SCIP_STATUS_UNKNOWN && set->limit_restarts >= 0 && stat->nruns > set->limit_restarts ) 5364 { 5365 *restart = FALSE; 5366 stat->status = SCIP_STATUS_RESTARTLIMIT; 5367 } 5368 5369 /* display node information line */ 5370 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, (SCIPnodeGetDepth(focusnode) == 0) && infeasible && !foundsol, TRUE) ); 5371 5372 SCIPsetDebugMsg(set, "Processing of node %" SCIP_LONGINT_FORMAT " in depth %d finished. %d siblings, %d children, %d leaves left\n", 5373 stat->nnodes, SCIPnodeGetDepth(focusnode), tree->nsiblings, tree->nchildren, SCIPtreeGetNLeaves(tree)); 5374 SCIPsetDebugMsg(set, "**********************************************************************\n"); 5375 } 5376 5377 /* update the primal-dual integral if node or time limits were hit or an interruption signal was called */ 5378 if( SCIPsolveIsStopped(set, stat, TRUE) ) 5379 { 5380 SCIPstatUpdatePrimalDualIntegrals(stat, set, transprob, origprob, SCIPsetInfinity(set), -SCIPsetInfinity(set)); 5381 } 5382 5383 assert(BMSgetNUsedBufferMemory(mem->buffer) == 0); 5384 5385 SCIPsetDebugMsg(set, "Problem solving finished with status %d (restart=%u, userrestart=%u)\n", stat->status, *restart, stat->userrestart); 5386 5387 /* cuts off nodes with lower bound is not better than given cutoff bound, manually; this necessary to ensure that 5388 * SCIP terminates with a proper solve stage 5389 */ 5390 SCIP_CALL( SCIPtreeCutoff(tree, reopt, blkmem, set, stat, eventfilter, eventqueue, lp, primal->cutoffbound) ); 5391 5392 /* if the current node is the only remaining node, and if its lower bound exceeds the upper bound, we have 5393 * to delete it manually in order to get to the SOLVED stage instead of thinking, that only the gap limit 5394 * was reached (this may happen, if the current node is the one defining the global lower bound and a 5395 * feasible solution with the same value was found at this node) 5396 */ 5397 if( tree->focusnode != NULL && SCIPtreeGetNNodes(tree) == 0 5398 && SCIPsetIsGE(set, tree->focusnode->lowerbound, primal->cutoffbound) ) 5399 { 5400 if( set->reopt_enable ) 5401 { 5402 assert(reopt != NULL); 5403 SCIP_CALL( SCIPreoptCheckCutoff(reopt, set, blkmem, tree->focusnode, SCIP_EVENTTYPE_NODEINFEASIBLE, lp, 5404 SCIPlpGetSolstat(lp), tree->root == focusnode, tree->focusnode == focusnode, tree->focusnode->lowerbound, 5405 tree->effectiverootdepth) ); 5406 } 5407 5408 focusnode = NULL; 5409 SCIP_CALL( SCIPnodeFocus(&focusnode, blkmem, set, messagehdlr, stat, transprob, origprob, primal, tree, reopt, lp, 5410 branchcand, conflict, conflictstore, eventfilter, eventqueue, cliquetable, &cutoff, FALSE, FALSE) ); 5411 } 5412 5413 /* check whether we finished solving */ 5414 if( SCIPtreeGetNNodes(tree) == 0 && SCIPtreeGetCurrentNode(tree) == NULL ) 5415 { 5416 /* no restart necessary */ 5417 *restart = FALSE; 5418 5419 /* set the solution status */ 5420 if( unbounded || SCIPsetIsInfinity(set, -SCIPgetUpperbound(set->scip)) ) 5421 { 5422 if( primal->nsols > 0 ) 5423 { 5424 /* switch status to UNBOUNDED */ 5425 stat->status = SCIP_STATUS_UNBOUNDED; 5426 } 5427 else 5428 { 5429 /* switch status to INFORUNB */ 5430 stat->status = SCIP_STATUS_INFORUNBD; 5431 } 5432 } 5433 else if( primal->nlimsolsfound == 0 ) 5434 { 5435 assert(primal->nsols == 0 || SCIPsetIsGT(set, SCIPsolGetObj(primal->sols[0], set, transprob, origprob), 5436 SCIPprobInternObjval(transprob, origprob, set, SCIPprobGetObjlim(transprob, set)))); 5437 5438 /* switch status to INFEASIBLE */ 5439 stat->status = SCIP_STATUS_INFEASIBLE; 5440 } 5441 else 5442 { 5443 /* switch status to OPTIMAL */ 5444 stat->status = SCIP_STATUS_OPTIMAL; 5445 } 5446 } 5447 5448 return SCIP_OKAY; 5449 } 5450