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