Scippy

SCIP

Solving Constraint Integer Programs

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