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