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