Scippy

SCIP

Solving Constraint Integer Programs

heur_rounding.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_rounding.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief LP rounding heuristic that tries to recover from intermediate infeasibilities
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_rounding.h"
26 #include "scip/pub_heur.h"
27 #include "scip/pub_lp.h"
28 #include "scip/pub_message.h"
29 #include "scip/pub_var.h"
30 #include "scip/scip_branch.h"
31 #include "scip/scip_heur.h"
32 #include "scip/scip_lp.h"
33 #include "scip/scip_mem.h"
34 #include "scip/scip_message.h"
35 #include "scip/scip_numerics.h"
36 #include "scip/scip_param.h"
37 #include "scip/scip_sol.h"
38 #include "scip/scip_solvingstats.h"
39 #include <string.h>
40 
41 #define HEUR_NAME "rounding"
42 #define HEUR_DESC "LP rounding heuristic with infeasibility recovering"
43 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING
44 #define HEUR_PRIORITY -1000
45 #define HEUR_FREQ 1
46 #define HEUR_FREQOFS 0
47 #define HEUR_MAXDEPTH -1
48 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP
49 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
50 
51 #define DEFAULT_SUCCESSFACTOR 100 /**< number of calls per found solution that are considered as standard success,
52  * a higher factor causes the heuristic to be called more often
53  */
54 #define DEFAULT_ONCEPERNODE FALSE /**< should the heuristic only be called once per node? */
55 
56 /* locally defined heuristic data */
57 struct SCIP_HeurData
58 {
59  SCIP_SOL* sol; /**< working solution */
60  SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */
61  int successfactor; /**< number of calls per found solution that are considered as standard success,
62  * a higher factor causes the heuristic to be called more often
63  */
64  SCIP_Bool oncepernode; /**< should the heuristic only be called once per node? */
65 };
66 
67 
68 /*
69  * local methods
70  */
71 
72 /** update row violation arrays after a row's activity value changed */
73 static
74 void updateViolations(
75  SCIP* scip, /**< SCIP data structure */
76  SCIP_ROW* row, /**< LP row */
77  SCIP_ROW** violrows, /**< array with currently violated rows */
78  int* violrowpos, /**< position of LP rows in violrows array */
79  int* nviolrows, /**< pointer to the number of currently violated rows */
80  SCIP_Real oldactivity, /**< old activity value of LP row */
81  SCIP_Real newactivity /**< new activity value of LP row */
82  )
83 {
84  SCIP_Real lhs;
85  SCIP_Real rhs;
86  SCIP_Bool oldviol;
87  SCIP_Bool newviol;
88 
89  assert(violrows != NULL);
90  assert(violrowpos != NULL);
91  assert(nviolrows != NULL);
92 
93  lhs = SCIProwGetLhs(row);
94  rhs = SCIProwGetRhs(row);
95  oldviol = (SCIPisFeasLT(scip, oldactivity, lhs) || SCIPisFeasGT(scip, oldactivity, rhs));
96  newviol = (SCIPisFeasLT(scip, newactivity, lhs) || SCIPisFeasGT(scip, newactivity, rhs));
97  if( oldviol != newviol )
98  {
99  int rowpos;
100  int violpos;
101 
102  rowpos = SCIProwGetLPPos(row);
103  assert(rowpos >= 0);
104 
105  if( oldviol )
106  {
107  /* the row violation was repaired: remove row from violrows array, decrease violation count */
108  violpos = violrowpos[rowpos];
109  assert(0 <= violpos && violpos < *nviolrows);
110  assert(violrows[violpos] == row);
111  violrowpos[rowpos] = -1;
112  if( violpos != *nviolrows-1 )
113  {
114  violrows[violpos] = violrows[*nviolrows-1];
115  violrowpos[SCIProwGetLPPos(violrows[violpos])] = violpos;
116  }
117  (*nviolrows)--;
118  }
119  else
120  {
121  /* the row is now violated: add row to violrows array, increase violation count */
122  assert(violrowpos[rowpos] == -1);
123  violrows[*nviolrows] = row;
124  violrowpos[rowpos] = *nviolrows;
125  (*nviolrows)++;
126  }
127  }
128 }
129 
130 /** update row activities after a variable's solution value changed */
131 static
133  SCIP* scip, /**< SCIP data structure */
134  SCIP_Real* activities, /**< LP row activities */
135  SCIP_ROW** violrows, /**< array with currently violated rows */
136  int* violrowpos, /**< position of LP rows in violrows array */
137  int* nviolrows, /**< pointer to the number of currently violated rows */
138  int nlprows, /**< number of rows in current LP */
139  SCIP_VAR* var, /**< variable that has been changed */
140  SCIP_Real oldsolval, /**< old solution value of variable */
141  SCIP_Real newsolval /**< new solution value of variable */
142  )
143 {
144  SCIP_COL* col;
145  SCIP_ROW** colrows;
146  SCIP_Real* colvals;
147  SCIP_Real delta;
148  int ncolrows;
149  int r;
150 
151  assert(activities != NULL);
152  assert(nviolrows != NULL);
153  assert(0 <= *nviolrows && *nviolrows <= nlprows);
154 
155  delta = newsolval - oldsolval;
156  col = SCIPvarGetCol(var);
157  colrows = SCIPcolGetRows(col);
158  colvals = SCIPcolGetVals(col);
159  ncolrows = SCIPcolGetNLPNonz(col);
160  assert(ncolrows == 0 || (colrows != NULL && colvals != NULL));
161 
162  for( r = 0; r < ncolrows; ++r )
163  {
164  SCIP_ROW* row;
165  int rowpos;
166 
167  row = colrows[r];
168  rowpos = SCIProwGetLPPos(row);
169  assert(-1 <= rowpos && rowpos < nlprows);
170 
171  if( rowpos >= 0 && !SCIProwIsLocal(row) )
172  {
173  SCIP_Real oldactivity;
174  SCIP_Real newactivity;
175 
176  assert(SCIProwIsInLP(row));
177 
178  /* update row activity */
179  oldactivity = activities[rowpos];
180  if( !SCIPisInfinity(scip, -oldactivity) && !SCIPisInfinity(scip, oldactivity) )
181  {
182  newactivity = oldactivity + delta * colvals[r];
183  if( SCIPisInfinity(scip, newactivity) )
184  newactivity = SCIPinfinity(scip);
185  else if( SCIPisInfinity(scip, -newactivity) )
186  newactivity = -SCIPinfinity(scip);
187  activities[rowpos] = newactivity;
188 
189  /* update row violation arrays */
190  updateViolations(scip, row, violrows, violrowpos, nviolrows, oldactivity, newactivity);
191  }
192  }
193  }
194 
195  return SCIP_OKAY;
196 }
197 
198 /** returns a variable, that pushes activity of the row in the given direction with minimal negative impact on other rows;
199  * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
200  * rounding in a direction is forbidden, if this forces the objective value over the upper bound
201  */
202 static
204  SCIP* scip, /**< SCIP data structure */
205  SCIP_SOL* sol, /**< primal solution */
206  SCIP_Real minobj, /**< minimal objective value possible after rounding remaining fractional vars */
207  SCIP_ROW* row, /**< LP row */
208  int direction, /**< should the activity be increased (+1) or decreased (-1)? */
209  SCIP_VAR** roundvar, /**< pointer to store the rounding variable, returns NULL if impossible */
210  SCIP_Real* oldsolval, /**< pointer to store old (fractional) solution value of rounding variable */
211  SCIP_Real* newsolval /**< pointer to store new (rounded) solution value of rounding variable */
212  )
213 {
214  SCIP_COL* col;
215  SCIP_VAR* var;
216  SCIP_Real val;
217  SCIP_COL** rowcols;
218  SCIP_Real* rowvals;
219  SCIP_Real solval;
220  SCIP_Real roundval;
221  SCIP_Real obj;
222  SCIP_Real deltaobj;
223  SCIP_Real bestdeltaobj;
224  SCIP_VARTYPE vartype;
225  int nrowcols;
226  int nlocks;
227  int minnlocks;
228  int c;
229 
230  assert(direction == +1 || direction == -1);
231  assert(roundvar != NULL);
232  assert(oldsolval != NULL);
233  assert(newsolval != NULL);
234 
235  /* get row entries */
236  rowcols = SCIProwGetCols(row);
237  rowvals = SCIProwGetVals(row);
238  nrowcols = SCIProwGetNLPNonz(row);
239 
240  /* select rounding variable */
241  minnlocks = INT_MAX;
242  bestdeltaobj = SCIPinfinity(scip);
243  *roundvar = NULL;
244  for( c = 0; c < nrowcols; ++c )
245  {
246  col = rowcols[c];
247  var = SCIPcolGetVar(col);
248 
249  vartype = SCIPvarGetType(var);
250  if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER )
251  {
252  solval = SCIPgetSolVal(scip, sol, var);
253 
254  if( !SCIPisFeasIntegral(scip, solval) )
255  {
256  val = rowvals[c];
257  obj = SCIPvarGetObj(var);
258 
259  if( direction * val < 0.0 )
260  {
261  /* rounding down */
263  if( nlocks <= minnlocks )
264  {
265  roundval = SCIPfeasFloor(scip, solval);
266  deltaobj = obj * (roundval - solval);
267  if( (nlocks < minnlocks || deltaobj < bestdeltaobj) && minobj - obj < SCIPgetCutoffbound(scip) )
268  {
269  minnlocks = nlocks;
270  bestdeltaobj = deltaobj;
271  *roundvar = var;
272  *oldsolval = solval;
273  *newsolval = roundval;
274  }
275  }
276  }
277  else
278  {
279  /* rounding up */
280  assert(direction * val > 0.0);
282  if( nlocks <= minnlocks )
283  {
284  roundval = SCIPfeasCeil(scip, solval);
285  deltaobj = obj * (roundval - solval);
286  if( (nlocks < minnlocks || deltaobj < bestdeltaobj) && minobj + obj < SCIPgetCutoffbound(scip) )
287  {
288  minnlocks = nlocks;
289  bestdeltaobj = deltaobj;
290  *roundvar = var;
291  *oldsolval = solval;
292  *newsolval = roundval;
293  }
294  }
295  }
296  }
297  }
298  }
299 
300  return SCIP_OKAY;
301 }
302 
303 /** returns a variable, that increases the activity of the row */
304 static
306  SCIP* scip, /**< SCIP data structure */
307  SCIP_SOL* sol, /**< primal solution */
308  SCIP_Real minobj, /**< minimal objective value possible after rounding remaining fractional vars */
309  SCIP_ROW* row, /**< LP row */
310  SCIP_VAR** roundvar, /**< pointer to store the rounding variable, returns NULL if impossible */
311  SCIP_Real* oldsolval, /**< old (fractional) solution value of rounding variable */
312  SCIP_Real* newsolval /**< new (rounded) solution value of rounding variable */
313  )
314 {
315  return selectRounding(scip, sol, minobj, row, +1, roundvar, oldsolval, newsolval);
316 }
317 
318 /** returns a variable, that decreases the activity of the row */
319 static
321  SCIP* scip, /**< SCIP data structure */
322  SCIP_SOL* sol, /**< primal solution */
323  SCIP_Real minobj, /**< minimal objective value possible after rounding remaining fractional vars */
324  SCIP_ROW* row, /**< LP row */
325  SCIP_VAR** roundvar, /**< pointer to store the rounding variable, returns NULL if impossible */
326  SCIP_Real* oldsolval, /**< old (fractional) solution value of rounding variable */
327  SCIP_Real* newsolval /**< new (rounded) solution value of rounding variable */
328  )
329 {
330  return selectRounding(scip, sol, minobj, row, -1, roundvar, oldsolval, newsolval);
331 }
332 
333 /** returns a fractional variable, that has most impact on rows in opposite direction, i.e. that is most crucial to
334  * fix in the other direction;
335  * if variables have equal impact, chooses the one with best objective value improvement in corresponding direction;
336  * rounding in a direction is forbidden, if this forces the objective value over the upper bound
337  */
338 static
340  SCIP* scip, /**< SCIP data structure */
341  SCIP_SOL* sol, /**< primal solution */
342  SCIP_Real minobj, /**< minimal objective value possible after rounding remaining fractional vars */
343  SCIP_VAR** lpcands, /**< fractional variables in LP */
344  int nlpcands, /**< number of fractional variables in LP */
345  SCIP_VAR** roundvar, /**< pointer to store the rounding variable, returns NULL if impossible */
346  SCIP_Real* oldsolval, /**< old (fractional) solution value of rounding variable */
347  SCIP_Real* newsolval /**< new (rounded) solution value of rounding variable */
348  )
349 {
350  SCIP_VAR* var;
351  SCIP_Real solval;
352  SCIP_Real roundval;
353  SCIP_Real obj;
354  SCIP_Real deltaobj;
355  SCIP_Real bestdeltaobj;
356  int maxnlocks;
357  int nlocks;
358  int v;
359 
360  assert(roundvar != NULL);
361  assert(oldsolval != NULL);
362  assert(newsolval != NULL);
363 
364  /* select rounding variable */
365  maxnlocks = -1;
366  bestdeltaobj = SCIPinfinity(scip);
367  *roundvar = NULL;
368  for( v = 0; v < nlpcands; ++v )
369  {
370  var = lpcands[v];
372 
373  solval = SCIPgetSolVal(scip, sol, var);
374  if( !SCIPisFeasIntegral(scip, solval) )
375  {
376  obj = SCIPvarGetObj(var);
377 
378  /* rounding down */
380  if( nlocks >= maxnlocks )
381  {
382  roundval = SCIPfeasFloor(scip, solval);
383  deltaobj = obj * (roundval - solval);
384  if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj - obj < SCIPgetCutoffbound(scip) )
385  {
386  maxnlocks = nlocks;
387  bestdeltaobj = deltaobj;
388  *roundvar = var;
389  *oldsolval = solval;
390  *newsolval = roundval;
391  }
392  }
393 
394  /* rounding up */
396  if( nlocks >= maxnlocks )
397  {
398  roundval = SCIPfeasCeil(scip, solval);
399  deltaobj = obj * (roundval - solval);
400  if( (nlocks > maxnlocks || deltaobj < bestdeltaobj) && minobj + obj < SCIPgetCutoffbound(scip) )
401  {
402  maxnlocks = nlocks;
403  bestdeltaobj = deltaobj;
404  *roundvar = var;
405  *oldsolval = solval;
406  *newsolval = roundval;
407  }
408  }
409  }
410  }
411 
412  return SCIP_OKAY;
413 }
414 
415 
416 /*
417  * Callback methods
418  */
419 
420 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
421 static
422 SCIP_DECL_HEURCOPY(heurCopyRounding)
423 { /*lint --e{715}*/
424  assert(scip != NULL);
425  assert(heur != NULL);
426  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
427 
428  /* call inclusion method of primal heuristic */
430 
431  return SCIP_OKAY;
432 }
433 
434 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
435 static
436 SCIP_DECL_HEURFREE(heurFreeRounding) /*lint --e{715}*/
437 { /*lint --e{715}*/
438  SCIP_HEURDATA* heurdata;
439 
440  assert(heur != NULL);
441  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
442  assert(scip != NULL);
443 
444  /* free heuristic data */
445  heurdata = SCIPheurGetData(heur);
446  assert(heurdata != NULL);
447  SCIPfreeBlockMemory(scip, &heurdata);
448  SCIPheurSetData(heur, NULL);
449 
450  return SCIP_OKAY;
451 }
452 
453 /** initialization method of primal heuristic (called after problem was transformed) */
454 static
455 SCIP_DECL_HEURINIT(heurInitRounding) /*lint --e{715}*/
456 { /*lint --e{715}*/
457  SCIP_HEURDATA* heurdata;
458 
459  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
460 
461  heurdata = SCIPheurGetData(heur);
462  assert(heurdata != NULL);
463 
464  /* create heuristic data */
465  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
466  heurdata->lastlp = -1;
467 
468  return SCIP_OKAY;
469 }
470 
471 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
472 static
473 SCIP_DECL_HEUREXIT(heurExitRounding) /*lint --e{715}*/
474 { /*lint --e{715}*/
475  SCIP_HEURDATA* heurdata;
476 
477  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
478 
479  /* free heuristic data */
480  heurdata = SCIPheurGetData(heur);
481  assert(heurdata != NULL);
482  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
483 
484  return SCIP_OKAY;
485 }
486 
487 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
488 static
489 SCIP_DECL_HEURINITSOL(heurInitsolRounding)
490 {
491  SCIP_HEURDATA* heurdata;
492 
493  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
494 
495  heurdata = SCIPheurGetData(heur);
496  assert(heurdata != NULL);
497  heurdata->lastlp = -1;
498 
499  /* change the heuristic's timingmask, if nit should be called only once per node */
500  if( heurdata->oncepernode )
502 
503  return SCIP_OKAY;
504 }
505 
506 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
507 static
508 SCIP_DECL_HEUREXITSOL(heurExitsolRounding)
509 {
510  /* reset the timing mask to its default value */
512 
513  return SCIP_OKAY;
514 }
515 
516 
517 /** execution method of primal heuristic */
518 static
519 SCIP_DECL_HEUREXEC(heurExecRounding) /*lint --e{715}*/
520 { /*lint --e{715}*/
521  SCIP_HEURDATA* heurdata;
522  SCIP_SOL* sol;
523  SCIP_VAR** lpcands;
524  SCIP_Real* lpcandssol;
525  SCIP_ROW** lprows;
526  SCIP_Real* activities;
527  SCIP_ROW** violrows;
528  int* violrowpos;
529  SCIP_Real obj;
530  SCIP_Real bestroundval;
531  SCIP_Real minobj;
532  int nlpcands;
533  int nlprows;
534  int nfrac;
535  int nviolrows;
536  int c;
537  int r;
538  SCIP_Longint nlps;
539  SCIP_Longint ncalls;
540  SCIP_Longint nsolsfound;
542 
543  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
544  assert(scip != NULL);
545  assert(result != NULL);
546  assert(SCIPhasCurrentNodeLP(scip));
547 
548  *result = SCIP_DIDNOTRUN;
549 
550  /* only call heuristic, if an optimal LP solution is at hand */
552  return SCIP_OKAY;
553 
554  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
555  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
556  return SCIP_OKAY;
557 
558  /* get heuristic data */
559  heurdata = SCIPheurGetData(heur);
560  assert(heurdata != NULL);
561 
562  /* don't call heuristic, if we have already processed the current LP solution */
563  nlps = SCIPgetNLPs(scip);
564  if( nlps == heurdata->lastlp )
565  return SCIP_OKAY;
566  heurdata->lastlp = nlps;
567 
568  /* don't call heuristic, if it was not successful enough in the past */
569  ncalls = SCIPheurGetNCalls(heur);
570  nsolsfound = 10*SCIPheurGetNBestSolsFound(heur) + SCIPheurGetNSolsFound(heur);
571  nnodes = SCIPgetNNodes(scip);
572  if( nnodes % ((ncalls/heurdata->successfactor)/(nsolsfound+1)+1) != 0 )
573  return SCIP_OKAY;
574 
575  /* get fractional variables, that should be integral */
576  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL) );
577  nfrac = nlpcands;
578 
579  /* only call heuristic, if LP solution is fractional */
580  if( nfrac == 0 )
581  return SCIP_OKAY;
582 
583  *result = SCIP_DIDNOTFIND;
584 
585  /* get LP rows */
586  SCIP_CALL( SCIPgetLPRowsData(scip, &lprows, &nlprows) );
587 
588  SCIPdebugMsg(scip, "executing rounding heuristic: %d LP rows, %d fractionals\n", nlprows, nfrac);
589 
590  /* get memory for activities, violated rows, and row violation positions */
591  SCIP_CALL( SCIPallocBufferArray(scip, &activities, nlprows) );
592  SCIP_CALL( SCIPallocBufferArray(scip, &violrows, nlprows) );
593  SCIP_CALL( SCIPallocBufferArray(scip, &violrowpos, nlprows) );
594 
595  /* get the activities for all globally valid rows;
596  * the rows should be feasible, but due to numerical inaccuracies in the LP solver, they can be violated
597  */
598  nviolrows = 0;
599  for( r = 0; r < nlprows; ++r )
600  {
601  SCIP_ROW* row;
602 
603  row = lprows[r];
604  assert(SCIProwGetLPPos(row) == r);
605 
606  if( !SCIProwIsLocal(row) )
607  {
608  activities[r] = SCIPgetRowActivity(scip, row);
609  if( SCIPisFeasLT(scip, activities[r], SCIProwGetLhs(row))
610  || SCIPisFeasGT(scip, activities[r], SCIProwGetRhs(row)) )
611  {
612  violrows[nviolrows] = row;
613  violrowpos[r] = nviolrows;
614  nviolrows++;
615  }
616  else
617  violrowpos[r] = -1;
618  }
619  }
620 
621  /* get the working solution from heuristic's local data */
622  sol = heurdata->sol;
623  assert(sol != NULL);
624 
625  /* copy the current LP solution to the working solution */
626  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
627 
628  /* calculate the minimal objective value possible after rounding fractional variables */
629  minobj = SCIPgetSolTransObj(scip, sol);
630  assert(minobj < SCIPgetCutoffbound(scip));
631  for( c = 0; c < nlpcands; ++c )
632  {
633  obj = SCIPvarGetObj(lpcands[c]);
634  bestroundval = obj > 0.0 ? SCIPfeasFloor(scip, lpcandssol[c]) : SCIPfeasCeil(scip, lpcandssol[c]);
635  minobj += obj * (bestroundval - lpcandssol[c]);
636  }
637 
638  /* try to round remaining variables in order to become/stay feasible */
639  while( nfrac > 0 )
640  {
641  SCIP_VAR* roundvar;
642  SCIP_Real oldsolval;
643  SCIP_Real newsolval;
644 
645  SCIPdebugMsg(scip, "rounding heuristic: nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
646  nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj));
647 
648  /* minobj < SCIPgetCutoffbound(scip) should be true, otherwise the rounding variable selection
649  * should have returned NULL. Due to possible cancellation we use SCIPisLE. */
650  assert( SCIPisLE(scip, minobj, SCIPgetCutoffbound(scip)) );
651 
652  /* choose next variable to process:
653  * - if a violated row exists, round a variable decreasing the violation, that has least impact on other rows
654  * - otherwise, round a variable, that has strongest devastating impact on rows in opposite direction
655  */
656  if( nviolrows > 0 )
657  {
658  SCIP_ROW* row;
659  int rowpos;
660 
661  row = violrows[nviolrows-1];
662  rowpos = SCIProwGetLPPos(row);
663  assert(0 <= rowpos && rowpos < nlprows);
664  assert(violrowpos[rowpos] == nviolrows-1);
665 
666  SCIPdebugMsg(scip, "rounding heuristic: try to fix violated row <%s>: %g <= %g <= %g\n",
667  SCIProwGetName(row), SCIProwGetLhs(row), activities[rowpos], SCIProwGetRhs(row));
668  if( SCIPisFeasLT(scip, activities[rowpos], SCIProwGetLhs(row)) )
669  {
670  /* lhs is violated: select a variable rounding, that increases the activity */
671  SCIP_CALL( selectIncreaseRounding(scip, sol, minobj, row, &roundvar, &oldsolval, &newsolval) );
672  }
673  else
674  {
675  assert(SCIPisFeasGT(scip, activities[rowpos], SCIProwGetRhs(row)));
676  /* rhs is violated: select a variable rounding, that decreases the activity */
677  SCIP_CALL( selectDecreaseRounding(scip, sol, minobj, row, &roundvar, &oldsolval, &newsolval) );
678  }
679  }
680  else
681  {
682  SCIPdebugMsg(scip, "rounding heuristic: search rounding variable and try to stay feasible\n");
683  SCIP_CALL( selectEssentialRounding(scip, sol, minobj, lpcands, nlpcands, &roundvar, &oldsolval, &newsolval) );
684  }
685 
686  /* check, whether rounding was possible */
687  if( roundvar == NULL )
688  {
689  SCIPdebugMsg(scip, "rounding heuristic: -> didn't find a rounding variable\n");
690  break;
691  }
692 
693  SCIPdebugMsg(scip, "rounding heuristic: -> round var <%s>, oldval=%g, newval=%g, obj=%g\n",
694  SCIPvarGetName(roundvar), oldsolval, newsolval, SCIPvarGetObj(roundvar));
695 
696  /* update row activities of globally valid rows */
697  SCIP_CALL( updateActivities(scip, activities, violrows, violrowpos, &nviolrows, nlprows,
698  roundvar, oldsolval, newsolval) );
699 
700  /* store new solution value and decrease fractionality counter */
701  SCIP_CALL( SCIPsetSolVal(scip, sol, roundvar, newsolval) );
702  nfrac--;
703 
704  /* update minimal objective value possible after rounding remaining variables */
705  obj = SCIPvarGetObj(roundvar);
706  if( obj > 0.0 && newsolval > oldsolval )
707  minobj += obj;
708  else if( obj < 0.0 && newsolval < oldsolval )
709  minobj -= obj;
710 
711  SCIPdebugMsg(scip, "rounding heuristic: -> nfrac=%d, nviolrows=%d, obj=%g (best possible obj: %g)\n",
712  nfrac, nviolrows, SCIPgetSolOrigObj(scip, sol), SCIPretransformObj(scip, minobj));
713  }
714 
715  /* check, if the new solution is feasible */
716  if( nfrac == 0 && nviolrows == 0 )
717  {
718  SCIP_Bool stored;
719 
720  /* check solution for feasibility, and add it to solution store if possible
721  * neither integrality nor feasibility of LP rows has to be checked, because this is already
722  * done in the rounding heuristic itself; however, be better check feasibility of LP rows,
723  * because of numerical problems with activity updating
724  */
725  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, TRUE, &stored) );
726 
727  if( stored )
728  {
729 #ifdef SCIP_DEBUG
730  SCIPdebugMsg(scip, "found feasible rounded solution:\n");
731  SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
732 #endif
733  *result = SCIP_FOUNDSOL;
734  }
735  }
736 
737  /* free memory buffers */
738  SCIPfreeBufferArray(scip, &violrowpos);
739  SCIPfreeBufferArray(scip, &violrows);
740  SCIPfreeBufferArray(scip, &activities);
741 
742  return SCIP_OKAY;
743 }
744 
745 
746 /*
747  * heuristic specific interface methods
748  */
749 
750 /** creates the rounding heuristic with infeasibility recovering and includes it in SCIP */
752  SCIP* scip /**< SCIP data structure */
753  )
754 {
755  SCIP_HEURDATA* heurdata;
756  SCIP_HEUR* heur;
757 
758  /* create Rounding primal heuristic data */
759  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
760 
761  /* include primal heuristic */
762  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
764  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRounding, heurdata) );
765 
766  assert(heur != NULL);
767 
768  /* set non-NULL pointers to callback methods */
769  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRounding) );
770  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRounding) );
771  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRounding) );
772  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRounding) );
773  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolRounding) );
774  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolRounding) );
775 
776  /* add rounding primal heuristic parameters */
777  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/successfactor",
778  "number of calls per found solution that are considered as standard success, a higher factor causes the heuristic to be called more often",
779  &heurdata->successfactor, TRUE, DEFAULT_SUCCESSFACTOR, -1, INT_MAX, NULL, NULL) );
780 
781  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/oncepernode",
782  "should the heuristic only be called once per node?",
783  &heurdata->oncepernode, TRUE, DEFAULT_ONCEPERNODE, NULL, NULL) );
784 
785  return SCIP_OKAY;
786 }
static SCIP_DECL_HEUREXEC(heurExecRounding)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1555
static SCIP_RETCODE selectDecreaseRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17250
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1565
#define DEFAULT_SUCCESSFACTOR
Definition: heur_rounding.c:51
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
public methods for SCIP parameter handling
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:17076
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define HEUR_FREQ
Definition: heur_rounding.c:45
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
SCIP_EXPORT int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3250
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
#define HEUR_NAME
Definition: heur_rounding.c:41
LP rounding heuristic that tries to recover from intermediate infeasibilities.
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition: lp.c:17010
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
static SCIP_RETCODE selectRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, int direction, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
#define HEUR_DESC
Definition: heur_rounding.c:42
#define FALSE
Definition: def.h:73
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition: lp.c:17000
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17510
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17177
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1018
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
public methods for problem variables
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
#define HEUR_MAXDEPTH
Definition: heur_rounding.c:47
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17350
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3125
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1575
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
static SCIP_DECL_HEURINITSOL(heurInitsolRounding)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
SCIP_Longint SCIPgetNLPs(SCIP *scip)
public methods for querying solving statistics
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17372
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define DEFAULT_ONCEPERNODE
Definition: heur_rounding.c:56
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
#define HEUR_FREQOFS
Definition: heur_rounding.c:46
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17087
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:540
#define SCIP_HEURTIMING_AFTERLPNODE
Definition: type_timing.h:73
#define HEUR_TIMING
Definition: heur_rounding.c:48
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17097
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition: lp.c:16989
static SCIP_DECL_HEUREXITSOL(heurExitsolRounding)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1469
#define SCIP_CALL(x)
Definition: def.h:364
static SCIP_RETCODE updateActivities(SCIP *scip, SCIP_Real *activities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
public methods for primal heuristic plugins and divesets
SCIP_EXPORT SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17376
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
static SCIP_DECL_HEUREXIT(heurExitRounding)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17141
public methods for LP management
#define HEUR_DISPCHAR
Definition: heur_rounding.c:43
#define HEUR_PRIORITY
Definition: heur_rounding.c:44
static SCIP_RETCODE selectEssentialRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_VAR **lpcands, int nlpcands, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
#define HEUR_USESSUBSCIP
Definition: heur_rounding.c:49
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16901
public methods for the LP relaxation, rows and columns
SCIP_EXPORT int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3193
SCIP_Real * r
Definition: circlepacking.c:50
public methods for branching rule plugins and branching
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for solutions
static SCIP_DECL_HEURFREE(heurFreeRounding)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message output
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1483
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1767
#define SCIP_Real
Definition: def.h:163
static SCIP_DECL_HEURCOPY(heurCopyRounding)
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1568
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17200
public methods for message handling
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
#define SCIP_Longint
Definition: def.h:148
static void updateViolations(SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, SCIP_Real oldactivity, SCIP_Real newactivity)
Definition: heur_rounding.c:76
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:60
#define nnodes
Definition: gastrans.c:65
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17151
public methods for primal heuristics
SCIP_RETCODE SCIPincludeHeurRounding(SCIP *scip)
static SCIP_RETCODE selectIncreaseRounding(SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_ROW *row, SCIP_VAR **roundvar, SCIP_Real *oldsolval, SCIP_Real *newsolval)
static SCIP_DECL_HEURINIT(heurInitRounding)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1436
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2044
memory allocation routines