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