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