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