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 heur_oneopt.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief improvement heuristic that alters single variable values 28 * @author Timo Berthold 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/heur_oneopt.h" 35 #include "scip/pub_heur.h" 36 #include "scip/pub_lp.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_misc.h" 39 #include "scip/pub_misc_sort.h" 40 #include "scip/pub_sol.h" 41 #include "scip/pub_var.h" 42 #include "scip/scip_copy.h" 43 #include "scip/scip_general.h" 44 #include "scip/scip_heur.h" 45 #include "scip/scip_lp.h" 46 #include "scip/scip_mem.h" 47 #include "scip/scip_message.h" 48 #include "scip/scip_numerics.h" 49 #include "scip/scip_param.h" 50 #include "scip/scip_prob.h" 51 #include "scip/scip_sol.h" 52 #include "scip/scip_solve.h" 53 #include "scip/scip_solvingstats.h" 54 #include "scip/scip_tree.h" 55 #include <string.h> 56 57 /* @note If the heuristic runs in the root node, the timing is changed to (SCIP_HEURTIMING_DURINGLPLOOP | 58 * SCIP_HEURTIMING_BEFORENODE), see SCIP_DECL_HEURINITSOL callback. 59 */ 60 61 #define HEUR_NAME "oneopt" 62 #define HEUR_DESC "1-opt heuristic which tries to improve setting of single integer variables" 63 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ITERATIVE 64 #define HEUR_PRIORITY -20000 65 #define HEUR_FREQ 1 66 #define HEUR_FREQOFS 0 67 #define HEUR_MAXDEPTH -1 68 #define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_AFTERNODE 69 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 70 71 #define DEFAULT_WEIGHTEDOBJ TRUE /**< should the objective be weighted with the potential shifting value when sorting the shifting candidates? */ 72 #define DEFAULT_DURINGROOT TRUE /**< should the heuristic be called before and during the root node? */ 73 #define DEFAULT_BEFOREPRESOL FALSE /**< should the heuristic be called before presolving */ 74 #define DEFAULT_FORCELPCONSTRUCTION FALSE /**< should the construction of the LP be forced even if LP solving is deactivated? */ 75 #define DEFAULT_USELOOP TRUE /**< should the heuristic continue to run as long as improvements are found? */ 76 /* 77 * Data structures 78 */ 79 80 /** primal heuristic data */ 81 struct SCIP_HeurData 82 { 83 int lastsolindex; /**< index of the last solution for which oneopt was performed */ 84 SCIP_Bool weightedobj; /**< should the objective be weighted with the potential shifting value when sorting the shifting candidates? */ 85 SCIP_Bool duringroot; /**< should the heuristic be called before and during the root node? */ 86 SCIP_Bool forcelpconstruction;/**< should the construction of the LP be forced even if LP solving is deactivated? */ 87 SCIP_Bool beforepresol; /**< should the heuristic be called before presolving */ 88 SCIP_Bool useloop; /**< should the heuristic continue to run as long as improvements are found? */ 89 }; 90 91 92 /* 93 * Local methods 94 */ 95 96 /** compute value by which the solution of variable @p var can be shifted */ 97 static 98 SCIP_Real calcShiftVal( 99 SCIP* scip, /**< SCIP data structure */ 100 SCIP_VAR* var, /**< variable that should be shifted */ 101 SCIP_Real solval, /**< current solution value */ 102 SCIP_Real* activities /**< LP row activities */ 103 ) 104 { 105 SCIP_Real lb; 106 SCIP_Real ub; 107 SCIP_Real obj; 108 SCIP_Real newsolval; 109 110 SCIP_COL* col; 111 SCIP_ROW** colrows; 112 SCIP_Real* colvals; 113 SCIP_Bool shiftdown; 114 115 int ncolrows; 116 117 /* get variable's solution value, global bounds and objective coefficient */ 118 lb = SCIPvarGetLbGlobal(var); 119 ub = SCIPvarGetUbGlobal(var); 120 obj = SCIPvarGetObj(var); 121 shiftdown = TRUE; 122 123 /* determine shifting direction and maximal possible shifting w.r.t. corresponding bound */ 124 if( obj > 0.0 ) 125 newsolval = SCIPfeasCeil(scip, lb); 126 else if( obj < 0.0 ) 127 { 128 newsolval = SCIPfeasFloor(scip, ub); 129 shiftdown = FALSE; 130 } 131 else 132 newsolval = solval; 133 134 /* newsolval might be bounding solval -> avoid numerical shifting */ 135 if( ( shiftdown && SCIPisFeasGE(scip, newsolval, solval) ) 136 || ( !shiftdown && SCIPisFeasLE(scip, newsolval, solval) ) ) 137 return 0.0; 138 139 SCIPdebugMsg(scip, "Try to shift %s variable <%s> with\n", shiftdown ? "down" : "up", SCIPvarGetName(var) ); 140 SCIPdebugMsg(scip, " lb:<%g> <= val:<%g> <= ub:<%g> and obj:<%g> by at most: <%g>\n", lb, solval, ub, obj, newsolval - solval ); 141 142 /* get data of LP column */ 143 col = SCIPvarGetCol(var); 144 colrows = SCIPcolGetRows(col); 145 colvals = SCIPcolGetVals(col); 146 ncolrows = SCIPcolGetNLPNonz(col); 147 148 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL)); 149 150 /* find maximal shift value, st. all rows stay valid */ 151 for( int i = 0; i < ncolrows; ++i ) 152 { 153 SCIP_ROW* row; 154 int rowpos; 155 156 row = colrows[i]; 157 rowpos = SCIProwGetLPPos(row); 158 assert( -1 <= rowpos && rowpos < SCIPgetNLPRows(scip) ); 159 160 /* only global rows need to be valid */ 161 if( rowpos >= 0 && !SCIProwIsLocal(row) ) 162 { 163 SCIP_Real side; 164 SCIP_Bool left; 165 166 left = shiftdown == ( colvals[i] > 0 ); 167 side = left ? SCIProwGetLhs(row) : SCIProwGetRhs(row); 168 169 /* only finite bounds need to be considered */ 170 if( !SCIPisInfinity(scip, left ? -side : side) ) 171 { 172 SCIP_Real newsolvalrow; 173 174 assert( SCIProwIsInLP(row) ); 175 newsolvalrow = solval + (side - activities[rowpos]) / colvals[i]; 176 177 /* update shifting value */ 178 if( ( shiftdown && newsolvalrow > newsolval ) || ( !shiftdown && newsolvalrow < newsolval ) ) 179 { 180 SCIP_Real activity; 181 182 activity = activities[rowpos] + colvals[i] * ((shiftdown ? floor(newsolvalrow) : ceil(newsolvalrow)) - solval); 183 184 /* ensure that shifting preserves feasibility */ 185 if( shiftdown == ( ( left && SCIPisFeasGE(scip, activity, side) ) 186 || ( !left && SCIPisFeasLE(scip, activity, side) ) ) ) 187 newsolval = floor(newsolvalrow); 188 else 189 newsolval = ceil(newsolvalrow); 190 191 SCIPdebugMsg(scip, " -> The shift value has to be set to <%g>, because of row <%s>.\n", 192 newsolval - solval, SCIProwGetName(row)); 193 SCIPdebugMsg(scip, " lhs:<%g> <= act:<%g> <= rhs:<%g>, colval:<%g>\n", 194 SCIProwGetLhs(row), activities[rowpos], SCIProwGetRhs(row), colvals[i]); 195 196 /* newsolval might have reached solval -> avoid numerical shifting */ 197 if( ( shiftdown && SCIPisFeasGE(scip, newsolval, solval) ) 198 || ( !shiftdown && SCIPisFeasLE(scip, newsolval, solval) ) ) 199 return 0.0; 200 } 201 } 202 } 203 } 204 205 /* we must not shift variables to infinity */ 206 return SCIPisInfinity(scip, shiftdown ? -newsolval : newsolval) ? 0.0 : newsolval - solval; 207 } 208 209 210 /** update row activities after a variable's solution value changed */ 211 static 212 SCIP_RETCODE updateRowActivities( 213 SCIP* scip, /**< SCIP data structure */ 214 SCIP_Real* activities, /**< LP row activities */ 215 SCIP_VAR* var, /**< variable that has been changed */ 216 SCIP_Real shiftval /**< value that is added to variable */ 217 ) 218 { 219 SCIP_Real* colvals; 220 SCIP_ROW** colrows; 221 SCIP_COL* col; 222 223 int ncolrows; 224 225 assert(activities != NULL); 226 227 /* get data of column associated to variable */ 228 col = SCIPvarGetCol(var); 229 colrows = SCIPcolGetRows(col); 230 colvals = SCIPcolGetVals(col); 231 ncolrows = SCIPcolGetNLPNonz(col); 232 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL)); 233 234 /* enumerate all rows with nonzero entry in this column */ 235 for( int i = 0; i < ncolrows; ++i ) 236 { 237 SCIP_ROW* row; 238 int rowpos; 239 240 row = colrows[i]; 241 rowpos = SCIProwGetLPPos(row); 242 assert(-1 <= rowpos && rowpos < SCIPgetNLPRows(scip) ); 243 244 /* update row activity, only regard global rows in the LP */ 245 if( rowpos >= 0 && !SCIProwIsLocal(row) ) 246 { 247 activities[rowpos] += shiftval * colvals[i]; 248 249 if( SCIPisInfinity(scip, activities[rowpos]) ) 250 activities[rowpos] = SCIPinfinity(scip); 251 else if( SCIPisInfinity(scip, -activities[rowpos]) ) 252 activities[rowpos] = -SCIPinfinity(scip); 253 } 254 } 255 256 return SCIP_OKAY; 257 } 258 259 /** setup and solve oneopt sub-SCIP */ 260 static 261 SCIP_RETCODE setupAndSolveSubscipOneopt( 262 SCIP* scip, /**< SCIP data structure */ 263 SCIP* subscip, /**< sub-SCIP data structure */ 264 SCIP_HEUR* heur, /**< oneopt heuristic */ 265 SCIP_VAR** vars, /**< SCIP variables */ 266 SCIP_VAR** subvars, /**< subproblem's variables */ 267 SCIP_SOL* bestsol, /**< incumbent solution */ 268 SCIP_RESULT* result, /**< pointer to store the result */ 269 SCIP_Bool* valid /**< pointer to store the valid value */ 270 ) 271 { 272 SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to sub-SCIP variables */ 273 SCIP_SOL* startsol; 274 int nvars; /* number of original problem's variables */ 275 276 assert(scip != NULL); 277 assert(subscip != NULL); 278 assert(heur != NULL); 279 280 nvars = SCIPgetNVars(scip); 281 282 /* create the variable mapping hash map */ 283 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) ); 284 285 /* copy complete SCIP instance */ 286 *valid = FALSE; 287 SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL, "oneopt", TRUE, FALSE, FALSE, TRUE, valid) ); 288 SCIP_CALL( SCIPtransformProb(subscip) ); 289 290 /* get variable image and create start solution for the subproblem */ 291 SCIP_CALL( SCIPcreateOrigSol(subscip, &startsol, NULL) ); 292 for( int i = 0; i < nvars; ++i ) 293 { 294 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 295 if( subvars[i] != NULL ) 296 SCIP_CALL( SCIPsetSolVal(subscip, startsol, subvars[i], SCIPgetSolVal(scip, bestsol, vars[i])) ); 297 } 298 299 /* try to add new solution to sub-SCIP and free it immediately */ 300 *valid = FALSE; 301 SCIP_CALL( SCIPtrySolFree(subscip, &startsol, FALSE, FALSE, FALSE, FALSE, FALSE, valid) ); 302 SCIPhashmapFree(&varmapfw); 303 304 /* deactivate basically everything except oneopt in the sub-SCIP */ 305 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 306 SCIP_CALL( SCIPsetHeuristics(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 307 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 308 309 /* set limits for the subproblem */ 310 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 311 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1LL) ); 312 313 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 314 315 #ifdef SCIP_DEBUG 316 /* for debugging, enable full output */ 317 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 318 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 319 #else 320 /* disable statistic timing inside sub SCIP and output to console */ 321 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 322 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 323 #endif 324 325 /* if necessary, some of the parameters have to be unfixed first */ 326 if( SCIPisParamFixed(subscip, "lp/solvefreq") ) 327 { 328 SCIPwarningMessage(scip, "unfixing parameter lp/solvefreq in subscip of oneopt heuristic\n"); 329 SCIP_CALL( SCIPunfixParam(subscip, "lp/solvefreq") ); 330 } 331 SCIP_CALL( SCIPsetIntParam(subscip, "lp/solvefreq", -1) ); 332 333 if( SCIPisParamFixed(subscip, "heuristics/oneopt/freq") ) 334 { 335 SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/freq in subscip of oneopt heuristic\n"); 336 SCIP_CALL( SCIPunfixParam(subscip, "heuristics/oneopt/freq") ); 337 } 338 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/oneopt/freq", 1) ); 339 340 if( SCIPisParamFixed(subscip, "heuristics/oneopt/forcelpconstruction") ) 341 { 342 SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/forcelpconstruction in subscip of oneopt heuristic\n"); 343 SCIP_CALL( SCIPunfixParam(subscip, "heuristics/oneopt/forcelpconstruction") ); 344 } 345 SCIP_CALL( SCIPsetBoolParam(subscip, "heuristics/oneopt/forcelpconstruction", TRUE) ); 346 347 /* avoid recursive call, which would lead to an endless loop */ 348 if( SCIPisParamFixed(subscip, "heuristics/oneopt/beforepresol") ) 349 { 350 SCIPwarningMessage(scip, "unfixing parameter heuristics/oneopt/beforepresol in subscip of oneopt heuristic\n"); 351 SCIP_CALL( SCIPunfixParam(subscip, "heuristics/oneopt/beforepresol") ); 352 } 353 SCIP_CALL( SCIPsetBoolParam(subscip, "heuristics/oneopt/beforepresol", FALSE) ); 354 355 /* speed up sub-SCIP by not checking dual LP feasibility */ 356 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 357 358 if( *valid ) 359 { 360 /* errors in solving the subproblem should not kill the overall solving process; 361 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 362 */ 363 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 364 365 #ifdef SCIP_DEBUG 366 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 367 #endif 368 369 /* check, whether a solution was found; 370 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted 371 */ 372 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, valid, NULL) ); 373 if( *valid ) 374 *result = SCIP_FOUNDSOL; 375 } 376 377 return SCIP_OKAY; 378 } 379 380 /* 381 * Callback methods of primal heuristic 382 */ 383 384 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 385 static 386 SCIP_DECL_HEURCOPY(heurCopyOneopt) 387 { /*lint --e{715}*/ 388 assert(scip != NULL); 389 assert(heur != NULL); 390 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 391 392 /* call inclusion method of primal heuristic */ 393 SCIP_CALL( SCIPincludeHeurOneopt(scip) ); 394 395 return SCIP_OKAY; 396 } 397 398 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 399 static 400 SCIP_DECL_HEURFREE(heurFreeOneopt) 401 { /*lint --e{715}*/ 402 SCIP_HEURDATA* heurdata; 403 404 assert(heur != NULL); 405 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 406 assert(scip != NULL); 407 408 /* free heuristic data */ 409 heurdata = SCIPheurGetData(heur); 410 assert(heurdata != NULL); 411 SCIPfreeBlockMemory(scip, &heurdata); 412 SCIPheurSetData(heur, NULL); 413 414 return SCIP_OKAY; 415 } 416 417 418 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */ 419 static 420 SCIP_DECL_HEURINITSOL(heurInitsolOneopt) 421 { 422 SCIP_HEURDATA* heurdata; 423 424 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 425 426 /* create heuristic data */ 427 heurdata = SCIPheurGetData(heur); 428 assert(heurdata != NULL); 429 430 /* if the heuristic is called at the root node, we may want to be called during the cut-and-price loop and even before the first LP solve */ 431 if( heurdata->duringroot && SCIPheurGetFreqofs(heur) == 0 ) 432 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_BEFORENODE); 433 434 return SCIP_OKAY; 435 } 436 437 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */ 438 static 439 SCIP_DECL_HEUREXITSOL(heurExitsolOneopt) 440 { 441 assert(heur != NULL); 442 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 443 444 /* reset the timing mask to its default value */ 445 SCIPheurSetTimingmask(heur, HEUR_TIMING); 446 447 return SCIP_OKAY; 448 } 449 450 /** initialization method of primal heuristic (called after problem was transformed) */ 451 static 452 SCIP_DECL_HEURINIT(heurInitOneopt) 453 { /*lint --e{715}*/ 454 SCIP_HEURDATA* heurdata; 455 456 assert(heur != NULL); 457 assert(scip != NULL); 458 459 /* get heuristic data */ 460 heurdata = SCIPheurGetData(heur); 461 assert(heurdata != NULL); 462 463 /* initialize last solution index */ 464 heurdata->lastsolindex = -1; 465 466 return SCIP_OKAY; 467 } 468 469 /** execution method of primal heuristic */ 470 static 471 SCIP_DECL_HEUREXEC(heurExecOneopt) 472 { /*lint --e{715}*/ 473 SCIP_HEURDATA* heurdata; 474 SCIP_SOL* bestsol; /* incumbent solution */ 475 SCIP_SOL* worksol; /* heuristic's working solution */ 476 SCIP_VAR** vars; /* SCIP variables */ 477 SCIP_VAR** shiftcands; /* shiftable variables */ 478 SCIP_ROW** lprows; /* SCIP LP rows */ 479 SCIP_Real* activities; /* row activities for working solution */ 480 SCIP_Real* shiftvals; 481 SCIP_Bool shifted; 482 483 SCIP_RETCODE retcode; 484 485 SCIP_Real lb; 486 SCIP_Real ub; 487 SCIP_Bool valid; 488 int nchgbound; 489 int nbinvars; 490 int nintvars; 491 int nvars; 492 int nlprows; 493 int nshiftcands; 494 int shiftcandssize; 495 int nsuccessfulshifts; 496 int niterations; 497 498 assert(heur != NULL); 499 assert(scip != NULL); 500 assert(result != NULL); 501 502 /* get heuristic's data */ 503 heurdata = SCIPheurGetData(heur); 504 assert(heurdata != NULL); 505 506 *result = SCIP_DELAYED; 507 508 /* we only want to process each solution once */ 509 bestsol = SCIPgetBestSol(scip); 510 if( bestsol == NULL || heurdata->lastsolindex == SCIPsolGetIndex(bestsol) ) 511 return SCIP_OKAY; 512 513 /* reset the timing mask to its default value (at the root node it could be different) */ 514 if( SCIPgetNNodes(scip) > 1 ) 515 SCIPheurSetTimingmask(heur, HEUR_TIMING); 516 517 /* get problem variables */ 518 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 519 nintvars += nbinvars; 520 521 /* do not run if there are no discrete variables */ 522 if( nintvars == 0 ) 523 { 524 *result = SCIP_DIDNOTRUN; 525 return SCIP_OKAY; 526 } 527 528 if( heurtiming == SCIP_HEURTIMING_BEFOREPRESOL ) 529 { 530 SCIP* subscip; /* the subproblem created by oneopt */ 531 SCIP_VAR** subvars; /* subproblem's variables */ 532 533 SCIP_Bool success; 534 535 if( !heurdata->beforepresol ) 536 return SCIP_OKAY; 537 538 /* check whether there is enough time and memory left */ 539 SCIP_CALL( SCIPcheckCopyLimits(scip, &success) ); 540 541 if( !success ) 542 return SCIP_OKAY; 543 544 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 545 546 /* initialize the subproblem */ 547 SCIP_CALL( SCIPcreate(&subscip) ); 548 549 /* setup and solve the subproblem and catch the return code */ 550 retcode = setupAndSolveSubscipOneopt(scip, subscip, heur, vars, subvars, bestsol, result, &valid); 551 552 /* free the subscip in any case */ 553 SCIP_CALL( SCIPfree(&subscip) ); 554 SCIP_CALL( retcode ); 555 556 SCIPfreeBufferArray(scip, &subvars); 557 558 return SCIP_OKAY; 559 } 560 561 /* we can only work on solutions valid in the transformed space */ 562 if( SCIPsolIsOriginal(bestsol) ) 563 return SCIP_OKAY; 564 565 if( heurtiming == SCIP_HEURTIMING_BEFORENODE && (SCIPhasCurrentNodeLP(scip) || heurdata->forcelpconstruction) ) 566 { 567 SCIP_Bool cutoff; 568 569 SCIP_CALL( SCIPconstructLP(scip, &cutoff) ); 570 571 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */ 572 if( cutoff ) 573 { 574 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) ); 575 return SCIP_OKAY; 576 } 577 578 SCIP_CALL( SCIPflushLP(scip) ); 579 580 /* get problem variables again, SCIPconstructLP() might have added new variables */ 581 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 582 nintvars += nbinvars; 583 } 584 585 /* we need an LP */ 586 if( SCIPgetNLPRows(scip) == 0 ) 587 return SCIP_OKAY; 588 589 *result = SCIP_DIDNOTFIND; 590 591 heurdata->lastsolindex = SCIPsolGetIndex(bestsol); 592 SCIP_CALL( SCIPcreateSolCopy(scip, &worksol, bestsol) ); 593 SCIPsolSetHeur(worksol,heur); 594 595 SCIPdebugMsg(scip, "Starting bound adjustment in 1-opt heuristic\n"); 596 597 nchgbound = 0; 598 /* change solution values due to possible global bound changes first */ 599 for( int i = nvars - 1; i >= 0; --i ) 600 { 601 SCIP_VAR* var; 602 SCIP_Real solval; 603 604 var = vars[i]; 605 lb = SCIPvarGetLbGlobal(var); 606 ub = SCIPvarGetUbGlobal(var); 607 608 solval = SCIPgetSolVal(scip, worksol, var); 609 /* old solution value is smaller than the actual lower bound */ 610 if( SCIPisFeasLT(scip, solval, lb) ) 611 { 612 /* set the solution value to the global lower bound */ 613 SCIP_CALL( SCIPsetSolVal(scip, worksol, var, lb) ); 614 ++nchgbound; 615 SCIPdebugMsg(scip, "var <%s> type %d, old solval %g now fixed to lb %g\n", SCIPvarGetName(var), SCIPvarGetType(var), solval, lb); 616 } 617 /* old solution value is greater than the actual upper bound */ 618 else if( SCIPisFeasGT(scip, solval, SCIPvarGetUbGlobal(var)) ) 619 { 620 /* set the solution value to the global upper bound */ 621 SCIP_CALL( SCIPsetSolVal(scip, worksol, var, ub) ); 622 ++nchgbound; 623 SCIPdebugMsg(scip, "var <%s> type %d, old solval %g now fixed to ub %g\n", SCIPvarGetName(var), SCIPvarGetType(var), solval, ub); 624 } 625 } 626 627 SCIPdebugMsg(scip, "number of bound changes (due to global bounds) = %d\n", nchgbound); 628 629 SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) ); 630 SCIP_CALL( SCIPallocBufferArray(scip, &activities, nlprows) ); 631 632 valid = TRUE; 633 634 /* initialize LP row activities */ 635 for( int i = 0; i < nlprows; ++i ) 636 { 637 SCIP_ROW* row; 638 639 row = lprows[i]; 640 assert(SCIProwGetLPPos(row) == i); 641 642 if( !SCIProwIsLocal(row) ) 643 { 644 activities[i] = SCIPgetRowSolActivity(scip, row, worksol); 645 SCIPdebugMsg(scip, "Row <%s> has activity %g\n", SCIProwGetName(row), activities[i]); 646 if( SCIPisFeasLT(scip, activities[i], SCIProwGetLhs(row)) || SCIPisFeasGT(scip, activities[i], SCIProwGetRhs(row)) ) 647 { 648 valid = FALSE; 649 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) ); 650 SCIPdebugMsg(scip, "row <%s> activity %g violates bounds, lhs = %g, rhs = %g\n", SCIProwGetName(row), activities[i], SCIProwGetLhs(row), SCIProwGetRhs(row)); 651 break; 652 } 653 } 654 } 655 656 if( !valid ) 657 { 658 /** @todo try to correct lp rows */ 659 SCIPdebugMsg(scip, "Some global bound changes were not valid in lp rows.\n"); 660 661 SCIPfreeBufferArray(scip, &activities); 662 SCIP_CALL( SCIPfreeSol(scip, &worksol) ); 663 664 return SCIP_OKAY; 665 } 666 667 /* allocate buffer storage for possible shift candidates */ 668 shiftcandssize = 8; 669 SCIP_CALL( SCIPallocBufferArray(scip, &shiftcands, shiftcandssize) ); 670 SCIP_CALL( SCIPallocBufferArray(scip, &shiftvals, shiftcandssize) ); 671 nsuccessfulshifts = 0; 672 niterations = 0; 673 do 674 { 675 /* initialize data */ 676 shifted = FALSE; 677 nshiftcands = 0; 678 ++niterations; 679 SCIPdebugMsg(scip, "Starting 1-opt heuristic iteration #%d\n", niterations); 680 681 /* enumerate all integer variables and find out which of them are shiftable */ 682 /* @todo if useloop=TRUE store for each variable which constraint blocked it and only iterate over those variables 683 * in the following rounds for which the constraint slack was increased by previous shifts 684 */ 685 for( int i = 0; i < nintvars; ++i ) 686 { 687 if( SCIPvarGetStatus(vars[i]) == SCIP_VARSTATUS_COLUMN ) 688 { 689 SCIP_Real shiftval; 690 SCIP_Real solval; 691 692 /* find out whether the variable can be shifted */ 693 solval = SCIPgetSolVal(scip, worksol, vars[i]); 694 shiftval = calcShiftVal(scip, vars[i], solval, activities); 695 696 /* insert the variable into the list of shifting candidates */ 697 if( !SCIPisFeasZero(scip, shiftval) ) 698 { 699 SCIPdebugMsg(scip, " -> Variable <%s> can be shifted by <%1.1f> \n", SCIPvarGetName(vars[i]), shiftval); 700 701 if( nshiftcands == shiftcandssize) 702 { 703 shiftcandssize *= 8; 704 SCIP_CALL( SCIPreallocBufferArray(scip, &shiftcands, shiftcandssize) ); 705 SCIP_CALL( SCIPreallocBufferArray(scip, &shiftvals, shiftcandssize) ); 706 } 707 shiftcands[nshiftcands] = vars[i]; 708 shiftvals[nshiftcands] = shiftval; 709 nshiftcands++; 710 } 711 } 712 } 713 714 /* if at least one variable can be shifted, shift variables sorted by their objective */ 715 if( nshiftcands > 0 ) 716 { 717 SCIP_Real shiftval; 718 SCIP_Real solval; 719 SCIP_VAR* var; 720 721 /* the case that exactly one variable can be shifted is slightly easier */ 722 if( nshiftcands == 1 ) 723 { 724 var = shiftcands[0]; 725 assert(var != NULL); 726 solval = SCIPgetSolVal(scip, worksol, var); 727 shiftval = shiftvals[0]; 728 assert(!SCIPisFeasZero(scip,shiftval)); 729 SCIPdebugMsg(scip, " Only one shiftcand found, var <%s>, which is now shifted by<%1.1f> \n", 730 SCIPvarGetName(var), shiftval); 731 SCIP_CALL( SCIPsetSolVal(scip, worksol, var, solval+shiftval) ); 732 SCIP_CALL( updateRowActivities(scip, activities, var, shiftval) ); 733 ++nsuccessfulshifts; 734 } 735 else 736 { 737 SCIP_Real* objcoeffs; 738 739 SCIP_CALL( SCIPallocBufferArray(scip, &objcoeffs, nshiftcands) ); 740 741 SCIPdebugMsg(scip, " %d shiftcands found \n", nshiftcands); 742 743 /* sort the variables by their objective, optionally weighted with the shiftval */ 744 if( heurdata->weightedobj ) 745 { 746 for( int i = 0; i < nshiftcands; ++i ) 747 objcoeffs[i] = SCIPvarGetObj(shiftcands[i])*shiftvals[i]; 748 } 749 else 750 { 751 for( int i = 0; i < nshiftcands; ++i ) 752 objcoeffs[i] = SCIPvarGetObj(shiftcands[i]); 753 } 754 755 /* sort arrays with respect to the first one */ 756 SCIPsortRealPtr(objcoeffs, (void**)shiftcands, nshiftcands); 757 758 /* try to shift each variable -> Activities have to be updated */ 759 for( int i = 0; i < nshiftcands; ++i ) 760 { 761 var = shiftcands[i]; 762 assert(var != NULL); 763 solval = SCIPgetSolVal(scip, worksol, var); 764 shiftval = calcShiftVal(scip, var, solval, activities); 765 assert(i > 0 || !SCIPisFeasZero(scip, shiftval)); 766 assert(SCIPisFeasGE(scip, solval+shiftval, SCIPvarGetLbGlobal(var)) && SCIPisFeasLE(scip, solval+shiftval, SCIPvarGetUbGlobal(var))); 767 768 /* update data structures for nonzero shift value */ 769 if( ! SCIPisFeasZero(scip, shiftval) ) 770 { 771 SCIPdebugMsg(scip, " -> Variable <%s> is now shifted by <%1.1f> \n", SCIPvarGetName(vars[i]), shiftval); 772 SCIP_CALL( SCIPsetSolVal(scip, worksol, var, solval+shiftval) ); 773 SCIP_CALL( updateRowActivities(scip, activities, var, shiftval) ); 774 ++nsuccessfulshifts; 775 } 776 } 777 778 SCIPfreeBufferArray(scip, &objcoeffs); 779 } 780 shifted = TRUE; 781 } 782 } 783 while( heurdata->useloop && shifted ); 784 785 if( nsuccessfulshifts > 0 ) 786 { 787 /* if the problem is a pure IP, try to install the solution, if it is a MIP, solve LP again to set the continuous 788 * variables to the best possible value 789 */ 790 if( nvars == nintvars || !SCIPhasCurrentNodeLP(scip) || SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 791 { 792 SCIP_Bool success; 793 794 /* since activities are maintained iteratively, we cannot guarantee the feasibility of the shiftings and have 795 * to set the checklprows flag to TRUE 796 */ 797 SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) ); 798 799 if( success ) 800 { 801 SCIPdebugMsg(scip, "found feasible shifted solution:\n"); 802 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) ); 803 *result = SCIP_FOUNDSOL; 804 } 805 } 806 else 807 { 808 SCIP_Bool lperror; 809 #ifdef NDEBUG 810 SCIP_RETCODE retstat; 811 #endif 812 813 SCIPdebugMsg(scip, "shifted solution should be feasible -> solve LP to fix continuous variables to best values\n"); 814 815 /* start diving to calculate the LP relaxation */ 816 SCIP_CALL( SCIPstartDive(scip) ); 817 818 /* set the bounds of the variables: fixed for integers, global bounds for continuous */ 819 for( int i = 0; i < nvars; ++i ) 820 { 821 if( SCIPvarGetStatus(vars[i]) == SCIP_VARSTATUS_COLUMN ) 822 { 823 SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], SCIPvarGetLbGlobal(vars[i])) ); 824 SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], SCIPvarGetUbGlobal(vars[i])) ); 825 } 826 } 827 /* apply this after global bounds to not cause an error with intermediate empty domains */ 828 for( int i = 0; i < nintvars; ++i ) 829 { 830 if( SCIPvarGetStatus(vars[i]) == SCIP_VARSTATUS_COLUMN ) 831 { 832 SCIP_Real solval; 833 solval = SCIPgetSolVal(scip, worksol, vars[i]); 834 SCIP_CALL( SCIPchgVarLbDive(scip, vars[i], solval) ); 835 SCIP_CALL( SCIPchgVarUbDive(scip, vars[i], solval) ); 836 } 837 } 838 839 /* solve LP */ 840 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip)); 841 842 /**@todo in case of an MINLP, if SCIPisNLPConstructed() is TRUE, say, rather solve the NLP instead of the LP */ 843 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic. 844 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 845 */ 846 #ifdef NDEBUG 847 retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL); 848 if( retstat != SCIP_OKAY ) 849 { 850 SCIPwarningMessage(scip, "Error while solving LP in 1-opt heuristic; LP solve terminated with code <%d>\n",retstat); 851 } 852 #else 853 SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) ); 854 #endif 855 856 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip)); 857 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip)); 858 859 /* check if this is a feasible solution */ 860 if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL ) 861 { 862 SCIP_Bool success; 863 864 /* copy the current LP solution to the working solution */ 865 SCIP_CALL( SCIPlinkLPSol(scip, worksol) ); 866 SCIP_CALL( SCIPtrySol(scip, worksol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) ); 867 868 /* check solution for feasibility */ 869 if( success ) 870 { 871 SCIPdebugMsg(scip, "found feasible shifted solution:\n"); 872 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, worksol, NULL, FALSE) ) ); 873 *result = SCIP_FOUNDSOL; 874 } 875 } 876 877 /* terminate the diving */ 878 SCIP_CALL( SCIPendDive(scip) ); 879 } 880 } 881 882 /* heuristic should not rerun on this incumbent because the heuristic loop finishes only after no further 883 * improvements of the incumbent solution are possible 884 */ 885 if( heurdata->useloop ) 886 heurdata->lastsolindex = SCIPsolGetIndex(SCIPgetBestSol(scip)); 887 888 SCIPfreeBufferArray(scip, &shiftvals); 889 SCIPfreeBufferArray(scip, &shiftcands); 890 SCIPfreeBufferArray(scip, &activities); 891 892 SCIP_CALL( SCIPfreeSol(scip, &worksol) ); 893 894 SCIPdebugMsg(scip, "Finished 1-opt heuristic\n"); 895 896 return SCIP_OKAY; 897 } 898 899 /* 900 * primal heuristic specific interface methods 901 */ 902 903 /** creates the oneopt primal heuristic and includes it in SCIP */ 904 SCIP_RETCODE SCIPincludeHeurOneopt( 905 SCIP* scip /**< SCIP data structure */ 906 ) 907 { 908 SCIP_HEURDATA* heurdata; 909 SCIP_HEUR* heur; 910 911 /* create Oneopt primal heuristic data */ 912 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 913 914 /* include primal heuristic */ 915 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 916 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 917 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecOneopt, heurdata) ); 918 919 assert(heur != NULL); 920 921 /* set non-NULL pointers to callback methods */ 922 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyOneopt) ); 923 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeOneopt) ); 924 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolOneopt) ); 925 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolOneopt) ); 926 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitOneopt) ); 927 928 /* add oneopt primal heuristic parameters */ 929 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/weightedobj", 930 "should the objective be weighted with the potential shifting value when sorting the shifting candidates?", 931 &heurdata->weightedobj, TRUE, DEFAULT_WEIGHTEDOBJ, NULL, NULL) ); 932 933 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/duringroot", 934 "should the heuristic be called before and during the root node?", 935 &heurdata->duringroot, TRUE, DEFAULT_DURINGROOT, NULL, NULL) ); 936 937 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/forcelpconstruction", 938 "should the construction of the LP be forced even if LP solving is deactivated?", 939 &heurdata->forcelpconstruction, TRUE, DEFAULT_FORCELPCONSTRUCTION, NULL, NULL) ); 940 941 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/beforepresol", 942 "should the heuristic be called before presolving?", 943 &heurdata->beforepresol, TRUE, DEFAULT_BEFOREPRESOL, NULL, NULL) ); 944 945 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/oneopt/useloop", 946 "should the heuristic continue to run as long as improvements are found?", 947 &heurdata->useloop, TRUE, DEFAULT_USELOOP, NULL, NULL) ); 948 949 return SCIP_OKAY; 950 } 951