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_intshifting.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variables, and 28 * solves a final LP to calculate feasible values for continuous variables 29 * @author Tobias Achterberg 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "blockmemshell/memory.h" 35 #include "scip/heur_intshifting.h" 36 #include "scip/pub_heur.h" 37 #include "scip/pub_lp.h" 38 #include "scip/pub_message.h" 39 #include "scip/pub_misc.h" 40 #include "scip/pub_var.h" 41 #include "scip/scip_branch.h" 42 #include "scip/scip_general.h" 43 #include "scip/scip_heur.h" 44 #include "scip/scip_lp.h" 45 #include "scip/scip_mem.h" 46 #include "scip/scip_message.h" 47 #include "scip/scip_numerics.h" 48 #include "scip/scip_prob.h" 49 #include "scip/scip_randnumgen.h" 50 #include "scip/scip_sol.h" 51 #include "scip/scip_solvingstats.h" 52 #include <string.h> 53 54 #define HEUR_NAME "intshifting" 55 #define HEUR_DESC "LP rounding heuristic with infeasibility recovering and final LP solving" 56 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING 57 #define HEUR_PRIORITY -10000 58 #define HEUR_FREQ 10 59 #define HEUR_FREQOFS 0 60 #define HEUR_MAXDEPTH -1 61 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 62 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 63 64 #define MAXSHIFTINGS 50 /**< maximal number of non improving shiftings */ 65 #define WEIGHTFACTOR 1.1 66 #define DEFAULT_RANDSEED 17 67 68 /* locally defined heuristic data */ 69 struct SCIP_HeurData 70 { 71 SCIP_SOL* sol; /**< working solution */ 72 SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */ 73 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 74 }; 75 76 77 /* 78 * local methods 79 */ 80 81 /** update row violation arrays after a row's activity value changed */ 82 static 83 void updateViolations( 84 SCIP* scip, /**< SCIP data structure */ 85 SCIP_ROW* row, /**< LP row */ 86 SCIP_ROW** violrows, /**< array with currently violated rows */ 87 int* violrowpos, /**< position of LP rows in violrows array */ 88 int* nviolrows, /**< pointer to the number of currently violated rows */ 89 int* nviolfracrows, /**< pointer to the number of violated rows with fractional candidates */ 90 int* nfracsinrow, /**< array with number of fractional variables for every row */ 91 SCIP_Real oldminactivity, /**< old minimal activity value of LP row */ 92 SCIP_Real oldmaxactivity, /**< old maximal activity value of LP row */ 93 SCIP_Real newminactivity, /**< new minimal activity value of LP row */ 94 SCIP_Real newmaxactivity /**< new maximal activity value of LP row */ 95 ) 96 { 97 SCIP_Real lhs; 98 SCIP_Real rhs; 99 SCIP_Bool oldviol; 100 SCIP_Bool newviol; 101 102 assert(violrows != NULL); 103 assert(violrowpos != NULL); 104 assert(nviolrows != NULL); 105 106 lhs = SCIProwGetLhs(row); 107 rhs = SCIProwGetRhs(row); 108 109 /* SCIPisFeasLT cannot handle comparing different infinities. To prevent this, we make a case distinction. */ 110 if( ! (SCIPisInfinity(scip, oldmaxactivity) || SCIPisInfinity(scip, -oldmaxactivity) 111 || SCIPisInfinity(scip, oldminactivity) || SCIPisInfinity(scip, -oldminactivity)) ) 112 { 113 oldviol = (SCIPisFeasLT(scip, oldmaxactivity, lhs) || SCIPisFeasGT(scip, oldminactivity, rhs)); 114 } 115 else 116 { 117 oldviol = (SCIPisInfinity(scip, -oldmaxactivity) && !SCIPisInfinity(scip, -lhs)) || 118 (SCIPisInfinity(scip, oldminactivity) && !SCIPisInfinity(scip, rhs)); 119 } 120 121 /* SCIPisFeasLT cannot handle comparing different infinities. To prevent this, we make a case distinction. */ 122 if( ! (SCIPisInfinity(scip, newmaxactivity) || SCIPisInfinity(scip, -newmaxactivity) 123 || SCIPisInfinity(scip, newminactivity) || SCIPisInfinity(scip, -newminactivity)) ) 124 { 125 newviol = (SCIPisFeasLT(scip, newmaxactivity, lhs) || SCIPisFeasGT(scip, newminactivity, rhs)); 126 } 127 else 128 { 129 newviol = (SCIPisInfinity(scip, -newmaxactivity) && !SCIPisInfinity(scip, -lhs)) || 130 (SCIPisInfinity(scip, newminactivity) && !SCIPisInfinity(scip, rhs)); 131 } 132 133 if( oldviol != newviol ) 134 { 135 int rowpos; 136 int violpos; 137 138 rowpos = SCIProwGetLPPos(row); 139 assert(rowpos >= 0); 140 141 if( oldviol ) 142 { 143 /* the row violation was repaired: remove row from violrows array, decrease violation count */ 144 violpos = violrowpos[rowpos]; 145 assert(0 <= violpos && violpos < *nviolrows); 146 assert(violrows[violpos] == row); 147 violrowpos[rowpos] = -1; 148 /* first, move the row to the end of the subset of violated rows with fractional variables */ 149 if( nfracsinrow[rowpos] > 0 ) 150 { 151 violrows[violpos] = violrows[*nviolrows-1]; 152 assert(violpos < *nviolfracrows); 153 154 /* replace with last violated row containing fractional variables */ 155 if( violpos != *nviolfracrows - 1 ) 156 { 157 violrows[violpos] = violrows[*nviolfracrows - 1]; 158 violrowpos[SCIProwGetLPPos(violrows[violpos])] = violpos; 159 violpos = *nviolfracrows - 1; 160 } 161 (*nviolfracrows)--; 162 } 163 164 assert(violpos >= *nviolfracrows); 165 166 /* swap row at the end of the violated array to the position of this row and decrease the counter */ 167 if( violpos != *nviolrows - 1 ) 168 { 169 violrows[violpos] = violrows[*nviolrows - 1]; 170 violrowpos[SCIProwGetLPPos(violrows[violpos])] = violpos; 171 } 172 (*nviolrows)--; 173 } 174 else 175 { 176 /* the row is now violated: add row to violrows array, increase violation count */ 177 assert(violrowpos[rowpos] == -1); 178 violrows[*nviolrows] = row; 179 violrowpos[rowpos] = *nviolrows; 180 (*nviolrows)++; 181 182 /* if the row contains fractional variables, swap with the last violated row that has no fractional variables 183 * at position *nviolfracrows 184 */ 185 if( nfracsinrow[rowpos] > 0 ) 186 { 187 if( *nviolfracrows < *nviolrows - 1 ) 188 { 189 assert(nfracsinrow[SCIProwGetLPPos(violrows[*nviolfracrows])] == 0); 190 191 violrows[*nviolrows - 1] = violrows[*nviolfracrows]; 192 violrowpos[SCIProwGetLPPos(violrows[*nviolrows - 1])] = *nviolrows - 1; 193 194 violrows[*nviolfracrows] = row; 195 violrowpos[rowpos] = *nviolfracrows; 196 } 197 (*nviolfracrows)++; 198 } 199 } 200 } 201 } 202 203 /** update row activities after a variable's solution value changed */ 204 static 205 SCIP_RETCODE updateActivities( 206 SCIP* scip, /**< SCIP data structure */ 207 SCIP_Real* minactivities, /**< LP row minimal activities */ 208 SCIP_Real* maxactivities, /**< LP row maximal activities */ 209 SCIP_ROW** violrows, /**< array with currently violated rows */ 210 int* violrowpos, /**< position of LP rows in violrows array */ 211 int* nviolrows, /**< pointer to the number of currently violated rows */ 212 int* nviolfracrows, /**< pointer to the number of violated rows with fractional candidates */ 213 int* nfracsinrow, /**< array with number of fractional variables for every row */ 214 int nlprows, /**< number of rows in current LP */ 215 SCIP_VAR* var, /**< variable that has been changed */ 216 SCIP_Real oldsolval, /**< old solution value of variable */ 217 SCIP_Real newsolval /**< new solution value of variable */ 218 ) 219 { 220 SCIP_COL* col; 221 SCIP_ROW** colrows; 222 SCIP_Real* colvals; 223 SCIP_Real delta; 224 int ncolrows; 225 int r; 226 227 assert(minactivities != NULL); 228 assert(maxactivities != NULL); 229 assert(nviolrows != NULL); 230 assert(0 <= *nviolrows && *nviolrows <= nlprows); 231 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER); 232 233 delta = newsolval - oldsolval; 234 col = SCIPvarGetCol(var); 235 colrows = SCIPcolGetRows(col); 236 colvals = SCIPcolGetVals(col); 237 ncolrows = SCIPcolGetNLPNonz(col); 238 assert(ncolrows == 0 || (colrows != NULL && colvals != NULL)); 239 240 for( r = 0; r < ncolrows; ++r ) 241 { 242 SCIP_ROW* row; 243 int rowpos; 244 245 row = colrows[r]; 246 rowpos = SCIProwGetLPPos(row); 247 assert(-1 <= rowpos && rowpos < nlprows); 248 249 if( rowpos >= 0 && !SCIProwIsLocal(row) ) 250 { 251 SCIP_Real oldminactivity; 252 SCIP_Real oldmaxactivity; 253 SCIP_Real newminactivity; 254 SCIP_Real newmaxactivity; 255 256 assert(SCIProwIsInLP(row)); 257 258 /* update row activities */ 259 oldminactivity = minactivities[rowpos]; 260 oldmaxactivity = maxactivities[rowpos]; 261 262 if( !SCIPisInfinity(scip, -oldminactivity) ) 263 { 264 newminactivity = oldminactivity + delta * colvals[r]; 265 minactivities[rowpos] = newminactivity; 266 } 267 else 268 newminactivity = -SCIPinfinity(scip); 269 if( !SCIPisInfinity(scip, oldmaxactivity) ) 270 { 271 newmaxactivity = oldmaxactivity + delta * colvals[r]; 272 maxactivities[rowpos] = newmaxactivity; 273 } 274 else 275 newmaxactivity = SCIPinfinity(scip); 276 277 /* update row violation arrays */ 278 updateViolations(scip, row, violrows, violrowpos, nviolrows, nviolfracrows, nfracsinrow, oldminactivity, oldmaxactivity, 279 newminactivity, newmaxactivity); 280 } 281 } 282 283 return SCIP_OKAY; 284 } 285 286 /** returns an integer variable, that pushes activity of the row in the given direction with minimal negative impact on 287 * other rows; 288 * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction; 289 * prefer fractional integers over other variables in order to become integral during the process; 290 * shifting in a direction is forbidden, if this forces the objective value over the upper bound, or if the variable 291 * was already shifted in the opposite direction 292 */ 293 static 294 SCIP_RETCODE selectShifting( 295 SCIP* scip, /**< SCIP data structure */ 296 SCIP_SOL* sol, /**< primal solution */ 297 SCIP_ROW* row, /**< LP row */ 298 SCIP_Real rowactivity, /**< activity of LP row */ 299 int direction, /**< should the activity be increased (+1) or decreased (-1)? */ 300 SCIP_Real* nincreases, /**< array with weighted number of increasings per variables */ 301 SCIP_Real* ndecreases, /**< array with weighted number of decreasings per variables */ 302 SCIP_Real increaseweight, /**< current weight of increase/decrease updates */ 303 SCIP_VAR** shiftvar, /**< pointer to store the shifting variable, returns NULL if impossible */ 304 SCIP_Real* oldsolval, /**< pointer to store old solution value of shifting variable */ 305 SCIP_Real* newsolval /**< pointer to store new (shifted) solution value of shifting variable */ 306 ) 307 { 308 SCIP_COL** rowcols; 309 SCIP_Real* rowvals; 310 int nrowcols; 311 SCIP_Real activitydelta; 312 SCIP_Real bestshiftscore; 313 SCIP_Real bestdeltaobj; 314 int c; 315 316 assert(direction == +1 || direction == -1); 317 assert(nincreases != NULL); 318 assert(ndecreases != NULL); 319 assert(shiftvar != NULL); 320 assert(oldsolval != NULL); 321 assert(newsolval != NULL); 322 323 /* get row entries */ 324 rowcols = SCIProwGetCols(row); 325 rowvals = SCIProwGetVals(row); 326 nrowcols = SCIProwGetNLPNonz(row); 327 328 /* calculate how much the activity must be shifted in order to become feasible */ 329 activitydelta = (direction == +1 ? SCIProwGetLhs(row) - rowactivity : SCIProwGetRhs(row) - rowactivity); 330 assert((direction == +1 && SCIPisPositive(scip, activitydelta)) 331 || (direction == -1 && SCIPisNegative(scip, activitydelta))); 332 333 /* select shifting variable */ 334 bestshiftscore = SCIP_REAL_MAX; 335 bestdeltaobj = SCIPinfinity(scip); 336 *shiftvar = NULL; 337 *newsolval = 0.0; 338 *oldsolval = 0.0; 339 for( c = 0; c < nrowcols; ++c ) 340 { 341 SCIP_COL* col; 342 SCIP_VAR* var; 343 SCIP_Real val; 344 SCIP_Real solval; 345 SCIP_Real shiftval; 346 SCIP_Real shiftscore; 347 SCIP_Bool isfrac; 348 SCIP_Bool increase; 349 int probindex; 350 351 col = rowcols[c]; 352 var = SCIPcolGetVar(col); 353 val = rowvals[c]; 354 assert(!SCIPisZero(scip, val)); 355 solval = SCIPgetSolVal(scip, sol, var); 356 357 /* only accept integer variables */ 358 if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY && SCIPvarGetType(var) != SCIP_VARTYPE_INTEGER ) 359 continue; 360 361 isfrac = !SCIPisFeasIntegral(scip, solval); 362 increase = (direction * val > 0.0); 363 probindex = SCIPvarGetProbindex(var); 364 365 /* calculate the score of the shifting (prefer smaller values) */ 366 if( isfrac ) 367 shiftscore = increase ? -1.0 / (SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) + 1.0) : 368 -1.0 / (SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) + 1.0); 369 else 370 { 371 if( increase ) 372 shiftscore = ndecreases[probindex]/increaseweight; 373 else 374 shiftscore = nincreases[probindex]/increaseweight; 375 shiftscore += 1.0; 376 } 377 378 if( shiftscore <= bestshiftscore ) 379 { 380 SCIP_Real deltaobj; 381 382 if( !increase ) 383 { 384 /* shifting down */ 385 assert(direction * val < 0.0); 386 if( isfrac ) 387 shiftval = SCIPfeasFloor(scip, solval); 388 else 389 { 390 SCIP_Real lb; 391 392 assert(activitydelta/val < 0.0); 393 shiftval = solval + activitydelta/val; 394 assert(shiftval <= solval); /* may be equal due to numerical digit erasement in the subtraction */ 395 shiftval = SCIPfeasFloor(scip, shiftval); 396 lb = SCIPvarGetLbGlobal(var); 397 shiftval = MAX(shiftval, lb); 398 } 399 } 400 else 401 { 402 /* shifting up */ 403 assert(direction * val > 0.0); 404 if( isfrac ) 405 shiftval = SCIPfeasCeil(scip, solval); 406 else 407 { 408 SCIP_Real ub; 409 410 assert(activitydelta/val > 0.0); 411 shiftval = solval + activitydelta/val; 412 assert(shiftval >= solval); /* may be equal due to numerical digit erasement in the subtraction */ 413 shiftval = SCIPfeasCeil(scip, shiftval); 414 ub = SCIPvarGetUbGlobal(var); 415 shiftval = MIN(shiftval, ub); 416 } 417 } 418 419 if( SCIPisEQ(scip, shiftval, solval) ) 420 continue; 421 422 deltaobj = SCIPvarGetObj(var) * (shiftval - solval); 423 if( (shiftscore < bestshiftscore || deltaobj < bestdeltaobj) 424 && !SCIPisHugeValue(scip, REALABS(shiftval)) ) /* ignore candidates for which shiftval is too large */ 425 { 426 bestshiftscore = shiftscore; 427 bestdeltaobj = deltaobj; 428 *shiftvar = var; 429 *oldsolval = solval; 430 *newsolval = shiftval; 431 } 432 } 433 } 434 435 return SCIP_OKAY; 436 } 437 438 /** returns a fractional variable, that has most impact on rows in opposite direction, i.e. that is most crucial to 439 * fix in the other direction; 440 * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction; 441 * shifting in a direction is forbidden, if this forces the objective value over the upper bound 442 */ 443 static 444 SCIP_RETCODE selectEssentialRounding( 445 SCIP* scip, /**< SCIP data structure */ 446 SCIP_SOL* sol, /**< primal solution */ 447 SCIP_Real minobj, /**< minimal objective value possible after shifting remaining fractional vars */ 448 SCIP_VAR** lpcands, /**< fractional variables in LP */ 449 int nlpcands, /**< number of fractional variables in LP */ 450 SCIP_VAR** shiftvar, /**< pointer to store the shifting variable, returns NULL if impossible */ 451 SCIP_Real* oldsolval, /**< old (fractional) solution value of shifting variable */ 452 SCIP_Real* newsolval /**< new (shifted) solution value of shifting variable */ 453 ) 454 { 455 SCIP_VAR* var; 456 SCIP_Real solval; 457 SCIP_Real shiftval; 458 SCIP_Real obj; 459 SCIP_Real deltaobj; 460 SCIP_Real bestdeltaobj; 461 int maxnlocks; 462 int nlocks; 463 int v; 464 465 assert(shiftvar != NULL); 466 assert(oldsolval != NULL); 467 assert(newsolval != NULL); 468 469 /* select shifting variable */ 470 maxnlocks = -1; 471 bestdeltaobj = SCIPinfinity(scip); 472 *shiftvar = NULL; 473 for( v = 0; v < nlpcands; ++v ) 474 { 475 var = lpcands[v]; 476 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER); 477 478 solval = SCIPgetSolVal(scip, sol, var); 479 if( !SCIPisFeasIntegral(scip, solval) ) 480 { 481 obj = SCIPvarGetObj(var); 482 483 /* shifting down */ 484 nlocks = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL); 485 if( nlocks >= maxnlocks ) 486 { 487 shiftval = SCIPfeasFloor(scip, solval); 488 deltaobj = obj * (shiftval - solval); 489 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj - obj < SCIPgetCutoffbound(scip) ) 490 { 491 maxnlocks = nlocks; 492 bestdeltaobj = deltaobj; 493 *shiftvar = var; 494 *oldsolval = solval; 495 *newsolval = shiftval; 496 } 497 } 498 499 /* shifting up */ 500 nlocks = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL); 501 if( nlocks >= maxnlocks ) 502 { 503 shiftval = SCIPfeasCeil(scip, solval); 504 deltaobj = obj * (shiftval - solval); 505 if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj + obj < SCIPgetCutoffbound(scip) ) 506 { 507 maxnlocks = nlocks; 508 bestdeltaobj = deltaobj; 509 *shiftvar = var; 510 *oldsolval = solval; 511 *newsolval = shiftval; 512 } 513 } 514 } 515 } 516 517 return SCIP_OKAY; 518 } 519 520 /** adds a given value to the fractionality counters of the rows in which the given variable appears */ 521 static 522 void addFracCounter( 523 int* nfracsinrow, /**< array to store number of fractional variables per row */ 524 SCIP_ROW** violrows, /**< array with currently violated rows */ 525 int* violrowpos, /**< position of LP rows in violrows array */ 526 int* nviolfracrows, /**< pointer to store the number of violated rows with fractional variables */ 527 int nviolrows, /**< the number of currently violated rows (stays unchanged in this method) */ 528 int nlprows, /**< number of rows in LP */ 529 SCIP_VAR* var, /**< variable for which the counting should be updated */ 530 int incval /**< value that should be added to the corresponding array entries */ 531 ) 532 { 533 SCIP_COL* col; 534 SCIP_ROW** rows; 535 int nrows; 536 int r; 537 538 assert(incval != 0); 539 assert(nviolrows >= *nviolfracrows); 540 541 col = SCIPvarGetCol(var); 542 rows = SCIPcolGetRows(col); 543 nrows = SCIPcolGetNLPNonz(col); 544 for( r = 0; r < nrows; ++r ) 545 { 546 int rowlppos; 547 int theviolrowpos; 548 SCIP_ROW* row; 549 550 row = rows[r]; 551 assert(NULL != row); 552 rowlppos = SCIProwGetLPPos(row); 553 assert(0 <= rowlppos && rowlppos < nlprows); 554 assert(!SCIProwIsLocal(row) || violrowpos[rowlppos] == -1); 555 556 if( SCIProwIsLocal(row) ) 557 continue; 558 559 nfracsinrow[rowlppos] += incval; 560 assert(nfracsinrow[rowlppos] >= 0); 561 562 theviolrowpos = violrowpos[rowlppos]; 563 564 /* swap positions in violrows array if fractionality has changed to 0 */ 565 if( theviolrowpos >= 0 ) 566 { 567 /* first case: the number of fractional variables has become zero: swap row in violrows array to the 568 * second part, containing only violated rows without fractional variables 569 */ 570 if( nfracsinrow[rowlppos] == 0 ) 571 { 572 assert(theviolrowpos <= *nviolfracrows - 1); 573 574 /* nothing to do if row is already at the end of the first part, otherwise, swap it to the last position 575 * and decrease the counter */ 576 if( theviolrowpos < *nviolfracrows - 1 ) 577 { 578 violrows[theviolrowpos] = violrows[*nviolfracrows - 1]; 579 violrows[*nviolfracrows - 1] = row; 580 581 violrowpos[SCIProwGetLPPos(violrows[theviolrowpos])] = theviolrowpos; 582 violrowpos[rowlppos] = *nviolfracrows - 1; 583 } 584 (*nviolfracrows)--; 585 } 586 /* second interesting case: the number of fractional variables was zero before, swap it with the first 587 * violated row without fractional variables 588 */ 589 else if( nfracsinrow[rowlppos] == incval ) 590 { 591 assert(theviolrowpos >= *nviolfracrows); 592 593 /* nothing to do if the row is exactly located at index *nviolfracrows */ 594 if( theviolrowpos > *nviolfracrows ) 595 { 596 violrows[theviolrowpos] = violrows[*nviolfracrows]; 597 violrows[*nviolfracrows] = row; 598 599 violrowpos[SCIProwGetLPPos(violrows[theviolrowpos])] = theviolrowpos; 600 violrowpos[rowlppos] = *nviolfracrows; 601 } 602 (*nviolfracrows)++; 603 } 604 } 605 } 606 } 607 608 609 /* 610 * Callback methods 611 */ 612 613 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 614 static 615 SCIP_DECL_HEURCOPY(heurCopyIntshifting) 616 { /*lint --e{715}*/ 617 assert(scip != NULL); 618 assert(heur != NULL); 619 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 620 621 /* call inclusion method of primal heuristic */ 622 SCIP_CALL( SCIPincludeHeurIntshifting(scip) ); 623 624 return SCIP_OKAY; 625 } 626 627 628 /** initialization method of primal heuristic (called after problem was transformed) */ 629 static 630 SCIP_DECL_HEURINIT(heurInitIntshifting) /*lint --e{715}*/ 631 { /*lint --e{715}*/ 632 SCIP_HEURDATA* heurdata; 633 634 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 635 assert(SCIPheurGetData(heur) == NULL); 636 637 /* create heuristic data */ 638 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 639 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 640 heurdata->lastlp = -1; 641 SCIPheurSetData(heur, heurdata); 642 643 /* create random number generator */ 644 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen, 645 DEFAULT_RANDSEED, TRUE) ); 646 647 return SCIP_OKAY; 648 } 649 650 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 651 static 652 SCIP_DECL_HEUREXIT(heurExitIntshifting) /*lint --e{715}*/ 653 { /*lint --e{715}*/ 654 SCIP_HEURDATA* heurdata; 655 656 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 657 658 /* free heuristic data */ 659 heurdata = SCIPheurGetData(heur); 660 assert(heurdata != NULL); 661 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 662 663 /* free random number generator */ 664 SCIPfreeRandom(scip, &heurdata->randnumgen); 665 666 SCIPfreeBlockMemory(scip, &heurdata); 667 SCIPheurSetData(heur, NULL); 668 669 return SCIP_OKAY; 670 } 671 672 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */ 673 static 674 SCIP_DECL_HEURINITSOL(heurInitsolIntshifting) 675 { 676 SCIP_HEURDATA* heurdata; 677 678 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 679 680 heurdata = SCIPheurGetData(heur); 681 assert(heurdata != NULL); 682 heurdata->lastlp = -1; 683 684 return SCIP_OKAY; 685 } 686 687 688 /** execution method of primal heuristic */ 689 static 690 SCIP_DECL_HEUREXEC(heurExecIntshifting) /*lint --e{715}*/ 691 { /*lint --e{715}*/ 692 SCIP_HEURDATA* heurdata; 693 SCIP_SOL* sol; 694 SCIP_VAR** lpcands; 695 SCIP_Real* lpcandssol; 696 SCIP_ROW** lprows; 697 SCIP_Real* minactivities; 698 SCIP_Real* maxactivities; 699 SCIP_ROW** violrows; 700 SCIP_Real* nincreases; 701 SCIP_Real* ndecreases; 702 int* violrowpos; 703 int* nfracsinrow; 704 SCIP_Real increaseweight; 705 SCIP_Real obj; 706 SCIP_Real bestshiftval; 707 SCIP_Real minobj; 708 int nlpcands; 709 int nlprows; 710 int nvars; 711 int nfrac; 712 int nviolrows; 713 int nviolfracrows; 714 int nprevviolrows; 715 int minnviolrows; 716 int nnonimprovingshifts; 717 int c; 718 int r; 719 SCIP_Longint nlps; 720 SCIP_Longint ncalls; 721 SCIP_Longint nsolsfound; 722 SCIP_Longint nnodes; 723 724 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 725 assert(scip != NULL); 726 assert(result != NULL); 727 assert(SCIPhasCurrentNodeLP(scip)); 728 729 *result = SCIP_DIDNOTRUN; 730 731 /* do not call heuristic of node was already detected to be infeasible */ 732 if( nodeinfeasible ) 733 return SCIP_OKAY; 734 735 /* don't call heuristic, if no continuous variables are present 736 * -> in this case, it is equivalent to shifting heuristic 737 */ 738 if( SCIPgetNContVars(scip) == 0 ) 739 return SCIP_OKAY; 740 741 /* only call heuristic, if an optimal LP solution is at hand */ 742 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 743 return SCIP_OKAY; 744 745 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */ 746 if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) ) 747 return SCIP_OKAY; 748 749 /* get heuristic data */ 750 heurdata = SCIPheurGetData(heur); 751 assert(heurdata != NULL); 752 753 /* don't call heuristic, if we have already processed the current LP solution */ 754 nlps = SCIPgetNLPs(scip); 755 if( nlps == heurdata->lastlp ) 756 return SCIP_OKAY; 757 heurdata->lastlp = nlps; 758 759 /* don't call heuristic, if it was not successful enough in the past */ 760 ncalls = SCIPheurGetNCalls(heur); 761 nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + SCIPheurGetNSolsFound(heur); 762 nnodes = SCIPgetNNodes(scip); 763 if( nnodes % (ncalls/(nsolsfound+1)+1) != 0 ) /*?????????? ncalls/100 */ 764 return SCIP_OKAY; 765 766 /* get fractional variables, that should be integral */ 767 /* todo check if heuristic should include implicit integer variables for its calculations */ 768 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL) ); 769 nfrac = nlpcands; 770 771 /* only call heuristic, if LP solution is fractional */ 772 if( nfrac == 0 ) 773 return SCIP_OKAY; 774 775 *result = SCIP_DIDNOTFIND; 776 777 /* get LP rows */ 778 SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) ); 779 780 SCIPdebugMsg(scip, "executing intshifting heuristic: %d LP rows, %d fractionals\n", nlprows, nfrac); 781 782 /* get memory for activities, violated rows, and row violation positions */ 783 nvars = SCIPgetNVars(scip); 784 SCIP_CALL( SCIPallocBufferArray(scip, &minactivities, nlprows) ); 785 SCIP_CALL( SCIPallocBufferArray(scip, &maxactivities, nlprows) ); 786 SCIP_CALL( SCIPallocBufferArray(scip, &violrows, nlprows) ); 787 SCIP_CALL( SCIPallocBufferArray(scip, &violrowpos, nlprows) ); 788 SCIP_CALL( SCIPallocBufferArray(scip, &nfracsinrow, nlprows) ); 789 SCIP_CALL( SCIPallocBufferArray(scip, &nincreases, nvars) ); 790 SCIP_CALL( SCIPallocBufferArray(scip, &ndecreases, nvars) ); 791 BMSclearMemoryArray(nfracsinrow, nlprows); 792 BMSclearMemoryArray(nincreases, nvars); 793 BMSclearMemoryArray(ndecreases, nvars); 794 795 /* get the minimal and maximal activity for all globally valid rows for continuous variables in their full range; 796 * these are the values of a*x' with x' being the LP solution for integer variables and the lower or upper bound 797 * for the continuous variables 798 */ 799 nviolrows = 0; 800 for( r = 0; r < nlprows; ++r ) 801 { 802 SCIP_ROW* row; 803 804 row = lprows[r]; 805 assert(SCIProwGetLPPos(row) == r); 806 807 if( !SCIProwIsLocal(row) ) 808 { 809 SCIP_COL** cols; 810 SCIP_Real* vals; 811 int nnonz; 812 SCIP_Bool mininf; 813 SCIP_Bool maxinf; 814 815 mininf = FALSE; 816 maxinf = FALSE; 817 minactivities[r] = 0.0; 818 maxactivities[r] = 0.0; 819 cols = SCIProwGetCols(row); 820 vals = SCIProwGetVals(row); 821 nnonz = SCIProwGetNNonz(row); 822 for( c = 0; c < nnonz && !(mininf && maxinf); ++c ) 823 { 824 SCIP_VAR* var; 825 826 var = SCIPcolGetVar(cols[c]); 827 if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER ) 828 { 829 SCIP_Real act; 830 831 act = vals[c] * SCIPcolGetPrimsol(cols[c]); 832 minactivities[r] += act; 833 maxactivities[r] += act; 834 } 835 else if( vals[c] > 0.0 ) 836 { 837 SCIP_Real lb; 838 SCIP_Real ub; 839 840 lb = SCIPvarGetLbGlobal(var); 841 ub = SCIPvarGetUbGlobal(var); 842 if( SCIPisInfinity(scip, -lb) ) 843 mininf = TRUE; 844 else 845 minactivities[r] += vals[c] * lb; 846 if( SCIPisInfinity(scip, ub) ) 847 maxinf = TRUE; 848 else 849 maxactivities[r] += vals[c] * ub; 850 } 851 else if( vals[c] < 0.0 ) 852 { 853 SCIP_Real lb; 854 SCIP_Real ub; 855 856 lb = SCIPvarGetLbGlobal(var); 857 ub = SCIPvarGetUbGlobal(var); 858 if( SCIPisInfinity(scip, ub) ) 859 mininf = TRUE; 860 else 861 minactivities[r] += vals[c] * ub; 862 if( SCIPisInfinity(scip, -lb) ) 863 maxinf = TRUE; 864 else 865 maxactivities[r] += vals[c] * lb; 866 } 867 868 if( mininf ) 869 minactivities[r] = -SCIPinfinity(scip); 870 if( maxinf ) 871 maxactivities[r] = SCIPinfinity(scip); 872 } 873 874 if( SCIPisFeasLT(scip, maxactivities[r], SCIProwGetLhs(row)) 875 || SCIPisFeasGT(scip, minactivities[r], SCIProwGetRhs(row)) ) 876 { 877 violrows[nviolrows] = row; 878 violrowpos[r] = nviolrows; 879 nviolrows++; 880 } 881 else 882 violrowpos[r] = -1; 883 } 884 else 885 /* if row is a local row */ 886 violrowpos[r] = -1; 887 } 888 889 nviolfracrows = 0; 890 /* calc the current number of fractional variables in rows */ 891 for( c = 0; c < nlpcands; ++c ) 892 addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, lpcands[c], +1); 893 894 /* get the working solution from heuristic's local data */ 895 sol = heurdata->sol; 896 assert(sol != NULL); 897 898 /* copy the current LP solution to the working solution */ 899 SCIP_CALL( SCIPlinkLPSol(scip, sol) ); 900 901 /* calculate the minimal objective value possible after rounding fractional variables */ 902 minobj = SCIPgetSolTransObj(scip, sol); 903 assert(minobj < SCIPgetCutoffbound(scip)); 904 for( c = 0; c < nlpcands; ++c ) 905 { 906 obj = SCIPvarGetObj(lpcands[c]); 907 bestshiftval = obj > 0.0 ? SCIPfeasFloor(scip, lpcandssol[c]) : SCIPfeasCeil(scip, lpcandssol[c]); 908 minobj += obj * (bestshiftval - lpcandssol[c]); 909 } 910 911 /* try to shift remaining variables in order to become/stay feasible */ 912 nnonimprovingshifts = 0; 913 minnviolrows = INT_MAX; 914 increaseweight = 1.0; 915 while( (nfrac > 0 || nviolrows > 0) && nnonimprovingshifts < MAXSHIFTINGS && !SCIPisStopped(scip) ) 916 { 917 SCIP_VAR* shiftvar; 918 SCIP_Real oldsolval; 919 SCIP_Real newsolval; 920 SCIP_Bool oldsolvalisfrac; 921 int probindex; 922 923 SCIPdebugMsg(scip, "intshifting heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g), cutoff=%g\n", 924 nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj), 925 SCIPretransformObj(scip, SCIPgetCutoffbound(scip))); 926 927 nprevviolrows = nviolrows; 928 929 /* choose next variable to process: 930 * - if a violated row exists, shift a variable decreasing the violation, that has least impact on other rows 931 * - otherwise, shift a variable, that has strongest devastating impact on rows in opposite direction 932 */ 933 shiftvar = NULL; 934 oldsolval = 0.0; 935 newsolval = 0.0; 936 if( nviolrows > 0 && (nfrac == 0 || nnonimprovingshifts < MAXSHIFTINGS-1) ) 937 { 938 SCIP_ROW* row; 939 int rowidx; 940 int rowpos; 941 int direction; 942 943 assert(nviolfracrows == 0 || nfrac > 0); 944 /* violated rows containing fractional variables are preferred; if such a row exists, choose the last one from the list 945 * (at position nviolfracrows - 1) because removing this row will cause one swapping operation less than other rows 946 */ 947 if( nviolfracrows > 0 ) 948 rowidx = nviolfracrows - 1; 949 else 950 rowidx = SCIPrandomGetInt(heurdata->randnumgen, 0, nviolrows-1); 951 952 assert(0 <= rowidx && rowidx < nviolrows); 953 row = violrows[rowidx]; 954 rowpos = SCIProwGetLPPos(row); 955 assert(0 <= rowpos && rowpos < nlprows); 956 assert(violrowpos[rowpos] == rowidx); 957 assert(nfracsinrow[rowpos] == 0 || rowidx == nviolfracrows - 1); 958 959 SCIPdebugMsg(scip, "intshifting heuristic: try to fix violated row <%s>: %g <= [%g,%g] <= %g\n", 960 SCIProwGetName(row), SCIProwGetLhs(row), minactivities[rowpos], maxactivities[rowpos], SCIProwGetRhs(row)); 961 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) ); 962 963 /* get direction in which activity must be shifted */ 964 assert(SCIPisFeasLT(scip, maxactivities[rowpos], SCIProwGetLhs(row)) 965 || SCIPisFeasGT(scip, minactivities[rowpos], SCIProwGetRhs(row))); 966 direction = SCIPisFeasLT(scip, maxactivities[rowpos], SCIProwGetLhs(row)) ? +1 : -1; 967 968 /* search an integer variable that can shift the activity in the necessary direction */ 969 SCIP_CALL( selectShifting(scip, sol, row, direction == +1 ? maxactivities[rowpos] : minactivities[rowpos], 970 direction, nincreases, ndecreases, increaseweight, &shiftvar, &oldsolval, &newsolval) ); 971 } 972 973 if( shiftvar == NULL && nfrac > 0 ) 974 { 975 SCIPdebugMsg(scip, "intshifting heuristic: search rounding variable and try to stay feasible\n"); 976 SCIP_CALL( selectEssentialRounding(scip, sol, minobj, lpcands, nlpcands, &shiftvar, &oldsolval, &newsolval) ); 977 } 978 979 /* check, whether shifting was possible */ 980 if( shiftvar == NULL || SCIPisEQ(scip, oldsolval, newsolval) ) 981 { 982 SCIPdebugMsg(scip, "intshifting heuristic: -> didn't find a shifting variable\n"); 983 break; 984 } 985 986 assert(SCIPvarGetType(shiftvar) == SCIP_VARTYPE_BINARY || SCIPvarGetType(shiftvar) == SCIP_VARTYPE_INTEGER); 987 988 SCIPdebugMsg(scip, "intshifting heuristic: -> shift var <%s>[%g,%g], type=%d, oldval=%g, newval=%g, obj=%g\n", 989 SCIPvarGetName(shiftvar), SCIPvarGetLbGlobal(shiftvar), SCIPvarGetUbGlobal(shiftvar), SCIPvarGetType(shiftvar), 990 oldsolval, newsolval, SCIPvarGetObj(shiftvar)); 991 992 /* update row activities of globally valid rows */ 993 SCIP_CALL( updateActivities(scip, minactivities, maxactivities, violrows, violrowpos, &nviolrows, &nviolfracrows, 994 nfracsinrow, nlprows, shiftvar, oldsolval, newsolval) ); 995 996 if( nviolrows >= nprevviolrows ) 997 nnonimprovingshifts++; 998 else if( nviolrows < minnviolrows ) 999 { 1000 minnviolrows = nviolrows; 1001 nnonimprovingshifts = 0; 1002 } 1003 1004 /* store new solution value and decrease fractionality counter */ 1005 SCIP_CALL( SCIPsetSolVal(scip, sol, shiftvar, newsolval) ); 1006 1007 /* update fractionality counter and minimal objective value possible after shifting remaining variables */ 1008 oldsolvalisfrac = !SCIPisFeasIntegral(scip, oldsolval); 1009 obj = SCIPvarGetObj(shiftvar); 1010 if( oldsolvalisfrac ) 1011 { 1012 assert(SCIPisFeasIntegral(scip, newsolval)); 1013 nfrac--; 1014 nnonimprovingshifts = 0; 1015 minnviolrows = INT_MAX; 1016 addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, shiftvar, -1); 1017 1018 /* the rounding was already calculated into the minobj -> update only if rounding in "wrong" direction */ 1019 if( obj > 0.0 && newsolval > oldsolval ) 1020 minobj += obj; 1021 else if( obj < 0.0 && newsolval < oldsolval ) 1022 minobj -= obj; 1023 } 1024 else 1025 { 1026 /* update minimal possible objective value */ 1027 minobj += obj * (newsolval - oldsolval); 1028 } 1029 1030 /* update increase/decrease arrays */ 1031 if( !oldsolvalisfrac ) 1032 { 1033 probindex = SCIPvarGetProbindex(shiftvar); 1034 assert(0 <= probindex && probindex < nvars); 1035 increaseweight *= WEIGHTFACTOR; 1036 if( newsolval < oldsolval ) 1037 ndecreases[probindex] += increaseweight; 1038 else 1039 nincreases[probindex] += increaseweight; 1040 if( increaseweight >= 1e+09 ) 1041 { 1042 int i; 1043 1044 for( i = 0; i < nvars; ++i ) 1045 { 1046 nincreases[i] /= increaseweight; 1047 ndecreases[i] /= increaseweight; 1048 } 1049 increaseweight = 1.0; 1050 } 1051 } 1052 1053 SCIPdebugMsg(scip, "intshifting heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n", 1054 nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj)); 1055 } 1056 1057 /* check, if the new solution is potentially feasible and solve the LP to calculate values for the continuous 1058 * variables 1059 */ 1060 if( nfrac == 0 && nviolrows == 0 ) 1061 { 1062 SCIP_VAR** vars; 1063 SCIP_Bool lperror; 1064 int nintvars; 1065 int v; 1066 #ifdef NDEBUG 1067 SCIP_RETCODE retstat; 1068 #endif 1069 1070 SCIPdebugMsg(scip, "shifted solution is potentially feasible -> solve LP to fix continuous variables\n"); 1071 1072 /* start diving to calculate the LP relaxation */ 1073 SCIP_CALL( SCIPstartDive(scip) ); 1074 1075 /* set the bounds of the variables: fixed for integers, global bounds for continuous */ 1076 vars = SCIPgetVars(scip); 1077 nintvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip); 1078 for( v = 0; v < nvars; ++v ) 1079 { 1080 if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN ) 1081 { 1082 SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], SCIPvarGetLbGlobal(vars[v])) ); 1083 SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], SCIPvarGetUbGlobal(vars[v])) ); 1084 } 1085 } 1086 for( v = 0; v < nintvars; ++v ) /* apply this after global bounds to not cause an error with intermediate empty domains */ 1087 { 1088 if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN ) 1089 { 1090 SCIP_Real solval; 1091 solval = SCIPgetSolVal(scip, sol, vars[v]); 1092 SCIP_CALL( SCIPchgVarLbDive(scip, vars[v], solval) ); 1093 SCIP_CALL( SCIPchgVarUbDive(scip, vars[v], solval) ); 1094 } 1095 } 1096 1097 /* solve LP */ 1098 SCIPdebugMsg(scip, " -> old LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip)); 1099 1100 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic. 1101 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 1102 */ 1103 #ifdef NDEBUG 1104 retstat = SCIPsolveDiveLP(scip, -1, &lperror, NULL); 1105 if( retstat != SCIP_OKAY ) 1106 { 1107 SCIPwarningMessage(scip, "Error while solving LP in Intshifting heuristic; LP solve terminated with code <%d>\n",retstat); 1108 } 1109 #else 1110 SCIP_CALL( SCIPsolveDiveLP(scip, -1, &lperror, NULL) ); 1111 #endif 1112 1113 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip)); 1114 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, SCIPgetLPSolstat(scip)); 1115 1116 /* check if this is a feasible solution */ 1117 if( !lperror && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL ) 1118 { 1119 SCIP_Bool stored; 1120 1121 /* copy the current LP solution to the working solution */ 1122 SCIP_CALL( SCIPlinkLPSol(scip, sol) ); 1123 1124 /* check solution for feasibility, and add it to solution store if possible 1125 * neither integrality nor feasibility of LP rows has to be checked, because this is already 1126 * done in the intshifting heuristic itself and due to the LP resolve 1127 */ 1128 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) ); 1129 1130 if( stored ) 1131 { 1132 SCIPdebugMsg(scip, "found feasible shifted solution:\n"); 1133 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ) ); 1134 *result = SCIP_FOUNDSOL; 1135 } 1136 } 1137 1138 /* terminate the diving */ 1139 SCIP_CALL( SCIPendDive(scip) ); 1140 } 1141 1142 /* free memory buffers */ 1143 SCIPfreeBufferArray(scip, &ndecreases); 1144 SCIPfreeBufferArray(scip, &nincreases); 1145 SCIPfreeBufferArray(scip, &nfracsinrow); 1146 SCIPfreeBufferArray(scip, &violrowpos); 1147 SCIPfreeBufferArray(scip, &violrows); 1148 SCIPfreeBufferArray(scip, &maxactivities); 1149 SCIPfreeBufferArray(scip, &minactivities); 1150 1151 return SCIP_OKAY; 1152 } 1153 1154 1155 /* 1156 * heuristic specific interface methods 1157 */ 1158 1159 /** creates the intshifting heuristic with infeasibility recovering and includes it in SCIP */ 1160 SCIP_RETCODE SCIPincludeHeurIntshifting( 1161 SCIP* scip /**< SCIP data structure */ 1162 ) 1163 { 1164 SCIP_HEUR* heur; 1165 1166 /* include primal heuristic */ 1167 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1168 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1169 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIntshifting, NULL) ); 1170 1171 assert(heur != NULL); 1172 1173 /* set non-NULL pointers to callback methods */ 1174 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIntshifting) ); 1175 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIntshifting) ); 1176 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIntshifting) ); 1177 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolIntshifting) ); 1178 1179 return SCIP_OKAY; 1180 } 1181