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