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