Scippy

SCIP

Solving Constraint Integer Programs

heur_shifting.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_shifting.c
17  * @brief LP rounding heuristic that tries to recover from intermediate infeasibilities and shifts continuous variables
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/heur_shifting.h"
27 #include "scip/pub_misc.h"
28 
29 
30 #define HEUR_NAME "shifting"
31 #define HEUR_DESC "LP rounding heuristic with infeasibility recovering also using continuous variables"
32 #define HEUR_DISPCHAR 's'
33 #define HEUR_PRIORITY -5000
34 #define HEUR_FREQ 10
35 #define HEUR_FREQOFS 0
36 #define HEUR_MAXDEPTH -1
37 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP
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 31 /**< initial random seed */
43 
44 
45 /* locally defined heuristic data */
46 struct SCIP_HeurData
47 {
48  SCIP_SOL* sol; /**< working solution */
49  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
50  SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */
51 };
52 
53 
54 /*
55  * local methods
56  */
57 
58 /** update row violation arrays after a row's activity value changed */
59 static
61  SCIP* scip, /**< SCIP data structure */
62  SCIP_ROW* row, /**< LP row */
63  SCIP_ROW** violrows, /**< array with currently violated rows */
64  int* violrowpos, /**< position of LP rows in violrows array */
65  int* nviolrows, /**< pointer to the number of currently violated rows */
66  int* nviolfracrows, /**< pointer to the number of violated rows with fractional candidates */
67  int* nfracsinrow, /**< array with number of fractional variables for every row */
68  SCIP_Real oldactivity, /**< old activity value of LP row */
69  SCIP_Real newactivity /**< new activity value of LP row */
70  )
71 {
72  SCIP_Real lhs;
73  SCIP_Real rhs;
74  SCIP_Bool oldviol;
75  SCIP_Bool newviol;
76 
77  assert(violrows != NULL);
78  assert(violrowpos != NULL);
79  assert(nviolrows != NULL);
80 
81  lhs = SCIProwGetLhs(row);
82  rhs = SCIProwGetRhs(row);
83  oldviol = (SCIPisFeasLT(scip, oldactivity, lhs) || SCIPisFeasGT(scip, oldactivity, rhs));
84  newviol = (SCIPisFeasLT(scip, newactivity, lhs) || SCIPisFeasGT(scip, newactivity, rhs));
85  if( oldviol != newviol )
86  {
87  int rowpos;
88  int violpos;
89 
90  rowpos = SCIProwGetLPPos(row);
91  assert(rowpos >= 0);
92 
93  if( oldviol )
94  {
95  /* the row violation was repaired: remove row from violrows array, decrease violation count */
96  violpos = violrowpos[rowpos];
97  assert(0 <= violpos && violpos < *nviolrows);
98  assert(violrows[violpos] == row);
99  violrowpos[rowpos] = -1;
100 
101  /* first, move the row to the end of the subset of violated rows with fractional variables */
102  if( nfracsinrow[rowpos] > 0 )
103  {
104  assert(violpos < *nviolfracrows);
105 
106  /* replace with last violated row containing fractional variables */
107  if( violpos != *nviolfracrows - 1 )
108  {
109  violrows[violpos] = violrows[*nviolfracrows - 1];
110  violrowpos[SCIProwGetLPPos(violrows[violpos])] = violpos;
111  violpos = *nviolfracrows - 1;
112  }
113  (*nviolfracrows)--;
114  }
115 
116  assert(violpos >= *nviolfracrows);
117 
118  /* swap row at the end of the violated array to the position of this row and decrease the counter */
119  if( violpos != *nviolrows - 1 )
120  {
121  violrows[violpos] = violrows[*nviolrows - 1];
122  violrowpos[SCIProwGetLPPos(violrows[violpos])] = violpos;
123  }
124  (*nviolrows)--;
125  }
126  else
127  {
128  /* the row is now violated: add row to violrows array, increase violation count */
129  assert(violrowpos[rowpos] == -1);
130  violrows[*nviolrows] = row;
131  violrowpos[rowpos] = *nviolrows;
132  (*nviolrows)++;
133 
134  /* if the row contains fractional variables, swap with the last violated row that has no fractional variables
135  * at position *nviolfracrows
136  */
137  if( nfracsinrow[rowpos] > 0 )
138  {
139  if( *nviolfracrows < *nviolrows - 1 )
140  {
141  assert(nfracsinrow[SCIProwGetLPPos(violrows[*nviolfracrows])] == 0);
142 
143  violrows[*nviolrows - 1] = violrows[*nviolfracrows];
144  violrowpos[SCIProwGetLPPos(violrows[*nviolrows - 1])] = *nviolrows - 1;
145 
146  violrows[*nviolfracrows] = row;
147  violrowpos[rowpos] = *nviolfracrows;
148  }
149  (*nviolfracrows)++;
150  }
151  }
152  }
153 }
154 
155 /** update row activities after a variable's solution value changed */
156 static
158  SCIP* scip, /**< SCIP data structure */
159  SCIP_Real* activities, /**< LP row activities */
160  SCIP_ROW** violrows, /**< array with currently violated rows */
161  int* violrowpos, /**< position of LP rows in violrows array */
162  int* nviolrows, /**< pointer to the number of currently violated rows */
163  int* nviolfracrows, /**< pointer to the number of violated rows with fractional candidates */
164  int* nfracsinrow, /**< array with number of fractional variables for every row */
165  int nlprows, /**< number of rows in current LP */
166  SCIP_VAR* var, /**< variable that has been changed */
167  SCIP_Real oldsolval, /**< old solution value of variable */
168  SCIP_Real newsolval /**< new solution value of variable */
169  )
170 {
171  SCIP_COL* col;
172  SCIP_ROW** colrows;
173  SCIP_Real* colvals;
174  SCIP_Real delta;
175  int ncolrows;
176  int r;
177 
178  assert(activities != NULL);
179  assert(nviolrows != NULL);
180  assert(0 <= *nviolrows && *nviolrows <= nlprows);
181 
182  delta = newsolval - oldsolval;
183  col = SCIPvarGetCol(var);
184  colrows = SCIPcolGetRows(col);
185  colvals = SCIPcolGetVals(col);
186  ncolrows = SCIPcolGetNLPNonz(col);
187  assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
188 
189  for( r = 0; r < ncolrows; ++r )
190  {
191  SCIP_ROW* row;
192  int rowpos;
193 
194  row = colrows[r];
195  rowpos = SCIProwGetLPPos(row);
196  assert(-1 <= rowpos && rowpos < nlprows);
197 
198  if( rowpos >= 0 && !SCIProwIsLocal(row) )
199  {
200  SCIP_Real oldactivity;
201  SCIP_Real newactivity;
202 
203  assert(SCIProwIsInLP(row));
204 
205  /* update row activity */
206  oldactivity = activities[rowpos];
207  if( !SCIPisInfinity(scip, -oldactivity) && !SCIPisInfinity(scip, oldactivity) )
208  {
209  newactivity = oldactivity + delta * colvals[r];
210  if( SCIPisInfinity(scip, newactivity) )
211  newactivity = SCIPinfinity(scip);
212  else if( SCIPisInfinity(scip, -newactivity) )
213  newactivity = -SCIPinfinity(scip);
214  activities[rowpos] = newactivity;
215 
216  /* update row violation arrays */
217  updateViolations(scip, row, violrows, violrowpos, nviolrows, nviolfracrows, nfracsinrow, oldactivity, newactivity);
218  }
219  }
220  }
221 
222  return SCIP_OKAY;
223 }
224 
225 /** returns a variable, that pushes activity of the row in the given direction with minimal negative impact on other rows;
226  * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
227  * prefer fractional integers over other variables in order to become integral during the process;
228  * shifting in a direction is forbidden, if this forces the objective value over the upper bound, or if the variable
229  * was already shifted in the opposite direction
230  */
231 static
233  SCIP* scip, /**< SCIP data structure */
234  SCIP_SOL* sol, /**< primal solution */
235  SCIP_ROW* row, /**< LP row */
236  SCIP_Real rowactivity, /**< activity of LP row */
237  int direction, /**< should the activity be increased (+1) or decreased (-1)? */
238  SCIP_Real* nincreases, /**< array with weighted number of increasings per variables */
239  SCIP_Real* ndecreases, /**< array with weighted number of decreasings per variables */
240  SCIP_Real increaseweight, /**< current weight of increase/decrease updates */
241  SCIP_VAR** shiftvar, /**< pointer to store the shifting variable, returns NULL if impossible */
242  SCIP_Real* oldsolval, /**< pointer to store old solution value of shifting variable */
243  SCIP_Real* newsolval /**< pointer to store new (shifted) solution value of shifting variable */
244  )
245 {
246  SCIP_COL** rowcols;
247  SCIP_Real* rowvals;
248  int nrowcols;
249  SCIP_Real activitydelta;
250  SCIP_Real bestshiftscore;
251  SCIP_Real bestdeltaobj;
252  int c;
253 
254  assert(direction == +1 || direction == -1);
255  assert(nincreases != NULL);
256  assert(ndecreases != NULL);
257  assert(shiftvar != NULL);
258  assert(oldsolval != NULL);
259  assert(newsolval != NULL);
260 
261  /* get row entries */
262  rowcols = SCIProwGetCols(row);
263  rowvals = SCIProwGetVals(row);
264  nrowcols = SCIProwGetNLPNonz(row);
265 
266  /* calculate how much the activity must be shifted in order to become feasible */
267  activitydelta = (direction == +1 ? SCIProwGetLhs(row) - rowactivity : SCIProwGetRhs(row) - rowactivity);
268  assert((direction == +1 && SCIPisPositive(scip, activitydelta))
269  || (direction == -1 && SCIPisNegative(scip, activitydelta)));
270 
271  /* select shifting variable */
272  bestshiftscore = SCIP_REAL_MAX;
273  bestdeltaobj = SCIPinfinity(scip);
274  *shiftvar = NULL;
275  *newsolval = 0.0;
276  *oldsolval = 0.0;
277  for( c = 0; c < nrowcols; ++c )
278  {
279  SCIP_COL* col;
280  SCIP_VAR* var;
281  SCIP_Real val;
282  SCIP_Real solval;
283  SCIP_Real shiftval;
284  SCIP_Real shiftscore;
285  SCIP_Bool isinteger;
286  SCIP_Bool isfrac;
287  SCIP_Bool increase;
288 
289  col = rowcols[c];
290  var = SCIPcolGetVar(col);
291  val = rowvals[c];
292  assert(!SCIPisZero(scip, val));
293  solval = SCIPgetSolVal(scip, sol, var);
294 
296  isfrac = (isinteger && !SCIPisFeasIntegral(scip, solval));
297  increase = (direction * val > 0.0);
298 
299  /* calculate the score of the shifting (prefer smaller values) */
300  if( isfrac )
301  shiftscore = increase ? -1.0 / (SCIPvarGetNLocksUp(var) + 1.0) :
302  -1.0 / (SCIPvarGetNLocksDown(var) + 1.0);
303  else
304  {
305  int probindex;
306  probindex = SCIPvarGetProbindex(var);
307 
308  if( increase )
309  shiftscore = ndecreases[probindex]/increaseweight;
310  else
311  shiftscore = nincreases[probindex]/increaseweight;
312  if( isinteger )
313  shiftscore += 1.0;
314  }
315 
316  if( shiftscore <= bestshiftscore )
317  {
318  SCIP_Real deltaobj;
319 
320  if( !increase )
321  {
322  /* shifting down */
323  assert(direction * val < 0.0);
324  if( isfrac )
325  shiftval = SCIPfeasFloor(scip, solval);
326  else
327  {
328  SCIP_Real lb;
329 
330  assert(activitydelta/val < 0.0);
331  shiftval = solval + activitydelta/val;
332  assert(shiftval <= solval); /* may be equal due to numerical digit erasement in the subtraction */
333  if( SCIPvarIsIntegral(var) )
334  shiftval = SCIPfeasFloor(scip, shiftval);
335  lb = SCIPvarGetLbGlobal(var);
336  shiftval = MAX(shiftval, lb);
337  }
338  }
339  else
340  {
341  /* shifting up */
342  assert(direction * val > 0.0);
343  if( isfrac )
344  shiftval = SCIPfeasCeil(scip, solval);
345  else
346  {
347  SCIP_Real ub;
348 
349  assert(activitydelta/val > 0.0);
350  shiftval = solval + activitydelta/val;
351  assert(shiftval >= solval); /* may be equal due to numerical digit erasement in the subtraction */
352  if( SCIPvarIsIntegral(var) )
353  shiftval = SCIPfeasCeil(scip, shiftval);
354  ub = SCIPvarGetUbGlobal(var);
355  shiftval = MIN(shiftval, ub);
356  }
357  }
358 
359  if( (SCIPisInfinity(scip, shiftval) && SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)))
360  || (SCIPisInfinity(scip, -shiftval) && SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)))
361  || SCIPisEQ(scip, shiftval, solval) )
362  continue;
363 
364  deltaobj = SCIPvarGetObj(var) * (shiftval - solval);
365  if( shiftscore < bestshiftscore || deltaobj < bestdeltaobj )
366  {
367  bestshiftscore = shiftscore;
368  bestdeltaobj = deltaobj;
369  *shiftvar = var;
370  *oldsolval = solval;
371  *newsolval = shiftval;
372  }
373  }
374  }
375 
376  return SCIP_OKAY;
377 }
378 
379 /** returns a fractional variable, that has most impact on rows in opposite direction, i.e. that is most crucial to
380  * fix in the other direction;
381  * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
382  * shifting in a direction is forbidden, if this forces the objective value over the upper bound
383  */
384 static
386  SCIP* scip, /**< SCIP data structure */
387  SCIP_SOL* sol, /**< primal solution */
388  SCIP_Real minobj, /**< minimal objective value possible after shifting remaining fractional vars */
389  SCIP_VAR** lpcands, /**< fractional variables in LP */
390  int nlpcands, /**< number of fractional variables in LP */
391  SCIP_VAR** shiftvar, /**< pointer to store the shifting variable, returns NULL if impossible */
392  SCIP_Real* oldsolval, /**< old (fractional) solution value of shifting variable */
393  SCIP_Real* newsolval /**< new (shifted) solution value of shifting variable */
394  )
395 {
396  SCIP_VAR* var;
397  SCIP_Real solval;
398  SCIP_Real shiftval;
399  SCIP_Real obj;
400  SCIP_Real deltaobj;
401  SCIP_Real bestdeltaobj;
402  int maxnlocks;
403  int nlocks;
404  int v;
405 
406  assert(shiftvar != NULL);
407  assert(oldsolval != NULL);
408  assert(newsolval != NULL);
409 
410  /* select shifting variable */
411  maxnlocks = -1;
412  bestdeltaobj = SCIPinfinity(scip);
413  *shiftvar = NULL;
414  for( v = 0; v < nlpcands; ++v )
415  {
416  var = lpcands[v];
418 
419  solval = SCIPgetSolVal(scip, sol, var);
420  if( !SCIPisFeasIntegral(scip, solval) )
421  {
422  obj = SCIPvarGetObj(var);
423 
424  /* shifting down */
425  nlocks = SCIPvarGetNLocksUp(var);
426  if( nlocks >= maxnlocks )
427  {
428  shiftval = SCIPfeasFloor(scip, solval);
429  deltaobj = obj * (shiftval - solval);
430  if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj - obj < SCIPgetCutoffbound(scip) )
431  {
432  maxnlocks = nlocks;
433  bestdeltaobj = deltaobj;
434  *shiftvar = var;
435  *oldsolval = solval;
436  *newsolval = shiftval;
437  }
438  }
439 
440  /* shifting up */
441  nlocks = SCIPvarGetNLocksDown(var);
442  if( nlocks >= maxnlocks )
443  {
444  shiftval = SCIPfeasCeil(scip, solval);
445  deltaobj = obj * (shiftval - solval);
446  if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj + obj < SCIPgetCutoffbound(scip) )
447  {
448  maxnlocks = nlocks;
449  bestdeltaobj = deltaobj;
450  *shiftvar = var;
451  *oldsolval = solval;
452  *newsolval = shiftval;
453  }
454  }
455  }
456  }
457 
458  return SCIP_OKAY;
459 }
460 
461 /** adds a given value to the fractionality counters of the rows in which the given variable appears */
462 static
464  int* nfracsinrow, /**< array to store number of fractional variables per row */
465  SCIP_ROW** violrows, /**< array with currently violated rows */
466  int* violrowpos, /**< position of LP rows in violrows array */
467  int* nviolfracrows, /**< pointer to store the number of violated rows with fractional variables */
468  int nviolrows, /**< the number of currently violated rows (stays unchanged in this method) */
469  int nlprows, /**< number of rows in LP */
470  SCIP_VAR* var, /**< variable for which the counting should be updated */
471  int incval /**< value that should be added to the corresponding array entries */
472  )
473 {
474  SCIP_COL* col;
475  SCIP_ROW** rows;
476  int nrows;
477  int r;
478 
479  assert(incval != 0);
480  assert(nviolrows >= *nviolfracrows);
481  col = SCIPvarGetCol(var);
482  rows = SCIPcolGetRows(col);
483  nrows = SCIPcolGetNLPNonz(col);
484  for( r = 0; r < nrows; ++r )
485  {
486  int rowlppos;
487  int theviolrowpos;
488 
489  rowlppos = SCIProwGetLPPos(rows[r]);
490  assert(0 <= rowlppos && rowlppos < nlprows);
491  assert(!SCIProwIsLocal(rows[r]) || violrowpos[rowlppos] == -1);
492 
493  /* skip local rows */
494  if( SCIProwIsLocal(rows[r]) )
495  continue;
496 
497  nfracsinrow[rowlppos] += incval;
498  assert(nfracsinrow[rowlppos] >= 0);
499  theviolrowpos = violrowpos[rowlppos];
500 
501 
502  /* swap positions in violrows array if fractionality has changed to 0 */
503  if( theviolrowpos >= 0 )
504  {
505  /* first case: the number of fractional variables has become zero: swap row in violrows array to the
506  * second part, containing only violated rows without fractional variables
507  */
508  if( nfracsinrow[rowlppos] == 0 )
509  {
510  assert(theviolrowpos <= *nviolfracrows - 1);
511 
512  /* nothing to do if row is already at the end of the first part, otherwise, swap it to the last position
513  * and decrease the counter */
514  if( theviolrowpos < *nviolfracrows - 1 )
515  {
516  violrows[theviolrowpos] = violrows[*nviolfracrows - 1];
517  violrows[*nviolfracrows - 1] = rows[r];
518 
519 
520  violrowpos[SCIProwGetLPPos(violrows[theviolrowpos])] = theviolrowpos;
521  violrowpos[rowlppos] = *nviolfracrows - 1;
522  }
523  (*nviolfracrows)--;
524  }
525  /* second interesting case: the number of fractional variables was zero before, swap it with the first
526  * violated row without fractional variables
527  */
528  else if( nfracsinrow[rowlppos] == incval )
529  {
530  assert(theviolrowpos >= *nviolfracrows);
531 
532  /* nothing to do if the row is exactly located at index *nviolfracrows */
533  if( theviolrowpos > *nviolfracrows )
534  {
535  violrows[theviolrowpos] = violrows[*nviolfracrows];
536  violrows[*nviolfracrows] = rows[r];
537 
538 
539  violrowpos[SCIProwGetLPPos(violrows[theviolrowpos])] = theviolrowpos;
540  violrowpos[rowlppos] = *nviolfracrows;
541  }
542  (*nviolfracrows)++;
543  }
544  }
545  }
546 }
547 
548 
549 /*
550  * Callback methods
551  */
552 
553 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
554 static
555 SCIP_DECL_HEURCOPY(heurCopyShifting)
556 { /*lint --e{715}*/
557  assert(scip != NULL);
558  assert(heur != NULL);
559  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
560 
561  /* call inclusion method of primal heuristic */
563 
564  return SCIP_OKAY;
565 }
566 
567 
568 /** initialization method of primal heuristic (called after problem was transformed) */
569 static
570 SCIP_DECL_HEURINIT(heurInitShifting) /*lint --e{715}*/
571 { /*lint --e{715}*/
572  SCIP_HEURDATA* heurdata;
573 
574  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
575  assert(SCIPheurGetData(heur) == NULL);
576 
577  /* create heuristic data */
578  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
579  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
580  heurdata->lastlp = -1;
581 
582  /* create random number generator */
583  SCIP_CALL( SCIPrandomCreate(&heurdata->randnumgen, SCIPblkmem(scip),
585 
586  SCIPheurSetData(heur, heurdata);
587 
588  return SCIP_OKAY;
589 }
590 
591 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
592 static
593 SCIP_DECL_HEUREXIT(heurExitShifting) /*lint --e{715}*/
594 { /*lint --e{715}*/
595  SCIP_HEURDATA* heurdata;
596 
597  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
598 
599  /* free heuristic data */
600  heurdata = SCIPheurGetData(heur);
601  assert(heurdata != NULL);
602  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
603 
604  /* free random number generator */
605  SCIPrandomFree(&heurdata->randnumgen);
606 
607  SCIPfreeBlockMemory(scip, &heurdata);
608  SCIPheurSetData(heur, NULL);
609 
610  return SCIP_OKAY;
611 }
612 
613 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
614 static
615 SCIP_DECL_HEURINITSOL(heurInitsolShifting)
616 {
617  SCIP_HEURDATA* heurdata;
618 
619  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
620 
621  heurdata = SCIPheurGetData(heur);
622  assert(heurdata != NULL);
623  heurdata->lastlp = -1;
624 
625  return SCIP_OKAY;
626 }
627 
628 
629 /** execution method of primal heuristic */
630 static
631 SCIP_DECL_HEUREXEC(heurExecShifting) /*lint --e{715}*/
632 { /*lint --e{715}*/
633  SCIP_HEURDATA* heurdata;
634  SCIP_SOL* sol;
635  SCIP_VAR** lpcands;
636  SCIP_Real* lpcandssol;
637  SCIP_ROW** lprows;
638  SCIP_Real* activities;
639  SCIP_ROW** violrows;
640  SCIP_Real* nincreases;
641  SCIP_Real* ndecreases;
642  int* violrowpos;
643  int* nfracsinrow;
644  SCIP_Real increaseweight;
645  SCIP_Real obj;
646  SCIP_Real bestshiftval;
647  SCIP_Real minobj;
648  int nlpcands;
649  int nlprows;
650  int nvars;
651  int nfrac;
652  int nviolrows;
653  int nviolfracrows;
654  int nprevviolrows;
655  int minnviolrows;
656  int nnonimprovingshifts;
657  int c;
658  int r;
659  SCIP_Longint nlps;
660  SCIP_Longint ncalls;
661  SCIP_Longint nsolsfound;
663 
664  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
665  assert(scip != NULL);
666  assert(result != NULL);
667  assert(SCIPhasCurrentNodeLP(scip));
668 
669  *result = SCIP_DIDNOTRUN;
670 
671  /* only call heuristic, if an optimal LP solution is at hand */
673  return SCIP_OKAY;
674 
675  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
677  return SCIP_OKAY;
678 
679  /* get heuristic data */
680  heurdata = SCIPheurGetData(heur);
681  assert(heurdata != NULL);
682 
683  /* don't call heuristic, if we have already processed the current LP solution */
684  nlps = SCIPgetNLPs(scip);
685  if( nlps == heurdata->lastlp )
686  return SCIP_OKAY;
687  heurdata->lastlp = nlps;
688 
689  /* don't call heuristic, if it was not successful enough in the past */
690  ncalls = SCIPheurGetNCalls(heur);
691  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + SCIPheurGetNSolsFound(heur);
692  nnodes = SCIPgetNNodes(scip);
693  if( nnodes % ((ncalls/100)/(nsolsfound+1)+1) != 0 )
694  return SCIP_OKAY;
695 
696  /* get fractional variables, that should be integral */
697  /* todo check if heuristic should include implicit integer variables for its calculations */
698  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL) );
699  nfrac = nlpcands;
700 
701  /* only call heuristic, if LP solution is fractional */
702  if( nfrac == 0 )
703  return SCIP_OKAY;
704 
705  *result = SCIP_DIDNOTFIND;
706 
707  /* get LP rows */
708  SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
709 
710  SCIPdebugMsg(scip, "executing shifting heuristic: %d LP rows, %d fractionals\n", nlprows, nfrac);
711 
712  /* get memory for activities, violated rows, and row violation positions */
713  nvars = SCIPgetNVars(scip);
714  SCIP_CALL( SCIPallocBufferArray(scip, &activities, nlprows) );
715  SCIP_CALL( SCIPallocBufferArray(scip, &violrows, nlprows) );
716  SCIP_CALL( SCIPallocBufferArray(scip, &violrowpos, nlprows) );
717  SCIP_CALL( SCIPallocBufferArray(scip, &nfracsinrow, nlprows) );
718  SCIP_CALL( SCIPallocBufferArray(scip, &nincreases, nvars) );
719  SCIP_CALL( SCIPallocBufferArray(scip, &ndecreases, nvars) );
720  BMSclearMemoryArray(nfracsinrow, nlprows);
721  BMSclearMemoryArray(nincreases, nvars);
722  BMSclearMemoryArray(ndecreases, nvars);
723 
724  /* get the activities for all globally valid rows;
725  * the rows should be feasible, but due to numerical inaccuracies in the LP solver, they can be violated
726  */
727  nviolrows = 0;
728  for( r = 0; r < nlprows; ++r )
729  {
730  SCIP_ROW* row;
731 
732  row = lprows[r];
733  assert(SCIProwGetLPPos(row) == r);
734 
735  if( !SCIProwIsLocal(row) )
736  {
737  activities[r] = SCIPgetRowActivity(scip, row);
738  if( SCIPisFeasLT(scip, activities[r], SCIProwGetLhs(row))
739  || SCIPisFeasGT(scip, activities[r], SCIProwGetRhs(row)) )
740  {
741  violrows[nviolrows] = row;
742  violrowpos[r] = nviolrows;
743  nviolrows++;
744  }
745  else
746  violrowpos[r] = -1;
747  }
748  else
749  violrowpos[r] = -1;
750  }
751 
752  nviolfracrows = 0;
753  /* calc the current number of fractional variables in rows */
754  for( c = 0; c < nlpcands; ++c )
755  addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, lpcands[c], +1);
756 
757  /* get the working solution from heuristic's local data */
758  sol = heurdata->sol;
759  assert(sol != NULL);
760 
761  /* copy the current LP solution to the working solution */
762  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
763 
764  /* calculate the minimal objective value possible after rounding fractional variables */
765  minobj = SCIPgetSolTransObj(scip, sol);
766  assert(minobj < SCIPgetCutoffbound(scip));
767  for( c = 0; c < nlpcands; ++c )
768  {
769  obj = SCIPvarGetObj(lpcands[c]);
770  bestshiftval = obj > 0.0 ? SCIPfeasFloor(scip, lpcandssol[c]) : SCIPfeasCeil(scip, lpcandssol[c]);
771  minobj += obj * (bestshiftval - lpcandssol[c]);
772  }
773 
774  /* try to shift remaining variables in order to become/stay feasible */
775  nnonimprovingshifts = 0;
776  minnviolrows = INT_MAX;
777  increaseweight = 1.0;
778  while( (nfrac > 0 || nviolrows > 0) && nnonimprovingshifts < MAXSHIFTINGS )
779  {
780  SCIP_VAR* shiftvar;
781  SCIP_Real oldsolval;
782  SCIP_Real newsolval;
783  SCIP_Bool oldsolvalisfrac;
784  int probindex;
785 
786  SCIPdebugMsg(scip, "shifting heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g), cutoff=%g\n",
787  nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj),
789 
790  nprevviolrows = nviolrows;
791 
792  /* choose next variable to process:
793  * - if a violated row exists, shift a variable decreasing the violation, that has least impact on other rows
794  * - otherwise, shift a variable, that has strongest devastating impact on rows in opposite direction
795  */
796  shiftvar = NULL;
797  oldsolval = 0.0;
798  newsolval = 0.0;
799  if( nviolrows > 0 && (nfrac == 0 || nnonimprovingshifts < MAXSHIFTINGS-1) )
800  {
801  SCIP_ROW* row;
802  int rowidx;
803  int rowpos;
804  int direction;
805 
806  assert(nviolfracrows == 0 || nfrac > 0);
807  /* violated rows containing fractional variables are preferred; if such a row exists, choose the last one from the list
808  * (at position nviolfracrows - 1) because removing this row will cause one swapping operation less than other rows
809  */
810  if( nviolfracrows > 0 )
811  rowidx = nviolfracrows - 1;
812  else
813  /* there is no violated row containing a fractional variable, select a violated row uniformly at random */
814  rowidx = SCIPrandomGetInt(heurdata->randnumgen, 0, nviolrows-1);
815 
816  assert(0 <= rowidx && rowidx < nviolrows);
817  row = violrows[rowidx];
818  rowpos = SCIProwGetLPPos(row);
819  assert(0 <= rowpos && rowpos < nlprows);
820  assert(violrowpos[rowpos] == rowidx);
821  assert(nfracsinrow[rowpos] == 0 || rowidx == nviolfracrows - 1);
822 
823  SCIPdebugMsg(scip, "shifting heuristic: try to fix violated row <%s>: %g <= %g <= %g\n",
824  SCIProwGetName(row), SCIProwGetLhs(row), activities[rowpos], SCIProwGetRhs(row));
826 
827  /* get direction in which activity must be shifted */
828  assert(SCIPisFeasLT(scip, activities[rowpos], SCIProwGetLhs(row))
829  || SCIPisFeasGT(scip, activities[rowpos], SCIProwGetRhs(row)));
830  direction = SCIPisFeasLT(scip, activities[rowpos], SCIProwGetLhs(row)) ? +1 : -1;
831 
832  /* search a variable that can shift the activity in the necessary direction */
833  SCIP_CALL( selectShifting(scip, sol, row, activities[rowpos], direction,
834  nincreases, ndecreases, increaseweight, &shiftvar, &oldsolval, &newsolval) );
835  }
836 
837  if( shiftvar == NULL && nfrac > 0 )
838  {
839  SCIPdebugMsg(scip, "shifting heuristic: search rounding variable and try to stay feasible\n");
840  SCIP_CALL( selectEssentialRounding(scip, sol, minobj, lpcands, nlpcands, &shiftvar, &oldsolval, &newsolval) );
841  }
842 
843  /* check, whether shifting was possible */
844  if( shiftvar == NULL || SCIPisEQ(scip, oldsolval, newsolval) )
845  {
846  SCIPdebugMsg(scip, "shifting heuristic: -> didn't find a shifting variable\n");
847  break;
848  }
849 
850  SCIPdebugMsg(scip, "shifting heuristic: -> shift var <%s>[%g,%g], type=%d, oldval=%g, newval=%g, obj=%g\n",
851  SCIPvarGetName(shiftvar), SCIPvarGetLbGlobal(shiftvar), SCIPvarGetUbGlobal(shiftvar), SCIPvarGetType(shiftvar),
852  oldsolval, newsolval, SCIPvarGetObj(shiftvar));
853 
854  /* update row activities of globally valid rows */
855  SCIP_CALL( updateActivities(scip, activities, violrows, violrowpos, &nviolrows, &nviolfracrows, nfracsinrow, nlprows,
856  shiftvar, oldsolval, newsolval) );
857  if( nviolrows >= nprevviolrows )
858  nnonimprovingshifts++;
859  else if( nviolrows < minnviolrows )
860  {
861  minnviolrows = nviolrows;
862  nnonimprovingshifts = 0;
863  }
864 
865  /* store new solution value and decrease fractionality counter */
866  SCIP_CALL( SCIPsetSolVal(scip, sol, shiftvar, newsolval) );
867 
868  /* update fractionality counter and minimal objective value possible after shifting remaining variables */
869  oldsolvalisfrac = !SCIPisFeasIntegral(scip, oldsolval)
870  && (SCIPvarGetType(shiftvar) == SCIP_VARTYPE_BINARY || SCIPvarGetType(shiftvar) == SCIP_VARTYPE_INTEGER);
871  obj = SCIPvarGetObj(shiftvar);
872  if( (SCIPvarGetType(shiftvar) == SCIP_VARTYPE_BINARY || SCIPvarGetType(shiftvar) == SCIP_VARTYPE_INTEGER)
873  && oldsolvalisfrac )
874  {
875  assert(SCIPisFeasIntegral(scip, newsolval));
876  nfrac--;
877  nnonimprovingshifts = 0;
878  minnviolrows = INT_MAX;
879  addFracCounter(nfracsinrow, violrows, violrowpos, &nviolfracrows, nviolrows, nlprows, shiftvar, -1);
880 
881  /* the rounding was already calculated into the minobj -> update only if rounding in "wrong" direction */
882  if( obj > 0.0 && newsolval > oldsolval )
883  minobj += obj;
884  else if( obj < 0.0 && newsolval < oldsolval )
885  minobj -= obj;
886  }
887  else
888  {
889  /* update minimal possible objective value */
890  minobj += obj * (newsolval - oldsolval);
891  }
892 
893  /* update increase/decrease arrays */
894  if( !oldsolvalisfrac )
895  {
896  probindex = SCIPvarGetProbindex(shiftvar);
897  assert(0 <= probindex && probindex < nvars);
898  increaseweight *= WEIGHTFACTOR;
899  if( newsolval < oldsolval )
900  ndecreases[probindex] += increaseweight;
901  else
902  nincreases[probindex] += increaseweight;
903  if( increaseweight >= 1e+09 )
904  {
905  int i;
906 
907  for( i = 0; i < nvars; ++i )
908  {
909  nincreases[i] /= increaseweight;
910  ndecreases[i] /= increaseweight;
911  }
912  increaseweight = 1.0;
913  }
914  }
915 
916  SCIPdebugMsg(scip, "shifting heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
917  nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj));
918  }
919 
920  /* check, if the new solution is feasible */
921  if( nfrac == 0 && nviolrows == 0 )
922  {
923  SCIP_Bool stored;
924 
925  /* check solution for feasibility, and add it to solution store if possible
926  * neither integrality nor feasibility of LP rows has to be checked, because this is already
927  * done in the shifting heuristic itself; however, we better check feasibility of LP rows,
928  * because of numerical problems with activity updating
929  */
930  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, TRUE, &stored) );
931 
932  if( stored )
933  {
934  SCIPdebugMsg(scip, "found feasible shifted solution:\n");
936  *result = SCIP_FOUNDSOL;
937  }
938  }
939 
940  /* free memory buffers */
941  SCIPfreeBufferArray(scip, &ndecreases);
942  SCIPfreeBufferArray(scip, &nincreases);
943  SCIPfreeBufferArray(scip, &nfracsinrow);
944  SCIPfreeBufferArray(scip, &violrowpos);
945  SCIPfreeBufferArray(scip, &violrows);
946  SCIPfreeBufferArray(scip, &activities);
947 
948  return SCIP_OKAY;
949 }
950 
951 
952 /*
953  * heuristic specific interface methods
954  */
955 
956 /** creates the shifting heuristic with infeasibility recovering and includes it in SCIP */
958  SCIP* scip /**< SCIP data structure */
959  )
960 {
961  SCIP_HEUR* heur;
962 
963  /* include primal heuristic */
964  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
966  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecShifting, NULL) );
967 
968  assert(heur != NULL);
969 
970  /* set non-NULL pointers to callback methods */
971  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyShifting) );
972  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitShifting) );
973  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitShifting) );
974  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolShifting) );
975 
976  return SCIP_OKAY;
977 }
978 
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36301
static SCIP_DECL_HEUREXEC(heurExecShifting)
static void addFracCounter(int *nfracsinrow, SCIP_ROW **violrows, int *violrowpos, int *nviolfracrows, int nviolrows, int nlprows, SCIP_VAR *var, int incval)
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:37847
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)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46333
LP rounding heuristic that tries to recover from intermediate infeasibilities and shifts continuous v...
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42726
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1327
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:16270
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip.c:8127
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:46110
#define HEUR_FREQ
Definition: heur_shifting.c:34
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46037
#define HEUR_FREQOFS
Definition: heur_shifting.c:35
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16450
SCIP_RETCODE SCIPincludeHeurShifting(SCIP *scip)
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:16326
static SCIP_DECL_HEURINITSOL(heurInitsolShifting)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16391
#define FALSE
Definition: def.h:64
static void updateViolations(SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, SCIP_Real oldactivity, SCIP_Real newactivity)
Definition: heur_shifting.c:60
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:46050
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:46122
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16862
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
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:8034
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:45985
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define HEUR_DISPCHAR
Definition: heur_shifting.c:32
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46457
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46445
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:16602
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
#define HEUR_USESSUBSCIP
Definition: heur_shifting.c:38
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip.c:8143
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
#define HEUR_PRIORITY
Definition: heur_shifting.c:33
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:16260
static SCIP_RETCODE updateActivities(SCIP *scip, SCIP_Real *activities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval)
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:16500
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45753
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38317
#define WEIGHTFACTOR
Definition: heur_shifting.c:41
#define SCIP_CALL(x)
Definition: def.h:316
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46359
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16401
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1307
#define HEUR_MAXDEPTH
Definition: heur_shifting.c:36
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16337
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28863
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:38042
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16347
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28948
static SCIP_DECL_HEURINIT(heurInitShifting)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
#define MAX(x, y)
Definition: tclique_def.h:75
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25561
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37806
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16883
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38268
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
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:39976
#define HEUR_NAME
Definition: heur_shifting.c:30
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11680
#define SCIP_REAL_MAX
Definition: def.h:146
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29027
#define DEFAULT_RANDSEED
Definition: heur_shifting.c:42
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16161
static SCIP_DECL_HEURCOPY(heurCopyShifting)
#define MAXSHIFTINGS
Definition: heur_shifting.c:40
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 SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip.c:8111
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip.c:38402
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:16580
#define SCIP_Real
Definition: def.h:145
#define MIN(x, y)
Definition: memory.c:75
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:30892
#define SCIP_Longint
Definition: def.h:130
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1317
#define HEUR_DESC
Definition: heur_shifting.c:31
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16720
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46098
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8079
#define nnodes
Definition: gastrans.c:65
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46421
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:89
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29295
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41409
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:41590
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:16249
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16746
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38182
static SCIP_DECL_HEUREXIT(heurExitShifting)
#define HEUR_TIMING
Definition: heur_shifting.c:37
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30803
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37178
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:38601