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