Scippy

SCIP

Solving Constraint Integer Programs

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