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 primal.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for collecting primal CIP solutions and primal informations 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include <assert.h> 34 35 #include "scip/def.h" 36 #include "scip/set.h" 37 #include "scip/stat.h" 38 #include "scip/visual.h" 39 #include "scip/event.h" 40 #include "scip/lp.h" 41 #include "scip/var.h" 42 #include "scip/prob.h" 43 #include "scip/sol.h" 44 #include "scip/primal.h" 45 #include "scip/tree.h" 46 #include "scip/reopt.h" 47 #include "scip/disp.h" 48 #include "scip/struct_event.h" 49 #include "scip/pub_message.h" 50 #include "scip/pub_var.h" 51 #include "scip/scip_solvingstats.h" 52 53 54 /* 55 * memory growing methods for dynamically allocated arrays 56 */ 57 58 /** ensures, that sols array can store at least num entries */ 59 static 60 SCIP_RETCODE ensureSolsSize( 61 SCIP_PRIMAL* primal, /**< primal data */ 62 SCIP_SET* set, /**< global SCIP settings */ 63 int num /**< minimum number of entries to store */ 64 ) 65 { 66 assert(primal->nsols <= primal->solssize); 67 68 if( num > primal->solssize ) 69 { 70 int newsize; 71 72 newsize = SCIPsetCalcMemGrowSize(set, num); 73 SCIP_ALLOC( BMSreallocMemoryArray(&primal->sols, newsize) ); 74 primal->solssize = newsize; 75 } 76 assert(num <= primal->solssize); 77 78 return SCIP_OKAY; 79 } 80 81 /** ensures, that partialsols array can store at least num entries */ 82 static 83 SCIP_RETCODE ensurePartialsolsSize( 84 SCIP_PRIMAL* primal, /**< primal data */ 85 SCIP_SET* set, /**< global SCIP settings */ 86 int num /**< minimum number of entries to store */ 87 ) 88 { 89 assert(primal->npartialsols <= primal->partialsolssize); 90 91 if( num > primal->partialsolssize ) 92 { 93 int newsize; 94 95 newsize = SCIPsetCalcMemGrowSize(set, num); 96 newsize = MIN(newsize, set->limit_maxorigsol); 97 98 SCIP_ALLOC( BMSreallocMemoryArray(&primal->partialsols, newsize) ); 99 primal->partialsolssize = newsize; 100 } 101 assert(num <= primal->partialsolssize); 102 103 return SCIP_OKAY; 104 } 105 106 /** ensures, that existingsols array can store at least num entries */ 107 static 108 SCIP_RETCODE ensureExistingsolsSize( 109 SCIP_PRIMAL* primal, /**< primal data */ 110 SCIP_SET* set, /**< global SCIP settings */ 111 int num /**< minimum number of entries to store */ 112 ) 113 { 114 assert(primal->nexistingsols <= primal->existingsolssize); 115 116 if( num > primal->existingsolssize ) 117 { 118 int newsize; 119 120 newsize = SCIPsetCalcMemGrowSize(set, num); 121 SCIP_ALLOC( BMSreallocMemoryArray(&primal->existingsols, newsize) ); 122 primal->existingsolssize = newsize; 123 } 124 assert(num <= primal->existingsolssize); 125 126 return SCIP_OKAY; 127 } 128 129 /** creates primal data */ 130 SCIP_RETCODE SCIPprimalCreate( 131 SCIP_PRIMAL** primal /**< pointer to primal data */ 132 ) 133 { 134 assert(primal != NULL); 135 136 SCIP_ALLOC( BMSallocMemory(primal) ); 137 (*primal)->sols = NULL; 138 (*primal)->partialsols = NULL; 139 (*primal)->existingsols = NULL; 140 (*primal)->currentsol = NULL; 141 (*primal)->primalray = NULL; 142 (*primal)->solssize = 0; 143 (*primal)->partialsolssize = 0; 144 (*primal)->nsols = 0; 145 (*primal)->npartialsols = 0; 146 (*primal)->existingsolssize = 0; 147 (*primal)->nexistingsols = 0; 148 (*primal)->nsolsfound = 0; 149 (*primal)->nlimsolsfound = 0; 150 (*primal)->nbestsolsfound = 0; 151 (*primal)->nlimbestsolsfound = 0; 152 (*primal)->upperbound = SCIP_INVALID; 153 (*primal)->cutoffbound = SCIP_INVALID; 154 (*primal)->updateviolations = TRUE; 155 156 return SCIP_OKAY; 157 } 158 159 /** frees primal data */ 160 SCIP_RETCODE SCIPprimalFree( 161 SCIP_PRIMAL** primal, /**< pointer to primal data */ 162 BMS_BLKMEM* blkmem /**< block memory */ 163 ) 164 { 165 int s; 166 167 assert(primal != NULL); 168 assert(*primal != NULL); 169 170 /* free temporary solution for storing current solution */ 171 if( (*primal)->currentsol != NULL ) 172 { 173 SCIP_CALL( SCIPsolFree(&(*primal)->currentsol, blkmem, *primal) ); 174 } 175 176 /* free solution for storing primal ray */ 177 if( (*primal)->primalray != NULL ) 178 { 179 SCIP_CALL( SCIPsolFree(&(*primal)->primalray, blkmem, *primal) ); 180 } 181 182 /* free feasible primal CIP solutions */ 183 for( s = 0; s < (*primal)->nsols; ++s ) 184 { 185 SCIP_CALL( SCIPsolFree(&(*primal)->sols[s], blkmem, *primal) ); 186 } 187 /* free partial CIP solutions */ 188 for( s = 0; s < (*primal)->npartialsols; ++s ) 189 { 190 SCIP_CALL( SCIPsolFree(&(*primal)->partialsols[s], blkmem, *primal) ); 191 } 192 assert((*primal)->nexistingsols == 0); 193 194 BMSfreeMemoryArrayNull(&(*primal)->sols); 195 BMSfreeMemoryArrayNull(&(*primal)->partialsols); 196 BMSfreeMemoryArrayNull(&(*primal)->existingsols); 197 BMSfreeMemory(primal); 198 199 return SCIP_OKAY; 200 } 201 202 /** clears primal data */ 203 SCIP_RETCODE SCIPprimalClear( 204 SCIP_PRIMAL** primal, /**< pointer to primal data */ 205 BMS_BLKMEM* blkmem /**< block memory */ 206 ) 207 { 208 int s; 209 210 assert(primal != NULL); 211 assert(*primal != NULL); 212 213 /* free temporary solution for storing current solution */ 214 if( (*primal)->currentsol != NULL ) 215 { 216 SCIP_CALL( SCIPsolFree(&(*primal)->currentsol, blkmem, *primal) ); 217 } 218 219 /* free solution for storing primal ray */ 220 if( (*primal)->primalray != NULL ) 221 { 222 SCIP_CALL( SCIPsolFree(&(*primal)->primalray, blkmem, *primal) ); 223 } 224 225 /* free feasible primal CIP solutions */ 226 for( s = 0; s < (*primal)->nsols; ++s ) 227 { 228 SCIP_CALL( SCIPsolFree(&(*primal)->sols[s], blkmem, *primal) ); 229 } 230 231 (*primal)->currentsol = NULL; 232 (*primal)->primalray = NULL; 233 (*primal)->nsols = 0; 234 (*primal)->nsolsfound = 0; 235 (*primal)->nlimsolsfound = 0; 236 (*primal)->nbestsolsfound = 0; 237 (*primal)->nlimbestsolsfound = 0; 238 (*primal)->upperbound = SCIP_INVALID; 239 (*primal)->cutoffbound = SCIP_INVALID; 240 (*primal)->updateviolations = TRUE; 241 242 return SCIP_OKAY; 243 } 244 245 /** sorts primal solutions by objective value */ 246 static 247 void sortPrimalSols( 248 SCIP_PRIMAL* primal, /**< primal data */ 249 SCIP_SET* set, /**< global SCIP settings */ 250 SCIP_PROB* origprob, /**< original problem */ 251 SCIP_PROB* transprob /**< transformed problem */ 252 ) 253 { 254 int i; 255 256 for( i = 1; i < primal->nsols; ++i ) 257 { 258 SCIP_SOL* sol; 259 SCIP_Real objval; 260 int j; 261 262 sol = primal->sols[i]; 263 objval = SCIPsolGetObj(sol, set, transprob, origprob); 264 for( j = i; j > 0 && objval < SCIPsolGetObj(primal->sols[j-1], set, transprob, origprob); --j ) 265 primal->sols[j] = primal->sols[j-1]; 266 primal->sols[j] = sol; 267 } 268 269 return; 270 } 271 272 /** sets the cutoff bound in primal data and in LP solver */ 273 static 274 SCIP_RETCODE primalSetCutoffbound( 275 SCIP_PRIMAL* primal, /**< primal data */ 276 BMS_BLKMEM* blkmem, /**< block memory */ 277 SCIP_SET* set, /**< global SCIP settings */ 278 SCIP_STAT* stat, /**< problem statistics data */ 279 SCIP_PROB* prob, /**< problem data */ 280 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 281 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 282 SCIP_TREE* tree, /**< branch and bound tree */ 283 SCIP_REOPT* reopt, /**< reoptimization data structure */ 284 SCIP_LP* lp, /**< current LP data */ 285 SCIP_Real cutoffbound /**< new cutoff bound */ 286 ) 287 { 288 assert(primal != NULL); 289 assert(cutoffbound <= SCIPsetInfinity(set)); 290 assert(primal->upperbound == SCIP_INVALID || SCIPsetIsLE(set, cutoffbound, primal->upperbound)); /*lint !e777*/ 291 assert(!SCIPtreeInRepropagation(tree)); 292 293 SCIPsetDebugMsg(set, "changing cutoff bound from %g to %g\n", primal->cutoffbound, cutoffbound); 294 295 primal->cutoffbound = MIN(cutoffbound, primal->upperbound); /* get rid of numerical issues */ 296 297 /* set cut off value in LP solver */ 298 SCIP_CALL( SCIPlpSetCutoffbound(lp, set, prob, primal->cutoffbound) ); 299 300 /* cut off leaves of the tree */ 301 SCIP_CALL( SCIPtreeCutoff(tree, reopt, blkmem, set, stat, eventfilter, eventqueue, lp, primal->cutoffbound) ); 302 303 return SCIP_OKAY; 304 } 305 306 /** sets the cutoff bound in primal data and in LP solver */ 307 SCIP_RETCODE SCIPprimalSetCutoffbound( 308 SCIP_PRIMAL* primal, /**< primal data */ 309 BMS_BLKMEM* blkmem, /**< block memory */ 310 SCIP_SET* set, /**< global SCIP settings */ 311 SCIP_STAT* stat, /**< problem statistics data */ 312 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 313 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 314 SCIP_PROB* transprob, /**< transformed problem data */ 315 SCIP_PROB* origprob, /**< original problem data */ 316 SCIP_TREE* tree, /**< branch and bound tree */ 317 SCIP_REOPT* reopt, /**< reoptimization data structure */ 318 SCIP_LP* lp, /**< current LP data */ 319 SCIP_Real cutoffbound, /**< new cutoff bound */ 320 SCIP_Bool useforobjlimit /**< should the cutoff bound be used to update the objective limit, if 321 * better? */ 322 ) 323 { 324 assert(primal != NULL); 325 assert(cutoffbound <= SCIPsetInfinity(set)); 326 assert(cutoffbound <= primal->upperbound); 327 assert(transprob != NULL); 328 assert(origprob != NULL); 329 330 if( cutoffbound < primal->cutoffbound ) 331 { 332 if( useforobjlimit ) 333 { 334 SCIP_Real objval; 335 336 objval = SCIPprobExternObjval(transprob, origprob, set, cutoffbound); 337 338 if( objval < SCIPprobGetObjlim(origprob, set) ) 339 { 340 SCIPsetDebugMsg(set, "changing cutoff bound from %g to %g changes objective limit from %g to %g\n", 341 primal->cutoffbound, cutoffbound, SCIPprobGetObjlim(origprob, set), objval); 342 SCIPprobSetObjlim(origprob, objval); 343 SCIPprobSetObjlim(transprob, objval); 344 } 345 } 346 347 /* update cutoff bound */ 348 SCIP_CALL( primalSetCutoffbound(primal, blkmem, set, stat, transprob, eventfilter, eventqueue, tree, reopt, lp, cutoffbound) ); 349 } 350 else if( cutoffbound > primal->cutoffbound ) 351 { 352 SCIPerrorMessage("invalid increase in cutoff bound\n"); 353 return SCIP_INVALIDDATA; 354 } 355 356 return SCIP_OKAY; 357 } 358 359 /** sets upper bound in primal data and in LP solver */ 360 static 361 SCIP_RETCODE primalSetUpperbound( 362 SCIP_PRIMAL* primal, /**< primal data */ 363 BMS_BLKMEM* blkmem, /**< block memory */ 364 SCIP_SET* set, /**< global SCIP settings */ 365 SCIP_STAT* stat, /**< problem statistics data */ 366 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 367 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 368 SCIP_PROB* prob, /**< transformed problem after presolve */ 369 SCIP_TREE* tree, /**< branch and bound tree */ 370 SCIP_REOPT* reopt, /**< reoptimization data structure */ 371 SCIP_LP* lp, /**< current LP data */ 372 SCIP_Real upperbound /**< new upper bound */ 373 ) 374 { 375 SCIP_Real cutoffbound; 376 377 assert(primal != NULL); 378 assert(stat != NULL); 379 assert(upperbound <= SCIPsetInfinity(set)); 380 assert(upperbound <= primal->upperbound || stat->nnodes == 0); 381 382 SCIPsetDebugMsg(set, "changing upper bound from %g to %g\n", primal->upperbound, upperbound); 383 384 primal->upperbound = upperbound; 385 386 /* if objective value is always integral, the cutoff bound can be reduced to nearly the previous integer number */ 387 if( SCIPprobIsObjIntegral(prob) && !SCIPsetIsInfinity(set, upperbound) ) 388 { 389 SCIP_Real delta; 390 391 delta = SCIPsetCutoffbounddelta(set); 392 393 cutoffbound = SCIPsetFeasCeil(set, upperbound) - (1.0 - delta); 394 cutoffbound = MIN(cutoffbound, upperbound); /* SCIPsetFeasCeil() can increase bound by almost 1.0 due to numerics 395 * and very large upperbound value */ 396 } 397 else 398 cutoffbound = upperbound; 399 400 /* update cutoff bound */ 401 if( cutoffbound < primal->cutoffbound ) 402 { 403 SCIP_CALL( primalSetCutoffbound(primal, blkmem, set, stat, prob, eventfilter, eventqueue, tree, reopt, lp, cutoffbound) ); 404 } 405 406 /* update upper bound in visualization output */ 407 if( SCIPtreeGetCurrentDepth(tree) >= 0 ) 408 { 409 SCIPvisualUpperbound(stat->visual, set, stat, primal->upperbound); 410 } 411 412 return SCIP_OKAY; 413 } 414 415 /** sets upper bound in primal data and in LP solver */ 416 SCIP_RETCODE SCIPprimalSetUpperbound( 417 SCIP_PRIMAL* primal, /**< primal data */ 418 BMS_BLKMEM* blkmem, /**< block memory */ 419 SCIP_SET* set, /**< global SCIP settings */ 420 SCIP_STAT* stat, /**< problem statistics data */ 421 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 422 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 423 SCIP_PROB* prob, /**< transformed problem after presolve */ 424 SCIP_TREE* tree, /**< branch and bound tree */ 425 SCIP_REOPT* reopt, /**< reoptimization data structure */ 426 SCIP_LP* lp, /**< current LP data */ 427 SCIP_Real upperbound /**< new upper bound */ 428 ) 429 { 430 assert(primal != NULL); 431 assert(upperbound <= SCIPsetInfinity(set)); 432 433 if( upperbound < primal->upperbound ) 434 { 435 /* update primal bound */ 436 SCIP_CALL( primalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, prob, tree, reopt, lp, upperbound) ); 437 } 438 else if( upperbound > primal->upperbound ) 439 { 440 SCIPerrorMessage("invalid increase in upper bound\n"); 441 return SCIP_INVALIDDATA; 442 } 443 444 return SCIP_OKAY; 445 } 446 447 /** updates upper bound and cutoff bound in primal data after a tightening of the problem's objective limit */ 448 SCIP_RETCODE SCIPprimalUpdateObjlimit( 449 SCIP_PRIMAL* primal, /**< primal data */ 450 BMS_BLKMEM* blkmem, /**< block memory */ 451 SCIP_SET* set, /**< global SCIP settings */ 452 SCIP_STAT* stat, /**< problem statistics data */ 453 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 454 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 455 SCIP_PROB* transprob, /**< transformed problem data */ 456 SCIP_PROB* origprob, /**< original problem data */ 457 SCIP_TREE* tree, /**< branch and bound tree */ 458 SCIP_REOPT* reopt, /**< reoptimization data structure */ 459 SCIP_LP* lp /**< current LP data */ 460 ) 461 { 462 SCIP_Real objlimit; 463 SCIP_Real inf; 464 465 assert(primal != NULL); 466 467 /* get internal objective limit */ 468 objlimit = SCIPprobInternObjval(transprob, origprob, set, SCIPprobGetObjlim(origprob, set)); 469 inf = SCIPsetInfinity(set); 470 objlimit = MIN(objlimit, inf); 471 472 /* update the cutoff bound */ 473 if( objlimit < primal->cutoffbound ) 474 { 475 SCIP_CALL( primalSetCutoffbound(primal, blkmem, set, stat, transprob, eventfilter, eventqueue, tree, reopt, lp, objlimit) ); 476 } 477 478 /* set new upper bound (and decrease cutoff bound, if objective value is always integral) */ 479 if( objlimit < primal->upperbound ) 480 { 481 SCIP_CALL( primalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, objlimit) ); 482 } 483 484 return SCIP_OKAY; 485 } 486 487 /** recalculates upper bound and cutoff bound in primal data after a change of the problem's objective offset */ 488 SCIP_RETCODE SCIPprimalUpdateObjoffset( 489 SCIP_PRIMAL* primal, /**< primal data */ 490 BMS_BLKMEM* blkmem, /**< block memory */ 491 SCIP_SET* set, /**< global SCIP settings */ 492 SCIP_STAT* stat, /**< problem statistics data */ 493 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 494 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 495 SCIP_PROB* transprob, /**< tranformed problem data */ 496 SCIP_PROB* origprob, /**< original problem data */ 497 SCIP_TREE* tree, /**< branch and bound tree */ 498 SCIP_REOPT* reopt, /**< reoptimization data structure */ 499 SCIP_LP* lp /**< current LP data */ 500 ) 501 { 502 SCIP_Real upperbound; 503 SCIP_Real inf; 504 505 assert(primal != NULL); 506 assert(SCIPsetGetStage(set) <= SCIP_STAGE_PRESOLVED); 507 508 /* recalculate internal objective limit */ 509 upperbound = SCIPprobInternObjval(transprob, origprob, set, SCIPprobGetObjlim(origprob, set)); 510 inf = SCIPsetInfinity(set); 511 upperbound = MIN(upperbound, inf); 512 513 /* resort current primal solutions */ 514 sortPrimalSols(primal, set, origprob, transprob); 515 516 /* compare objective limit to currently best solution */ 517 if( primal->nsols > 0 ) 518 { 519 SCIP_Real obj; 520 521 assert(SCIPsolIsOriginal(primal->sols[0])); 522 obj = SCIPsolGetObj(primal->sols[0], set, transprob, origprob); 523 524 upperbound = MIN(upperbound, obj); 525 } 526 527 /* invalidate old upper bound */ 528 SCIP_CALL( primalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, SCIPsetInfinity(set)) ); 529 530 /* reset the cutoff bound 531 * 532 * @note we might need to relax the bound since in presolving the objective correction of an 533 * aggregation is still in progress 534 */ 535 SCIP_CALL( primalSetCutoffbound(primal, blkmem, set, stat, transprob, eventfilter, eventqueue, tree, reopt, lp, upperbound) ); 536 537 /* set new upper bound (and decrease cutoff bound, if objective value is always integral) */ 538 SCIP_CALL( primalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, upperbound) ); 539 540 return SCIP_OKAY; 541 } 542 543 /** adds additional objective offset in original space to all existing solution (in original space) */ 544 void SCIPprimalAddOrigObjoffset( 545 SCIP_PRIMAL* primal, /**< primal data */ 546 SCIP_SET* set, /**< global SCIP settings */ 547 SCIP_Real addval /**< additional objective offset in original space */ 548 ) 549 { 550 int i; 551 552 assert(primal != NULL); 553 assert(set != NULL); 554 assert(SCIPsetGetStage(set) == SCIP_STAGE_PROBLEM); 555 556 #ifndef NDEBUG 557 assert(primal->nsols == 0 || SCIPsolGetOrigin(primal->sols[0]) == SCIP_SOLORIGIN_ORIGINAL); 558 559 /* check current order of primal solutions */ 560 for( i = 1; i < primal->nsols; ++i ) 561 { 562 assert(SCIPsolGetOrigin(primal->sols[i]) == SCIP_SOLORIGIN_ORIGINAL); 563 assert(SCIPsetIsLE(set, SCIPsolGetOrigObj(primal->sols[i-1]), SCIPsolGetOrigObj(primal->sols[i]))); 564 } 565 #endif 566 567 /* check current order of primal solutions */ 568 for( i = 0; i < primal->nexistingsols; ++i ) 569 { 570 assert(primal->existingsols[i] != NULL); 571 SCIPsolOrigAddObjval(primal->existingsols[i], addval); 572 } 573 } 574 575 /** returns whether the current primal bound is justified with a feasible primal solution; if not, the primal bound 576 * was set from the user as objective limit 577 */ 578 SCIP_Bool SCIPprimalUpperboundIsSol( 579 SCIP_PRIMAL* primal, /**< primal data */ 580 SCIP_SET* set, /**< global SCIP settings */ 581 SCIP_PROB* transprob, /**< tranformed problem data */ 582 SCIP_PROB* origprob /**< original problem data */ 583 ) 584 { 585 assert(primal != NULL); 586 587 return (primal->nsols > 0 && SCIPsetIsEQ(set, primal->upperbound, SCIPsolGetObj(primal->sols[0], set, transprob, origprob))); 588 } 589 590 /** returns the primal ray thats proves unboundedness */ 591 SCIP_SOL* SCIPprimalGetRay( 592 SCIP_PRIMAL* primal /**< primal data */ 593 ) 594 { 595 assert(primal != NULL); 596 597 return primal->primalray; 598 } 599 600 /** update the primal ray thats proves unboundedness */ 601 SCIP_RETCODE SCIPprimalUpdateRay( 602 SCIP_PRIMAL* primal, /**< primal data */ 603 SCIP_SET* set, /**< global SCIP settings */ 604 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 605 SCIP_SOL* primalray, /**< the new primal ray */ 606 BMS_BLKMEM* blkmem /**< block memory */ 607 ) 608 { 609 assert(primal != NULL); 610 assert(set != NULL); 611 assert(stat != NULL); 612 assert(primalray != NULL); 613 assert(blkmem != NULL); 614 615 /* clear previously stored primal ray, if any */ 616 if( primal->primalray != NULL ) 617 { 618 SCIP_CALL( SCIPsolFree(&primal->primalray, blkmem, primal) ); 619 } 620 621 assert(primal->primalray == NULL); 622 623 SCIP_CALL( SCIPsolCopy(&primal->primalray, blkmem, set, stat, primal, primalray) ); 624 625 return SCIP_OKAY; 626 } 627 628 /** adds primal solution to solution storage at given position */ 629 static 630 SCIP_RETCODE primalAddSol( 631 SCIP_PRIMAL* primal, /**< primal data */ 632 BMS_BLKMEM* blkmem, /**< block memory */ 633 SCIP_SET* set, /**< global SCIP settings */ 634 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 635 SCIP_STAT* stat, /**< problem statistics data */ 636 SCIP_PROB* origprob, /**< original problem */ 637 SCIP_PROB* transprob, /**< transformed problem after presolve */ 638 SCIP_TREE* tree, /**< branch and bound tree */ 639 SCIP_REOPT* reopt, /**< reoptimization data structure */ 640 SCIP_LP* lp, /**< current LP data */ 641 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 642 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 643 SCIP_SOL** solptr, /**< pointer to primal CIP solution */ 644 int insertpos, /**< position in solution storage to add solution to */ 645 SCIP_Bool replace /**< should the solution at insertpos be replaced by the new solution? */ 646 ) 647 { 648 SCIP_SOL* sol; 649 /* cppcheck-suppress unassignedVariable */ 650 SCIP_EVENT event; 651 SCIP_Real obj; 652 int pos; 653 654 assert(primal != NULL); 655 assert(set != NULL); 656 assert(solptr != NULL); 657 assert(stat != NULL); 658 assert(transprob != NULL); 659 assert(origprob != NULL); 660 assert(0 <= insertpos && insertpos < set->limit_maxsol); 661 assert(tree == NULL || !SCIPtreeInRepropagation(tree)); 662 663 sol = *solptr; 664 assert(sol != NULL); 665 666 /* if the solution is added during presolving and it is not defined on original variables, 667 * presolving operations will destroy its validity, so we retransform it to the original space 668 */ 669 if( set->stage < SCIP_STAGE_PRESOLVED && !SCIPsolIsOriginal(sol) ) 670 { 671 SCIP_Bool hasinfval; 672 673 SCIP_CALL( SCIPsolUnlink(sol, set, transprob) ); 674 SCIP_CALL( SCIPsolRetransform(sol, set, stat, origprob, transprob, &hasinfval) ); 675 } 676 677 obj = SCIPsolGetObj(sol, set, transprob, origprob); 678 679 SCIPsetDebugMsg(set, "insert primal solution %p with obj %g at position %d (replace=%u):\n", 680 (void*)sol, obj, insertpos, replace); 681 682 /* make sure that the primal bound is at least the lower bound */ 683 if( ! SCIPsetIsInfinity(set, obj) && ! SCIPsetIsInfinity(set, -SCIPgetLowerbound(set->scip)) && SCIPsetIsFeasGT(set, SCIPgetLowerbound(set->scip), obj) ) 684 { 685 if( origprob->objsense == SCIP_OBJSENSE_MINIMIZE ) 686 { 687 SCIPmessagePrintWarning(messagehdlr, "Dual bound %g is larger than the objective of the primal solution %g. The solution might not be optimal.\n", 688 SCIPprobExternObjval(transprob, origprob, set, SCIPgetLowerbound(set->scip)), SCIPprobExternObjval(transprob, origprob, set, obj)); 689 } 690 else 691 { 692 SCIPmessagePrintWarning(messagehdlr, "Dual bound %g is smaller than the objective of the primal solution %g. The solution might not be optimal.\n", 693 SCIPprobExternObjval(transprob, origprob, set, SCIPgetLowerbound(set->scip)), SCIPprobExternObjval(transprob, origprob, set, obj)); 694 } 695 #ifdef WITH_DEBUG_SOLUTION 696 SCIPABORT(); 697 #endif 698 } 699 700 SCIPdebug( SCIP_CALL( SCIPsolPrint(sol, set, messagehdlr, stat, transprob, NULL, NULL, FALSE, FALSE) ) ); 701 702 #if 0 /* this is not a valid debug check, but can be used to track down numerical troubles */ 703 #ifndef NDEBUG 704 /* check solution again completely 705 * it fail for different reasons: 706 * - in the LP solver, the feasibility tolerance is a relative measure against the row's norm 707 * - in SCIP, the feasibility tolerance is a relative measure against the row's rhs/lhs 708 * - the rhs/lhs of a row might drastically change during presolving when variables are fixed or (multi-)aggregated 709 */ 710 if( !SCIPsolIsOriginal(sol) ) 711 { 712 SCIP_Bool feasible; 713 714 SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, TRUE, TRUE, TRUE, TRUE, &feasible) ); 715 716 if( !feasible ) 717 { 718 SCIPerrorMessage("infeasible solution accepted:\n"); 719 SCIP_CALL( SCIPsolPrint(sol, set, messagehdlr, stat, origprob, transprob, NULL, FALSE, FALSE) ); 720 } 721 assert(feasible); 722 } 723 #endif 724 #endif 725 726 /* completely fill the solution's own value array to unlink it from the LP or pseudo solution */ 727 SCIP_CALL( SCIPsolUnlink(sol, set, transprob) ); 728 729 /* allocate memory for solution storage */ 730 SCIP_CALL( ensureSolsSize(primal, set, set->limit_maxsol) ); 731 732 /* if set->limit_maxsol was decreased in the meantime, free all solutions exceeding the limit */ 733 for( pos = set->limit_maxsol; pos < primal->nsols; ++pos ) 734 { 735 SCIP_CALL( SCIPsolFree(&primal->sols[pos], blkmem, primal) ); 736 } 737 primal->nsols = MIN(primal->nsols, set->limit_maxsol); 738 739 /* if the solution should replace an existing one, free this solution, otherwise, 740 * free the last solution if the solution storage is full; 741 */ 742 if( replace ) 743 { 744 SCIP_CALL( SCIPsolTransform(primal->sols[insertpos], solptr, blkmem, set, primal) ); 745 sol = primal->sols[insertpos]; 746 } 747 else 748 { 749 if( primal->nsols == set->limit_maxsol ) 750 { 751 SCIP_CALL( SCIPsolFree(&primal->sols[set->limit_maxsol - 1], blkmem, primal) ); 752 } 753 else 754 { 755 primal->nsols = primal->nsols + 1; 756 assert(primal->nsols <= set->limit_maxsol); 757 } 758 759 /* move all solutions with worse objective value than the new solution */ 760 for( pos = primal->nsols-1; pos > insertpos; --pos ) 761 primal->sols[pos] = primal->sols[pos-1]; 762 763 /* insert solution at correct position */ 764 assert(0 <= insertpos && insertpos < primal->nsols); 765 primal->sols[insertpos] = sol; 766 primal->nsolsfound++; 767 768 /* check if solution is better than objective limit */ 769 if( SCIPsetIsFeasLE(set, obj, SCIPprobInternObjval(transprob, origprob, set, SCIPprobGetObjlim(origprob, set))) ) 770 primal->nlimsolsfound++; 771 } 772 773 /* if its the first primal solution, store the relevant statistics */ 774 if( primal->nsolsfound == 1 ) 775 { 776 SCIP_Real primalsolval; 777 778 stat->nnodesbeforefirst = SCIPsolGetNodenum(sol); 779 stat->nrunsbeforefirst = SCIPsolGetRunnum(sol); 780 stat->firstprimalheur = SCIPsolGetHeur(sol); 781 stat->firstprimaltime = SCIPsolGetTime(sol); 782 stat->firstprimaldepth = SCIPsolGetDepth(sol); 783 784 primalsolval = obj; 785 stat->firstprimalbound = SCIPprobExternObjval(transprob, origprob, set, primalsolval); 786 787 SCIPsetDebugMsg(set, "First Solution stored in problem specific statistics.\n"); 788 SCIPsetDebugMsg(set, "-> %" SCIP_LONGINT_FORMAT " nodes, %d runs, %.2g time, %d depth, %.15g objective\n", stat->nnodesbeforefirst, stat->nrunsbeforefirst, 789 stat->firstprimaltime, stat->firstprimaldepth, stat->firstprimalbound); 790 } 791 792 SCIPsetDebugMsg(set, " -> stored at position %d of %d solutions, found %" SCIP_LONGINT_FORMAT " solutions\n", 793 insertpos, primal->nsols, primal->nsolsfound); 794 795 /* update the solution value sums in variables */ 796 if( !SCIPsolIsOriginal(sol) ) 797 { 798 SCIPsolUpdateVarsum(sol, set, stat, transprob, 799 (SCIP_Real)(primal->nsols - insertpos)/(SCIP_Real)(2.0*primal->nsols - 1.0)); 800 } 801 802 /* change color of node in visualization output */ 803 SCIPvisualFoundSolution(stat->visual, set, stat, SCIPtreeGetCurrentNode(tree), insertpos == 0 ? TRUE : FALSE, sol); 804 805 /* check, if the global upper bound has to be updated */ 806 if( obj < primal->cutoffbound && insertpos == 0 ) 807 { 808 /* update the upper bound */ 809 SCIP_CALL( SCIPprimalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, obj) ); 810 811 /* issue BESTSOLFOUND event */ 812 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_BESTSOLFOUND) ); 813 primal->nbestsolsfound++; 814 stat->bestsolnode = stat->nnodes; 815 816 if( set->limit_objstop != SCIP_INVALID ) /*lint !e777*/ 817 { 818 SCIP_Real origobj; 819 820 if( !SCIPsolIsOriginal(sol) ) 821 { 822 SCIP_Bool hasinfval; 823 SCIP_CALL( SCIPsolRetransform(sol, set, stat, origprob, transprob, &hasinfval) ); 824 } 825 origobj = SCIPsolGetOrigObj(sol); 826 827 if( SCIPsetIsLE(set, origobj * (int) origprob->objsense, set->limit_objstop * (int) origprob->objsense) ) 828 { 829 SCIPmessagePrintInfo(messagehdlr, "interrupting solve because objective stop was reached. \n"); 830 stat->userinterrupt = TRUE; 831 } 832 } 833 } 834 else 835 { 836 /* issue POORSOLFOUND event */ 837 SCIP_CALL( SCIPeventChgType(&event, SCIP_EVENTTYPE_POORSOLFOUND) ); 838 } 839 SCIP_CALL( SCIPeventChgSol(&event, sol) ); 840 SCIP_CALL( SCIPeventProcess(&event, set, NULL, NULL, NULL, eventfilter) ); 841 842 /* display node information line */ 843 if( insertpos == 0 && !replace && set->stage >= SCIP_STAGE_SOLVING ) 844 { 845 SCIP_CALL( SCIPdispPrintLine(set, messagehdlr, stat, NULL, TRUE, TRUE) ); 846 } 847 848 /* if an original solution was added during solving, try to transfer it to the transformed space */ 849 if( SCIPsolIsOriginal(sol) && SCIPsetGetStage(set) == SCIP_STAGE_SOLVING && set->misc_transorigsols ) 850 { 851 SCIP_Bool added; 852 853 SCIP_CALL( SCIPprimalTransformSol(primal, sol, blkmem, set, messagehdlr, stat, origprob, transprob, tree, reopt, 854 lp, eventqueue, eventfilter, NULL, NULL, 0, &added) ); 855 856 SCIPsetDebugMsg(set, "original solution %p was successfully transferred to the transformed problem space\n", 857 (void*)sol); 858 } /*lint !e438*/ 859 860 return SCIP_OKAY; 861 } 862 863 /** adds primal solution to solution storage at given position */ 864 static 865 SCIP_RETCODE primalAddOrigSol( 866 SCIP_PRIMAL* primal, /**< primal data */ 867 BMS_BLKMEM* blkmem, /**< block memory */ 868 SCIP_SET* set, /**< global SCIP settings */ 869 SCIP_PROB* prob, /**< original problem data */ 870 SCIP_SOL* sol, /**< primal CIP solution */ 871 int insertpos /**< position in solution storage to add solution to */ 872 ) 873 { 874 int pos; 875 876 assert(primal != NULL); 877 assert(set != NULL); 878 assert(prob != NULL); 879 assert(sol != NULL); 880 assert(0 <= insertpos && insertpos < set->limit_maxorigsol); 881 assert(!set->reopt_enable); 882 883 SCIPsetDebugMsg(set, "insert primal solution candidate %p with obj %g at position %d:\n", (void*)sol, SCIPsolGetOrigObj(sol), insertpos); 884 885 /* allocate memory for solution storage */ 886 SCIP_CALL( ensureSolsSize(primal, set, set->limit_maxorigsol) ); 887 888 /* if the solution storage is full, free the last solution(s) 889 * more than one solution may be freed, if set->limit_maxorigsol was decreased in the meantime 890 */ 891 for( pos = set->limit_maxorigsol-1; pos < primal->nsols; ++pos ) 892 { 893 SCIP_CALL( SCIPsolFree(&primal->sols[pos], blkmem, primal) ); 894 } 895 896 /* insert solution at correct position */ 897 primal->nsols = MIN(primal->nsols+1, set->limit_maxorigsol); 898 for( pos = primal->nsols-1; pos > insertpos; --pos ) 899 primal->sols[pos] = primal->sols[pos-1]; 900 901 assert(0 <= insertpos && insertpos < primal->nsols); 902 primal->sols[insertpos] = sol; 903 primal->nsolsfound++; 904 905 /* check if solution is better than objective limit */ 906 if( SCIPsetIsFeasLE(set, SCIPsolGetOrigObj(sol), SCIPprobGetObjlim(prob, set)) ) 907 primal->nlimsolsfound++; 908 909 SCIPsetDebugMsg(set, " -> stored at position %d of %d solutions, found %" SCIP_LONGINT_FORMAT " solutions\n", 910 insertpos, primal->nsols, primal->nsolsfound); 911 912 return SCIP_OKAY; 913 } 914 915 /** adds primal solution to solution storage */ 916 static 917 SCIP_RETCODE primalAddOrigPartialSol( 918 SCIP_PRIMAL* primal, /**< primal data */ 919 SCIP_SET* set, /**< global SCIP settings */ 920 SCIP_PROB* prob, /**< original problem data */ 921 SCIP_SOL* sol /**< primal CIP solution */ 922 ) 923 { /*lint --e{715}*/ 924 assert(primal != NULL); 925 assert(set != NULL); 926 assert(prob != NULL); 927 assert(sol != NULL); 928 929 if( primal->npartialsols >= set->limit_maxorigsol ) 930 { 931 SCIPerrorMessage("Cannot add partial solution to storage: limit reached.\n"); 932 return SCIP_INVALIDCALL; 933 } 934 935 SCIPsetDebugMsg(set, "insert partial solution candidate %p:\n", (void*)sol); 936 937 /* allocate memory for solution storage */ 938 SCIP_CALL( ensurePartialsolsSize(primal, set, primal->npartialsols+1) ); 939 940 primal->partialsols[primal->npartialsols] = sol; 941 ++primal->npartialsols; 942 943 return SCIP_OKAY; 944 } 945 946 /** uses binary search to find position in solution storage */ 947 static 948 int primalSearchSolPos( 949 SCIP_PRIMAL* primal, /**< primal data */ 950 SCIP_SET* set, /**< global SCIP settings */ 951 SCIP_PROB* transprob, /**< tranformed problem data */ 952 SCIP_PROB* origprob, /**< original problem data */ 953 SCIP_SOL* sol /**< primal solution to search position for */ 954 ) 955 { 956 SCIP_SOL** sols; 957 SCIP_Real obj; 958 SCIP_Real middleobj; 959 int left; 960 int right; 961 int middle; 962 963 assert(primal != NULL); 964 965 obj = SCIPsolGetObj(sol, set, transprob, origprob); 966 sols = primal->sols; 967 968 left = -1; 969 right = primal->nsols; 970 while( left < right-1 ) 971 { 972 middle = (left+right)/2; 973 assert(left < middle && middle < right); 974 assert(0 <= middle && middle < primal->nsols); 975 976 middleobj = SCIPsolGetObj(sols[middle], set, transprob, origprob); 977 978 if( obj < middleobj ) 979 right = middle; 980 else 981 left = middle; 982 } 983 assert(left == right-1); 984 985 /* prefer solutions that live in the transformed space */ 986 if( !SCIPsolIsOriginal(sol) ) 987 { 988 while( right > 0 && SCIPsolIsOriginal(sols[right-1]) 989 && SCIPsetIsEQ(set, SCIPsolGetObj(sols[right-1], set, transprob, origprob), obj) ) 990 --right; 991 } 992 993 return right; 994 } 995 996 /** uses binary search to find position in solution storage */ 997 static 998 int primalSearchOrigSolPos( 999 SCIP_PRIMAL* primal, /**< primal data */ 1000 SCIP_SOL* sol /**< primal solution to search position for */ 1001 ) 1002 { 1003 SCIP_Real obj; 1004 SCIP_Real middleobj; 1005 int left; 1006 int right; 1007 int middle; 1008 1009 assert(primal != NULL); 1010 1011 obj = SCIPsolGetOrigObj(sol); 1012 1013 left = -1; 1014 right = primal->nsols; 1015 while( left < right-1 ) 1016 { 1017 middle = (left+right)/2; 1018 assert(left < middle && middle < right); 1019 assert(0 <= middle && middle < primal->nsols); 1020 middleobj = SCIPsolGetOrigObj(primal->sols[middle]); 1021 if( obj < middleobj ) 1022 right = middle; 1023 else 1024 left = middle; 1025 } 1026 assert(left == right-1); 1027 1028 return right; 1029 } 1030 1031 /** returns whether the given primal solution is already existent in the solution storage */ 1032 static 1033 SCIP_Bool primalExistsSol( 1034 SCIP_PRIMAL* primal, /**< primal data */ 1035 SCIP_SET* set, /**< global SCIP settings */ 1036 SCIP_STAT* stat, /**< problem statistics data */ 1037 SCIP_PROB* origprob, /**< original problem */ 1038 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1039 SCIP_SOL* sol, /**< primal solution to search position for */ 1040 int* insertpos, /**< pointer to insertion position returned by primalSearchSolPos(); the 1041 * position might be changed if an existing solution should be replaced */ 1042 SCIP_Bool* replace /**< pointer to store whether the solution at insertpos should be replaced */ 1043 ) 1044 { 1045 SCIP_Real obj; 1046 int i; 1047 1048 assert(primal != NULL); 1049 assert(insertpos != NULL); 1050 assert(replace != NULL); 1051 assert(0 <= (*insertpos) && (*insertpos) <= primal->nsols); 1052 1053 obj = SCIPsolGetObj(sol, set, transprob, origprob); 1054 1055 assert(primal->sols != NULL || primal->nsols == 0); 1056 assert(primal->sols != NULL || (*insertpos) == 0); 1057 1058 /* search in the better solutions */ 1059 for( i = (*insertpos)-1; i >= 0; --i ) 1060 { 1061 SCIP_Real solobj; 1062 1063 solobj = SCIPsolGetObj(primal->sols[i], set, transprob, origprob); 1064 1065 /* due to transferring the objective value of transformed solutions to the original space, small numerical errors might occur 1066 * which can lead to SCIPsetIsLE() failing in case of high absolute numbers 1067 */ 1068 assert(SCIPsetIsLE(set, solobj, obj) || (REALABS(obj) > 1e+13 * SCIPsetEpsilon(set) && SCIPsetIsFeasLE(set, solobj, obj))); 1069 1070 if( SCIPsetIsLT(set, solobj, obj) ) 1071 break; 1072 1073 if( SCIPsolsAreEqual(sol, primal->sols[i], set, stat, origprob, transprob) ) 1074 { 1075 if( set->stage >= SCIP_STAGE_PRESOLVED && SCIPsolIsOriginal(primal->sols[i]) && !SCIPsolIsOriginal(sol) ) 1076 { 1077 (*insertpos) = i; 1078 (*replace) = TRUE; 1079 } 1080 return TRUE; 1081 } 1082 } 1083 1084 /* search in the worse solutions */ 1085 for( i = (*insertpos); i < primal->nsols; ++i ) 1086 { 1087 SCIP_Real solobj; 1088 1089 solobj = SCIPsolGetObj(primal->sols[i], set, transprob, origprob); 1090 1091 /* due to transferring the objective value of transformed solutions to the original space, small numerical errors might occur 1092 * which can lead to SCIPsetIsLE() failing in case of high absolute numbers 1093 */ 1094 assert( SCIPsetIsGE(set, solobj, obj) || (REALABS(obj) > 1e+13 * SCIPsetEpsilon(set) && SCIPsetIsFeasGE(set, solobj, obj))); 1095 1096 if( SCIPsetIsGT(set, solobj, obj) ) 1097 break; 1098 1099 if( SCIPsolsAreEqual(sol, primal->sols[i], set, stat, origprob, transprob) ) 1100 { 1101 if( set->stage >= SCIP_STAGE_PRESOLVED && SCIPsolIsOriginal(primal->sols[i]) && !SCIPsolIsOriginal(sol) ) 1102 { 1103 (*insertpos) = i; 1104 (*replace) = TRUE; 1105 } 1106 return TRUE; 1107 } 1108 } 1109 1110 return FALSE; 1111 } 1112 1113 /** returns whether the given primal solution is already existent in the original solution candidate storage */ 1114 static 1115 SCIP_Bool primalExistsOrigSol( 1116 SCIP_PRIMAL* primal, /**< primal data */ 1117 SCIP_SET* set, /**< global SCIP settings */ 1118 SCIP_STAT* stat, /**< problem statistics data */ 1119 SCIP_PROB* prob, /**< original problem */ 1120 SCIP_SOL* sol, /**< primal solution to search position for */ 1121 int insertpos /**< insertion position returned by primalSearchOrigSolPos() */ 1122 ) 1123 { 1124 SCIP_Real obj; 1125 int i; 1126 1127 assert(primal != NULL); 1128 assert(0 <= insertpos && insertpos <= primal->nsols); 1129 1130 obj = SCIPsolGetOrigObj(sol); 1131 1132 /* search in the better solutions */ 1133 for( i = insertpos-1; i >= 0; --i ) 1134 { 1135 SCIP_Real solobj; 1136 1137 solobj = SCIPsolGetOrigObj(primal->sols[i]); 1138 assert( SCIPsetIsLE(set, solobj, obj) ); 1139 1140 if( SCIPsetIsLT(set, solobj, obj) ) 1141 break; 1142 1143 if( SCIPsolsAreEqual(sol, primal->sols[i], set, stat, prob, NULL) ) 1144 return TRUE; 1145 } 1146 1147 /* search in the worse solutions */ 1148 for( i = insertpos; i < primal->nsols; ++i ) 1149 { 1150 SCIP_Real solobj; 1151 1152 solobj = SCIPsolGetOrigObj(primal->sols[i]); 1153 assert( SCIPsetIsGE(set, solobj, obj) ); 1154 1155 if( SCIPsetIsGT(set, solobj, obj) ) 1156 break; 1157 1158 if( SCIPsolsAreEqual(sol, primal->sols[i], set, stat, prob, NULL) ) 1159 return TRUE; 1160 } 1161 1162 return FALSE; 1163 } 1164 1165 /** check if we are willing to check the solution for feasibility */ 1166 static 1167 SCIP_Bool solOfInterest( 1168 SCIP_PRIMAL* primal, /**< primal data */ 1169 SCIP_SET* set, /**< global SCIP settings */ 1170 SCIP_STAT* stat, /**< problem statistics data */ 1171 SCIP_PROB* origprob, /**< original problem */ 1172 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1173 SCIP_SOL* sol, /**< primal CIP solution */ 1174 int* insertpos, /**< pointer to store the insert position of that solution */ 1175 SCIP_Bool* replace /**< pointer to store whether the solution at insertpos should be replaced 1176 * (e.g., because it lives in the original space) */ 1177 ) 1178 { 1179 SCIP_Real obj; 1180 1181 obj = SCIPsolGetObj(sol, set, transprob, origprob); 1182 1183 /* check if we are willing to check worse solutions; a solution is better if the objective is smaller than the 1184 * current cutoff bound; solutions with infinite objective value are never accepted 1185 */ 1186 if( (!set->misc_improvingsols || obj < primal->cutoffbound) && !SCIPsetIsInfinity(set, obj) ) 1187 { 1188 /* find insert position for the solution */ 1189 (*insertpos) = primalSearchSolPos(primal, set, transprob, origprob, sol); 1190 (*replace) = FALSE; 1191 1192 /* the solution should be added, if the insertpos is smaller than the maximum number of solutions to be stored 1193 * and it does not already exist or it does exist, but the existing solution should be replaced by the new one 1194 */ 1195 if( (*insertpos) < set->limit_maxsol && 1196 (!primalExistsSol(primal, set, stat, origprob, transprob, sol, insertpos, replace) || (*replace)) ) 1197 return TRUE; 1198 } 1199 1200 return FALSE; 1201 } 1202 1203 /** check if we are willing to store the solution candidate for later checking */ 1204 static 1205 SCIP_Bool origsolOfInterest( 1206 SCIP_PRIMAL* primal, /**< primal data */ 1207 SCIP_SET* set, /**< global SCIP settings */ 1208 SCIP_STAT* stat, /**< problem statistics data */ 1209 SCIP_PROB* origprob, /**< original problem */ 1210 SCIP_SOL* sol, /**< primal CIP solution */ 1211 int* insertpos /**< pointer to store the insert position of that solution */ 1212 ) 1213 { 1214 assert(SCIPsolIsOriginal(sol)); 1215 1216 /* find insert position for the solution */ 1217 (*insertpos) = primalSearchOrigSolPos(primal, sol); 1218 1219 if( !set->reopt_enable && (*insertpos) < set->limit_maxorigsol && !primalExistsOrigSol(primal, set, stat, origprob, sol, *insertpos) ) 1220 return TRUE; 1221 1222 return FALSE; 1223 } 1224 1225 /** adds primal solution to solution storage by copying it */ 1226 SCIP_RETCODE SCIPprimalAddSol( 1227 SCIP_PRIMAL* primal, /**< primal data */ 1228 BMS_BLKMEM* blkmem, /**< block memory */ 1229 SCIP_SET* set, /**< global SCIP settings */ 1230 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1231 SCIP_STAT* stat, /**< problem statistics data */ 1232 SCIP_PROB* origprob, /**< original problem */ 1233 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1234 SCIP_TREE* tree, /**< branch and bound tree */ 1235 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1236 SCIP_LP* lp, /**< current LP data */ 1237 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1238 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 1239 SCIP_SOL* sol, /**< primal CIP solution */ 1240 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 1241 ) 1242 { 1243 SCIP_Bool replace; 1244 int insertpos; 1245 1246 assert(primal != NULL); 1247 assert(blkmem != NULL); 1248 assert(set != NULL); 1249 assert(messagehdlr != NULL); 1250 assert(stat != NULL); 1251 assert(origprob != NULL); 1252 assert(transprob != NULL); 1253 assert(tree != NULL); 1254 assert(lp != NULL); 1255 assert(eventqueue != NULL); 1256 assert(eventfilter != NULL); 1257 assert(sol != NULL); 1258 assert(stored != NULL); 1259 1260 insertpos = -1; 1261 1262 assert(!SCIPsolIsPartial(sol)); 1263 1264 if( solOfInterest(primal, set, stat, origprob, transprob, sol, &insertpos, &replace) ) 1265 { 1266 SCIP_SOL* solcopy; 1267 #ifdef SCIP_MORE_DEBUG 1268 int i; 1269 #endif 1270 1271 assert(insertpos >= 0 && insertpos < set->limit_maxsol); 1272 1273 /* create a copy of the solution */ 1274 SCIP_CALL( SCIPsolCopy(&solcopy, blkmem, set, stat, primal, sol) ); 1275 1276 /* insert copied solution into solution storage */ 1277 SCIP_CALL( primalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, 1278 tree, reopt, lp, eventqueue, eventfilter, &solcopy, insertpos, replace) ); 1279 #ifdef SCIP_MORE_DEBUG 1280 for( i = 0; i < primal->nsols - 1; ++i ) 1281 { 1282 assert(SCIPsetIsLE(set, SCIPsolGetObj(primal->sols[i], set, transprob, origprob), SCIPsolGetObj(primal->sols[i+1], set, transprob, origprob))); 1283 } 1284 #endif 1285 *stored = TRUE; 1286 } 1287 else 1288 *stored = FALSE; 1289 1290 return SCIP_OKAY; 1291 } 1292 1293 /** adds primal solution to solution storage, frees the solution afterwards */ 1294 SCIP_RETCODE SCIPprimalAddSolFree( 1295 SCIP_PRIMAL* primal, /**< primal data */ 1296 BMS_BLKMEM* blkmem, /**< block memory */ 1297 SCIP_SET* set, /**< global SCIP settings */ 1298 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1299 SCIP_STAT* stat, /**< problem statistics data */ 1300 SCIP_PROB* origprob, /**< original problem */ 1301 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1302 SCIP_TREE* tree, /**< branch and bound tree */ 1303 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1304 SCIP_LP* lp, /**< current LP data */ 1305 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1306 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 1307 SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */ 1308 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 1309 ) 1310 { 1311 SCIP_Bool replace; 1312 int insertpos; 1313 1314 assert(primal != NULL); 1315 assert(transprob != NULL); 1316 assert(origprob != NULL); 1317 assert(sol != NULL); 1318 assert(*sol != NULL); 1319 assert(stored != NULL); 1320 1321 insertpos = -1; 1322 1323 if( solOfInterest(primal, set, stat, origprob, transprob, *sol, &insertpos, &replace) ) 1324 { 1325 assert(insertpos >= 0 && insertpos < set->limit_maxsol); 1326 1327 /* insert solution into solution storage */ 1328 SCIP_CALL( primalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, 1329 tree, reopt, lp, eventqueue, eventfilter, sol, insertpos, replace) ); 1330 1331 /* clear the pointer, such that the user cannot access the solution anymore */ 1332 *sol = NULL; 1333 1334 *stored = TRUE; 1335 } 1336 else 1337 { 1338 /* the solution is too bad -> free it immediately */ 1339 SCIP_CALL( SCIPsolFree(sol, blkmem, primal) ); 1340 1341 *stored = FALSE; 1342 } 1343 assert(*sol == NULL); 1344 1345 return SCIP_OKAY; 1346 } 1347 1348 /** adds primal solution to solution candidate storage of original problem space */ 1349 SCIP_RETCODE SCIPprimalAddOrigSol( 1350 SCIP_PRIMAL* primal, /**< primal data */ 1351 BMS_BLKMEM* blkmem, /**< block memory */ 1352 SCIP_SET* set, /**< global SCIP settings */ 1353 SCIP_STAT* stat, /**< problem statistics data */ 1354 SCIP_PROB* prob, /**< original problem data */ 1355 SCIP_SOL* sol, /**< primal CIP solution; is cleared in function call */ 1356 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 1357 ) 1358 { 1359 int insertpos; 1360 1361 assert(primal != NULL); 1362 assert(blkmem != NULL); 1363 assert(set != NULL); 1364 assert(stat != NULL); 1365 assert(sol != NULL); 1366 assert(SCIPsolIsOriginal(sol)); 1367 assert(stored != NULL); 1368 1369 insertpos = -1; 1370 1371 if( SCIPsolIsPartial(sol) ) 1372 { 1373 SCIP_SOL* solcopy; 1374 1375 /* create a copy of the solution */ 1376 SCIP_CALL( SCIPsolCopy(&solcopy, blkmem, set, stat, primal, sol) ); 1377 1378 SCIP_CALL( primalAddOrigPartialSol(primal, set, prob, solcopy) ); 1379 1380 *stored = TRUE; 1381 } 1382 else if( origsolOfInterest(primal, set, stat, prob, sol, &insertpos) ) 1383 { 1384 SCIP_SOL* solcopy; 1385 1386 assert(insertpos >= 0 && insertpos < set->limit_maxorigsol); 1387 assert(!set->reopt_enable); 1388 1389 /* create a copy of the solution */ 1390 SCIP_CALL( SCIPsolCopy(&solcopy, blkmem, set, stat, primal, sol) ); 1391 1392 /* insert solution into solution storage */ 1393 SCIP_CALL( primalAddOrigSol(primal, blkmem, set, prob, solcopy, insertpos) ); 1394 1395 *stored = TRUE; 1396 } 1397 else 1398 *stored = FALSE; 1399 1400 return SCIP_OKAY; 1401 } 1402 1403 /** adds primal solution to solution candidate storage of original problem space, frees the solution afterwards */ 1404 SCIP_RETCODE SCIPprimalAddOrigSolFree( 1405 SCIP_PRIMAL* primal, /**< primal data */ 1406 BMS_BLKMEM* blkmem, /**< block memory */ 1407 SCIP_SET* set, /**< global SCIP settings */ 1408 SCIP_STAT* stat, /**< problem statistics data */ 1409 SCIP_PROB* prob, /**< original problem data */ 1410 SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */ 1411 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 1412 ) 1413 { 1414 int insertpos; 1415 1416 assert(primal != NULL); 1417 assert(sol != NULL); 1418 assert(*sol != NULL); 1419 assert(SCIPsolIsOriginal(*sol)); 1420 assert(stored != NULL); 1421 1422 insertpos = -1; 1423 1424 if( SCIPsolIsPartial(*sol) ) 1425 { 1426 /* insert solution into solution storage */ 1427 SCIP_CALL( primalAddOrigPartialSol(primal, set, prob, *sol) ); 1428 1429 /* clear the pointer, such that the user cannot access the solution anymore */ 1430 *sol = NULL; 1431 1432 *stored = TRUE; 1433 } 1434 else if( origsolOfInterest(primal, set, stat, prob, *sol, &insertpos) ) 1435 { 1436 assert(insertpos >= 0 && insertpos < set->limit_maxorigsol); 1437 assert(!set->reopt_enable); 1438 1439 /* insert solution into solution storage */ 1440 SCIP_CALL( primalAddOrigSol(primal, blkmem, set, prob, *sol, insertpos) ); 1441 1442 /* clear the pointer, such that the user cannot access the solution anymore */ 1443 *sol = NULL; 1444 1445 *stored = TRUE; 1446 } 1447 else 1448 { 1449 /* the solution is too bad -> free it immediately */ 1450 SCIP_CALL( SCIPsolFree(sol, blkmem, primal) ); 1451 1452 *stored = FALSE; 1453 } 1454 assert(*sol == NULL); 1455 1456 return SCIP_OKAY; 1457 } 1458 1459 /** links temporary solution of primal data to current solution */ 1460 static 1461 SCIP_RETCODE primalLinkCurrentSol( 1462 SCIP_PRIMAL* primal, /**< primal data */ 1463 BMS_BLKMEM* blkmem, /**< block memory */ 1464 SCIP_SET* set, /**< global SCIP settings */ 1465 SCIP_STAT* stat, /**< problem statistics data */ 1466 SCIP_PROB* prob, /**< transformed problem data */ 1467 SCIP_TREE* tree, /**< branch and bound tree */ 1468 SCIP_LP* lp, /**< current LP data */ 1469 SCIP_HEUR* heur /**< heuristic that found the solution (or NULL if it's from the tree) */ 1470 ) 1471 { 1472 assert(primal != NULL); 1473 1474 if( primal->currentsol == NULL ) 1475 { 1476 SCIP_CALL( SCIPsolCreateCurrentSol(&primal->currentsol, blkmem, set, stat, prob, primal, tree, lp, heur) ); 1477 } 1478 else 1479 { 1480 SCIP_CALL( SCIPsolLinkCurrentSol(primal->currentsol, set, stat, prob, tree, lp) ); 1481 SCIPsolSetHeur(primal->currentsol, heur); 1482 } 1483 1484 return SCIP_OKAY; 1485 } 1486 1487 /** adds current LP/pseudo solution to solution storage */ 1488 SCIP_RETCODE SCIPprimalAddCurrentSol( 1489 SCIP_PRIMAL* primal, /**< primal data */ 1490 BMS_BLKMEM* blkmem, /**< block memory */ 1491 SCIP_SET* set, /**< global SCIP settings */ 1492 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1493 SCIP_STAT* stat, /**< problem statistics data */ 1494 SCIP_PROB* origprob, /**< original problem */ 1495 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1496 SCIP_TREE* tree, /**< branch and bound tree */ 1497 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1498 SCIP_LP* lp, /**< current LP data */ 1499 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1500 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 1501 SCIP_HEUR* heur, /**< heuristic that found the solution (or NULL if it's from the tree) */ 1502 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 1503 ) 1504 { 1505 assert(primal != NULL); 1506 1507 /* link temporary solution to current solution */ 1508 SCIP_CALL( primalLinkCurrentSol(primal, blkmem, set, stat, transprob, tree, lp, heur) ); 1509 1510 /* add solution to solution storage */ 1511 SCIP_CALL( SCIPprimalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, 1512 tree, reopt, lp, eventqueue, eventfilter, primal->currentsol, stored) ); 1513 1514 return SCIP_OKAY; 1515 } 1516 1517 /** checks primal solution; if feasible, adds it to storage by copying it */ 1518 SCIP_RETCODE SCIPprimalTrySol( 1519 SCIP_PRIMAL* primal, /**< primal data */ 1520 BMS_BLKMEM* blkmem, /**< block memory */ 1521 SCIP_SET* set, /**< global SCIP settings */ 1522 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1523 SCIP_STAT* stat, /**< problem statistics data */ 1524 SCIP_PROB* origprob, /**< original problem */ 1525 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1526 SCIP_TREE* tree, /**< branch and bound tree */ 1527 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1528 SCIP_LP* lp, /**< current LP data */ 1529 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1530 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 1531 SCIP_SOL* sol, /**< primal CIP solution */ 1532 SCIP_Bool printreason, /**< Should all reasons of violations be printed? */ 1533 SCIP_Bool completely, /**< Should all violations be checked? */ 1534 SCIP_Bool checkbounds, /**< Should the bounds of the variables be checked? */ 1535 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */ 1536 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */ 1537 SCIP_Bool* stored /**< stores whether given solution was feasible and good enough to keep */ 1538 ) 1539 { 1540 SCIP_Bool feasible; 1541 SCIP_Bool replace; 1542 int insertpos; 1543 1544 assert(primal != NULL); 1545 assert(set != NULL); 1546 assert(transprob != NULL); 1547 assert(origprob != NULL); 1548 assert(tree != NULL); 1549 assert(sol != NULL); 1550 assert(stored != NULL); 1551 1552 /* if we want to solve exactly, the constraint handlers cannot rely on the LP's feasibility */ 1553 checklprows = checklprows || set->misc_exactsolve; 1554 1555 insertpos = -1; 1556 1557 if( solOfInterest(primal, set, stat, origprob, transprob, sol, &insertpos, &replace) ) 1558 { 1559 /* check solution for feasibility */ 1560 SCIP_CALL( SCIPsolCheck(sol, set, messagehdlr, blkmem, stat, transprob, printreason, completely, checkbounds, 1561 checkintegrality, checklprows, &feasible) ); 1562 } 1563 else 1564 feasible = FALSE; 1565 1566 if( feasible ) 1567 { 1568 SCIP_SOL* solcopy; 1569 1570 assert(insertpos >= 0 && insertpos < set->limit_maxsol); 1571 1572 /* create a copy of the solution */ 1573 SCIP_CALL( SCIPsolCopy(&solcopy, blkmem, set, stat, primal, sol) ); 1574 1575 /* insert copied solution into solution storage */ 1576 SCIP_CALL( primalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, 1577 tree, reopt, lp, eventqueue, eventfilter, &solcopy, insertpos, replace) ); 1578 1579 *stored = TRUE; 1580 } 1581 else 1582 *stored = FALSE; 1583 1584 return SCIP_OKAY; 1585 } 1586 1587 /** checks primal solution; if feasible, adds it to storage; solution is freed afterwards */ 1588 SCIP_RETCODE SCIPprimalTrySolFree( 1589 SCIP_PRIMAL* primal, /**< primal data */ 1590 BMS_BLKMEM* blkmem, /**< block memory */ 1591 SCIP_SET* set, /**< global SCIP settings */ 1592 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1593 SCIP_STAT* stat, /**< problem statistics data */ 1594 SCIP_PROB* origprob, /**< original problem */ 1595 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1596 SCIP_TREE* tree, /**< branch and bound tree */ 1597 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1598 SCIP_LP* lp, /**< current LP data */ 1599 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1600 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 1601 SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */ 1602 SCIP_Bool printreason, /**< Should all the reasons of violations be printed? */ 1603 SCIP_Bool completely, /**< Should all violations be checked? */ 1604 SCIP_Bool checkbounds, /**< Should the bounds of the variables be checked? */ 1605 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */ 1606 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */ 1607 SCIP_Bool* stored /**< stores whether solution was feasible and good enough to keep */ 1608 ) 1609 { 1610 SCIP_Bool feasible; 1611 SCIP_Bool replace; 1612 int insertpos; 1613 1614 assert(primal != NULL); 1615 assert(transprob != NULL); 1616 assert(origprob != NULL); 1617 assert(tree != NULL); 1618 assert(sol != NULL); 1619 assert(*sol != NULL); 1620 assert(stored != NULL); 1621 1622 *stored = FALSE; 1623 1624 /* if we want to solve exactly, the constraint handlers cannot rely on the LP's feasibility */ 1625 checklprows = checklprows || set->misc_exactsolve; 1626 1627 insertpos = -1; 1628 1629 if( solOfInterest(primal, set, stat, origprob, transprob, *sol, &insertpos, &replace) ) 1630 { 1631 /* check solution for feasibility */ 1632 SCIP_CALL( SCIPsolCheck(*sol, set, messagehdlr, blkmem, stat, transprob, printreason, completely, checkbounds, 1633 checkintegrality, checklprows, &feasible) ); 1634 } 1635 else 1636 feasible = FALSE; 1637 1638 if( feasible ) 1639 { 1640 assert(insertpos >= 0 && insertpos < set->limit_maxsol); 1641 1642 /* insert solution into solution storage */ 1643 SCIP_CALL( primalAddSol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, 1644 tree, reopt, lp, eventqueue, eventfilter, sol, insertpos, replace) ); 1645 1646 /* clear the pointer, such that the user cannot access the solution anymore */ 1647 *sol = NULL; 1648 *stored = TRUE; 1649 } 1650 else 1651 { 1652 /* the solution is too bad or infeasible -> free it immediately */ 1653 SCIP_CALL( SCIPsolFree(sol, blkmem, primal) ); 1654 *stored = FALSE; 1655 } 1656 assert(*sol == NULL); 1657 1658 return SCIP_OKAY; 1659 } 1660 1661 /** checks current LP/pseudo solution; if feasible, adds it to storage */ 1662 SCIP_RETCODE SCIPprimalTryCurrentSol( 1663 SCIP_PRIMAL* primal, /**< primal data */ 1664 BMS_BLKMEM* blkmem, /**< block memory */ 1665 SCIP_SET* set, /**< global SCIP settings */ 1666 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1667 SCIP_STAT* stat, /**< problem statistics data */ 1668 SCIP_PROB* origprob, /**< original problem */ 1669 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1670 SCIP_TREE* tree, /**< branch and bound tree */ 1671 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1672 SCIP_LP* lp, /**< current LP data */ 1673 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1674 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 1675 SCIP_HEUR* heur, /**< heuristic that found the solution (or NULL if it's from the tree) */ 1676 SCIP_Bool printreason, /**< Should all reasons of violations be printed? */ 1677 SCIP_Bool completely, /**< Should all violations be checked? */ 1678 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */ 1679 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */ 1680 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 1681 ) 1682 { 1683 assert(primal != NULL); 1684 1685 /* link temporary solution to current solution */ 1686 SCIP_CALL( primalLinkCurrentSol(primal, blkmem, set, stat, transprob, tree, lp, heur) ); 1687 1688 /* add solution to solution storage */ 1689 SCIP_CALL( SCIPprimalTrySol(primal, blkmem, set, messagehdlr, stat, origprob, transprob, 1690 tree, reopt, lp, eventqueue, eventfilter, primal->currentsol, 1691 printreason, completely, FALSE, checkintegrality, checklprows, stored) ); 1692 1693 return SCIP_OKAY; 1694 } 1695 1696 /** inserts solution into the global array of all existing primal solutions */ 1697 SCIP_RETCODE SCIPprimalSolCreated( 1698 SCIP_PRIMAL* primal, /**< primal data */ 1699 SCIP_SET* set, /**< global SCIP settings */ 1700 SCIP_SOL* sol /**< primal CIP solution */ 1701 ) 1702 { 1703 assert(primal != NULL); 1704 assert(sol != NULL); 1705 assert(SCIPsolGetPrimalIndex(sol) == -1); 1706 1707 /* allocate memory for solution storage */ 1708 SCIP_CALL( ensureExistingsolsSize(primal, set, primal->nexistingsols+1) ); 1709 1710 /* append solution */ 1711 SCIPsolSetPrimalIndex(sol, primal->nexistingsols); 1712 primal->existingsols[primal->nexistingsols] = sol; 1713 primal->nexistingsols++; 1714 1715 return SCIP_OKAY; 1716 } 1717 1718 /** removes solution from the global array of all existing primal solutions */ 1719 void SCIPprimalSolFreed( 1720 SCIP_PRIMAL* primal, /**< primal data */ 1721 SCIP_SOL* sol /**< primal CIP solution */ 1722 ) 1723 { 1724 int idx; 1725 1726 assert(primal != NULL); 1727 assert(sol != NULL); 1728 1729 #ifndef NDEBUG 1730 for( idx = 0; idx < primal->nexistingsols; ++idx ) 1731 { 1732 assert(idx == SCIPsolGetPrimalIndex(primal->existingsols[idx])); 1733 } 1734 #endif 1735 1736 /* remove solution */ 1737 idx = SCIPsolGetPrimalIndex(sol); 1738 assert(0 <= idx && idx < primal->nexistingsols); 1739 assert(sol == primal->existingsols[idx]); 1740 if( idx < primal->nexistingsols-1 ) 1741 { 1742 primal->existingsols[idx] = primal->existingsols[primal->nexistingsols-1]; 1743 SCIPsolSetPrimalIndex(primal->existingsols[idx], idx); 1744 } 1745 primal->nexistingsols--; 1746 } 1747 1748 /** updates all existing primal solutions after a change in a variable's objective value */ 1749 void SCIPprimalUpdateVarObj( 1750 SCIP_PRIMAL* primal, /**< primal data */ 1751 SCIP_VAR* var, /**< problem variable */ 1752 SCIP_Real oldobj, /**< old objective value */ 1753 SCIP_Real newobj /**< new objective value */ 1754 ) 1755 { 1756 int i; 1757 1758 assert(primal != NULL); 1759 1760 for( i = 0; i < primal->nexistingsols; ++i ) 1761 { 1762 if( !SCIPsolIsOriginal(primal->existingsols[i]) ) 1763 SCIPsolUpdateVarObj(primal->existingsols[i], var, oldobj, newobj); 1764 } 1765 } 1766 1767 /** retransforms all existing solutions to original problem space 1768 * 1769 * @note as a side effect, the objective value of the solutions can change (numerical errors) 1770 * so we update the objective cutoff value and upper bound accordingly 1771 */ 1772 SCIP_RETCODE SCIPprimalRetransformSolutions( 1773 SCIP_PRIMAL* primal, /**< primal data */ 1774 BMS_BLKMEM* blkmem, /**< block memory */ 1775 SCIP_SET* set, /**< global SCIP settings */ 1776 SCIP_STAT* stat, /**< problem statistics data */ 1777 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 1778 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1779 SCIP_PROB* origprob, /**< original problem */ 1780 SCIP_PROB* transprob, /**< transformed problem */ 1781 SCIP_TREE* tree, /**< branch and bound tree */ 1782 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1783 SCIP_LP* lp /**< current LP data */ 1784 ) 1785 { 1786 SCIP_Bool hasinfval; 1787 int i; 1788 1789 assert(primal != NULL); 1790 1791 for( i = 0; i < primal->nsols; ++i ) 1792 { 1793 if( SCIPsolGetOrigin(primal->sols[i]) == SCIP_SOLORIGIN_ZERO ) 1794 { 1795 SCIP_CALL( SCIPsolRetransform(primal->sols[i], set, stat, origprob, transprob, &hasinfval) ); 1796 } 1797 } 1798 1799 sortPrimalSols(primal, set, origprob, transprob); 1800 1801 /* check if the global upper bound has to be updated 1802 * @todo we do not inform anybody about this change; if this leads to some 1803 * problem, a possible solution is to issue a BESTSOLFOUND event 1804 */ 1805 if( primal->nsols > 0 ) 1806 { 1807 SCIP_Real obj; 1808 1809 obj = SCIPsolGetObj(primal->sols[0], set, transprob, origprob); 1810 if( obj < primal->cutoffbound ) 1811 { 1812 /* update the upper bound */ 1813 SCIP_CALL( SCIPprimalSetUpperbound(primal, blkmem, set, stat, eventfilter, eventqueue, transprob, tree, reopt, lp, obj) ); 1814 } 1815 } 1816 1817 return SCIP_OKAY; 1818 } 1819 1820 /** tries to transform original solution to the transformed problem space */ 1821 SCIP_RETCODE SCIPprimalTransformSol( 1822 SCIP_PRIMAL* primal, /**< primal data */ 1823 SCIP_SOL* sol, /**< primal solution */ 1824 BMS_BLKMEM* blkmem, /**< block memory */ 1825 SCIP_SET* set, /**< global SCIP settings */ 1826 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1827 SCIP_STAT* stat, /**< problem statistics data */ 1828 SCIP_PROB* origprob, /**< original problem */ 1829 SCIP_PROB* transprob, /**< transformed problem after presolve */ 1830 SCIP_TREE* tree, /**< branch and bound tree */ 1831 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1832 SCIP_LP* lp, /**< current LP data */ 1833 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1834 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 1835 SCIP_Real* solvals, /**< array for internal use to store solution values, or NULL; 1836 * if the method is called multiple times in a row, an array with size >= 1837 * number of active variables should be given for performance reasons */ 1838 SCIP_Bool* solvalset, /**< array for internal use to store which solution values were set, or NULL; 1839 * if the method is called multiple times in a row, an array with size >= 1840 * number of active variables should be given for performance reasons */ 1841 int solvalssize, /**< size of solvals and solvalset arrays, should be >= number of active 1842 * variables */ 1843 SCIP_Bool* added /**< pointer to store whether the solution was added */ 1844 ) 1845 { 1846 SCIP_VAR** origvars; 1847 SCIP_VAR** transvars; 1848 SCIP_VAR* var; 1849 SCIP_Real* localsolvals; 1850 SCIP_Bool* localsolvalset; 1851 SCIP_Real solval; 1852 SCIP_Real scalar; 1853 SCIP_Real constant; 1854 SCIP_Bool localarrays; 1855 SCIP_Bool feasible; 1856 int norigvars; 1857 int ntransvars; 1858 int nvarsset; 1859 int v; 1860 1861 assert(origprob != NULL); 1862 assert(transprob != NULL); 1863 assert(SCIPsolIsOriginal(sol)); 1864 assert(solvalssize == 0 || solvals != NULL); 1865 assert(solvalssize == 0 || solvalset != NULL); 1866 1867 origvars = origprob->vars; 1868 norigvars = origprob->nvars; 1869 transvars = transprob->vars; 1870 ntransvars = transprob->nvars; 1871 assert(solvalssize == 0 || solvalssize >= ntransvars); 1872 1873 SCIPsetDebugMsg(set, "try to transfer original solution %p with objective %g into the transformed problem space\n", 1874 (void*)sol, SCIPsolGetOrigObj(sol)); 1875 1876 /* if no solvals and solvalset arrays are given, allocate local ones, otherwise use the given ones */ 1877 localarrays = (solvalssize == 0); 1878 if( localarrays ) 1879 { 1880 SCIP_CALL( SCIPsetAllocBufferArray(set, &localsolvals, ntransvars) ); 1881 SCIP_CALL( SCIPsetAllocBufferArray(set, &localsolvalset, ntransvars) ); 1882 } 1883 else 1884 { 1885 localsolvals = solvals; 1886 localsolvalset = solvalset; 1887 } 1888 1889 BMSclearMemoryArray(localsolvalset, ntransvars); 1890 feasible = TRUE; 1891 (*added) = FALSE; 1892 nvarsset = 0; 1893 1894 /* for each original variable, get the corresponding active, fixed or multi-aggregated variable; 1895 * if it resolves to an active variable, we set its solution value or check whether an already stored solution value 1896 * is consistent; if it resolves to a fixed variable, we check that the fixing matches the original solution value; 1897 * multi-aggregated variables are skipped, because their value is defined by setting solution values for the active 1898 * variables, anyway 1899 */ 1900 for( v = 0; v < norigvars && feasible; ++v ) 1901 { 1902 var = origvars[v]; 1903 1904 solval = SCIPsolGetVal(sol, set, stat, var); 1905 1906 /* get corresponding active, fixed, or multi-aggregated variable */ 1907 scalar = 1.0; 1908 constant = 0.0; 1909 SCIP_CALL( SCIPvarGetProbvarSum(&var, set, &scalar, &constant) ); 1910 assert(SCIPvarIsActive(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED 1911 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR); 1912 1913 /* check whether the fixing corresponds to the solution value of the original variable */ 1914 if( scalar == 0.0 ) 1915 { 1916 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || 1917 (SCIPsetIsInfinity(set, constant) || SCIPsetIsInfinity(set, -constant))); 1918 1919 if( !SCIPsetIsEQ(set, solval, constant) ) 1920 { 1921 SCIPsetDebugMsg(set, "original variable <%s> (solval=%g) resolves to fixed variable <%s> (original solval=%g)\n", 1922 SCIPvarGetName(origvars[v]), solval, SCIPvarGetName(var), constant); 1923 feasible = FALSE; 1924 } 1925 } 1926 else if( SCIPvarIsActive(var) ) 1927 { 1928 /* if we already assigned a solution value to the transformed variable, check that it corresponds to the 1929 * value obtained from the currently regarded original variable 1930 */ 1931 if( localsolvalset[SCIPvarGetProbindex(var)] ) 1932 { 1933 if( !SCIPsetIsEQ(set, solval, scalar * localsolvals[SCIPvarGetProbindex(var)] + constant) ) 1934 { 1935 SCIPsetDebugMsg(set, "original variable <%s> (solval=%g) resolves to active variable <%s> with assigned solval %g (original solval=%g)\n", 1936 SCIPvarGetName(origvars[v]), solval, SCIPvarGetName(var), localsolvals[SCIPvarGetProbindex(var)], 1937 scalar * localsolvals[SCIPvarGetProbindex(var)] + constant); 1938 feasible = FALSE; 1939 } 1940 } 1941 /* assign solution value to the transformed variable */ 1942 else 1943 { 1944 assert(scalar != 0.0); 1945 1946 localsolvals[SCIPvarGetProbindex(var)] = (solval - constant) / scalar; 1947 localsolvalset[SCIPvarGetProbindex(var)] = TRUE; 1948 ++nvarsset; 1949 } 1950 } 1951 #ifndef NDEBUG 1952 /* we do not have to handle multi-aggregated variables here, since by assigning values to all active variabes, 1953 * we implicitly assign values to the multi-aggregated variables, too 1954 */ 1955 else 1956 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR); 1957 #endif 1958 } 1959 1960 /* if the solution values of fixed and active variables lead to no contradiction, construct solution and try it */ 1961 if( feasible ) 1962 { 1963 SCIP_SOL* transsol; 1964 1965 SCIP_CALL( SCIPsolCreate(&transsol, blkmem, set, stat, primal, tree, SCIPsolGetHeur(sol)) ); 1966 1967 /* set solution values for variables to which we assigned a value */ 1968 for( v = 0; v < ntransvars; ++v ) 1969 { 1970 if( localsolvalset[v] ) 1971 { 1972 SCIP_CALL( SCIPsolSetVal(transsol, set, stat, tree, transvars[v], localsolvals[v]) ); 1973 } 1974 } 1975 1976 SCIP_CALL( SCIPprimalTrySolFree(primal, blkmem, set, messagehdlr, stat, origprob, transprob, 1977 tree, reopt, lp, eventqueue, eventfilter, &transsol, FALSE, FALSE, TRUE, TRUE, TRUE, added) ); 1978 1979 SCIPsetDebugMsg(set, "solution transferred, %d/%d active variables set (stored=%u)\n", nvarsset, ntransvars, *added); 1980 } 1981 else 1982 (*added) = FALSE; 1983 1984 /* free local arrays, if needed */ 1985 if( localarrays ) 1986 { 1987 SCIPsetFreeBufferArray(set, &localsolvalset); 1988 SCIPsetFreeBufferArray(set, &localsolvals); 1989 } 1990 1991 return SCIP_OKAY; 1992 } 1993 1994 1995 /** is the updating of violations enabled for this problem? */ 1996 SCIP_Bool SCIPprimalUpdateViolations( 1997 SCIP_PRIMAL* primal /**< problem data */ 1998 ) 1999 { 2000 assert(primal != NULL); 2001 2002 return primal->updateviolations; 2003 } 2004 2005 /** set whether the updating of violations is turned on */ 2006 void SCIPprimalSetUpdateViolations( 2007 SCIP_PRIMAL* primal, /**< problem data */ 2008 SCIP_Bool updateviolations /**< marks whether the updating of violations is turned on */ 2009 ) 2010 { 2011 assert(primal != NULL); 2012 2013 primal->updateviolations = updateviolations; 2014 } 2015