Scippy

SCIP

Solving Constraint Integer Programs

heur_randrounding.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-2014 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_randrounding.c
17  * @brief randomized LP rounding heuristic which also generates conflicts via an auxiliary probing tree
18  * @author Gregor Hendel
19  *
20  * Randomized LP rounding uses a random variable from a uniform distribution
21  * over [0,1] to determine whether the fractional LP value x should be rounded
22  * up with probability x - floor(x) or down with probability ceil(x) - x.
23  *
24  * This implementation uses domain propagation techniques to tighten the variable domains after every
25  * rounding step.
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 #include <assert.h>
31 #include <string.h>
32 
33 #include "scip/heur_randrounding.h"
34 
35 
36 #define HEUR_NAME "randrounding"
37 #define HEUR_DESC "fast LP rounding heuristic"
38 #define HEUR_DISPCHAR 'G'
39 #define HEUR_PRIORITY -200
40 #define HEUR_FREQ 20
41 #define HEUR_FREQOFS 0
42 #define HEUR_MAXDEPTH -1
43 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP
44 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
45 
46 #define DEFAULT_ONCEPERNODE FALSE /**< should the heuristic only be called once per node? */
47 #define DEFAULT_RANDSEED 14081986 /**< default random seed */
48 #define DEFAULT_USESIMPLEROUNDING FALSE /**< should the heuristic apply the variable lock strategy of simple rounding,
49  * if possible? */
50 #define DEFAULT_MAXPROPROUNDS 1 /**< limit of rounds for each propagation call */
51 #define DEFAULT_PROPAGATEONLYROOT TRUE /**< should the probing part of the heuristic be applied exclusively at the root node */
52 
53 /* locally defined heuristic data */
54 struct SCIP_HeurData
55 {
56  SCIP_SOL* sol; /**< working solution */
57  SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */
58  unsigned int randseed; /**< seed for random number generation */
59  int maxproprounds; /**< limit of rounds for each propagation call */
60  SCIP_Bool oncepernode; /**< should the heuristic only be called once per node? */
61  SCIP_Bool usesimplerounding; /**< should the heuristic apply the variable lock strategy of simple rounding,
62  * if possible? */
63  SCIP_Bool propagateonlyroot; /**< should the probing part of the heuristic be applied exclusively at the root node? */
64 };
65 
66 /*
67  * Local methods
68  */
69 
70 /** perform randomized rounding of the given solution. Domain propagation is optionally applied after every rounding
71  * step
72  */
73 static
74 SCIP_RETCODE performRandRounding(
75  SCIP* scip, /**< SCIP main data structure */
76  SCIP_HEURDATA* heurdata, /**< heuristic data */
77  SCIP_SOL* sol, /**< solution to round */
78  SCIP_VAR** cands, /**< candidate variables */
79  int ncands, /**< number of candidates */
80  SCIP_Bool propagate, /**< should the rounding be propagated? */
81  SCIP_RESULT* result /**< pointer to store the result of the heuristic call */
82  )
83 {
84  int c;
85  SCIP_Bool stored;
86  SCIP_VAR** permutedcands;
87  SCIP_Bool cutoff;
88 
89  assert(heurdata != NULL);
90 
91  /* start probing tree before rounding begins */
92  if( propagate )
93  {
94  SCIP_CALL( SCIPstartProbing(scip) );
95  SCIPenableVarHistory(scip);
96  }
97 
98  /* copy and permute the candidate array */
99  SCIP_CALL( SCIPduplicateBufferArray(scip, &permutedcands, cands, ncands) );
100 
101  assert(permutedcands != NULL);
102 
103  SCIPpermuteArray((void **)permutedcands, 0, ncands, &heurdata->randseed);
104  cutoff = FALSE;
105 
106  /* loop over candidates and perform randomized rounding and optionally probing. */
107  for (c = 0; c < ncands && !cutoff; ++c)
108  {
109  SCIP_VAR* var;
110  SCIP_Real oldsolval;
111  SCIP_Real newsolval;
112  SCIP_Bool mayrounddown;
113  SCIP_Bool mayroundup;
114  SCIP_Longint ndomreds;
115  SCIP_Real lb;
116  SCIP_Real ub;
117  SCIP_Real ceilval;
118  SCIP_Real floorval;
119 
120  /* get next variable from permuted candidate array */
121  var = permutedcands[c];
122  oldsolval = SCIPgetSolVal(scip, sol, var);
123  lb = SCIPvarGetLbLocal(var);
124  ub = SCIPvarGetUbLocal(var);
125 
126  assert( ! SCIPisFeasIntegral(scip, oldsolval) );
127  assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
128 
129  mayrounddown = SCIPvarMayRoundDown(var);
130  mayroundup = SCIPvarMayRoundUp(var);
131  ceilval = SCIPfeasCeil(scip, oldsolval);
132  floorval = SCIPfeasFloor(scip, oldsolval);
133 
134  SCIPdebugMessage("rand rounding heuristic: var <%s>, val=%g, rounddown=%u, roundup=%u\n",
135  SCIPvarGetName(var), oldsolval, mayrounddown, mayroundup);
136 
137  /* abort if rounded ceil and floor value lie outside the variable domain. Otherwise, check if
138  * bounds allow only one rounding direction, anyway */
139  if( lb > ceilval + 0.5 || ub < floorval - 0.5 )
140  {
141  cutoff = TRUE;
142  break;
143  }
144  else if( SCIPisFeasEQ(scip, lb, ceilval) )
145  {
146  /* only rounding up possible */
147  assert(SCIPisFeasGE(scip, ub, ceilval));
148  newsolval = ceilval;
149  }
150  else if( SCIPisFeasEQ(scip, ub, floorval) )
151  {
152  /* only rounding down possible */
153  assert(SCIPisFeasLE(scip,lb, floorval));
154  newsolval = floorval;
155  }
156  else if( !heurdata->usesimplerounding || !(mayroundup || mayrounddown) )
157  {
158  /* the standard randomized rounding */
159  SCIP_Real randnumber;
160 
161  randnumber = SCIPgetRandomReal(0.0, 1.0, &heurdata->randseed);
162  if( randnumber <= oldsolval - floorval )
163  newsolval = ceilval;
164  else
165  newsolval = floorval;
166  }
167  /* choose rounding direction, if possible, or use the only direction guaranteed to be feasible */
168  else if( mayrounddown && mayroundup )
169  {
170  /* we can round in both directions: round in objective function direction */
171  if ( SCIPvarGetObj(var) >= 0.0 )
172  newsolval = floorval;
173  else
174  newsolval = ceilval;
175  }
176  else if( mayrounddown )
177  newsolval = floorval;
178  else
179  {
180  assert(mayroundup);
181  newsolval = ceilval;
182  }
183 
184  assert(SCIPisFeasLE(scip, lb, newsolval));
185  assert(SCIPisFeasGE(scip, ub, newsolval));
186 
187  /* if propagation is enabled, fix the candidate variable to its rounded value and propagate the solution */
188  if( propagate )
189  {
190  SCIP_Bool lbadjust;
191  SCIP_Bool ubadjust;
192 
193  lbadjust = SCIPisGT(scip, newsolval, lb);
194  ubadjust = SCIPisLT(scip, newsolval, ub);
195 
196  assert( lbadjust || ubadjust || SCIPisFeasEQ(scip, lb, ub));
197 
198  /* enter a new probing node if the variable was not already fixed before */
199  if( lbadjust || ubadjust )
200  {
201  SCIP_RETCODE retcode;
202 
203  if( SCIPisStopped(scip) )
204  break;
205 
206  retcode = SCIPnewProbingNode(scip);
207  if( retcode == SCIP_MAXDEPTHLEVEL )
208  break;
209 
210  SCIP_CALL( retcode );
211 
212  /* tighten the bounds to fix the variable for the probing node */
213  if( lbadjust )
214  {
215  SCIP_CALL( SCIPchgVarLbProbing(scip, var, newsolval) );
216  }
217  if( ubadjust )
218  {
219  SCIP_CALL( SCIPchgVarUbProbing(scip, var, newsolval) );
220  }
221 
222  /* call propagation routines for the reduced problem */
223  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, &cutoff, &ndomreds) );
224  }
225  }
226  /* store new solution value */
227  SCIP_CALL( SCIPsetSolVal(scip, sol, var, newsolval) );
228  }
229 
230  /* if no cutoff was detected, the solution is a candidate to be checked for feasibility */
231  if( !cutoff && ! SCIPisStopped(scip) )
232  {
233  if( SCIPallColsInLP(scip) )
234  {
235  /* check solution for feasibility, and add it to solution store if possible
236  * neither integrality nor feasibility of LP rows has to be checked, because all fractional
237  * variables were already moved in feasible direction to the next integer
238  */
239  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, TRUE, &stored) );
240  }
241  else
242  {
243  /* if there are variables which are not present in the LP, e.g., for
244  * column generation, we need to check their bounds
245  */
246  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, TRUE, FALSE, TRUE, &stored) );
247  }
248 
249  if( stored )
250  {
251 #ifdef SCIP_DEBUG
252  SCIPdebugMessage("found feasible rounded solution:\n");
253  SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) );
254 #endif
255  *result = SCIP_FOUNDSOL;
256  }
257  }
258 
259  assert( !propagate || SCIPinProbing(scip) );
260 
261  /* exit probing mode and free locally allocated memory */
262  if( propagate )
263  {
264  SCIP_CALL( SCIPendProbing(scip) );
265  }
266 
267  SCIPfreeBufferArray(scip, &permutedcands);
268 
269  return SCIP_OKAY;
270 }
271 
272 /** perform randomized LP-rounding */
273 static
274 SCIP_RETCODE performLPRandRounding(
275  SCIP* scip, /**< SCIP main data structure */
276  SCIP_HEURDATA* heurdata, /**< heuristic data */
277  SCIP_HEURTIMING heurtiming, /**< heuristic timing mask */
278  SCIP_Bool propagate, /**< should the heuristic apply SCIP's propagation? */
279  SCIP_RESULT* result /**< pointer to store the result of the heuristic call */
280  )
281 {
282  SCIP_SOL* sol;
283  SCIP_VAR** lpcands;
284  SCIP_Longint nlps;
285  int nlpcands;
286 
287  /* only call heuristic, if an optimal LP solution is at hand */
288  if ( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
289  return SCIP_OKAY;
290 
291  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
292  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
293  return SCIP_OKAY;
294 
295  /* get fractional variables, that should be integral */
296  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, NULL, &nlpcands, NULL, NULL) );
297 
298  /* only call heuristic, if LP solution is fractional; except we are called during pricing, in this case we
299  * want to detect a (mixed) integer (LP) solution which is primal feasible */
300  if ( nlpcands == 0 && heurtiming != SCIP_HEURTIMING_DURINGPRICINGLOOP )
301  return SCIP_OKAY;
302 
303  /* get the working solution from heuristic's local data */
304  sol = heurdata->sol;
305  assert( sol != NULL );
306 
307  /* copy the current LP solution to the working solution */
308  SCIP_CALL( SCIPlinkLPSol(scip, sol) );
309 
310  /* don't call heuristic, if we have already processed the current LP solution */
311  nlps = SCIPgetNLPs(scip);
312  if( nlps == heurdata->lastlp )
313  return SCIP_OKAY;
314  heurdata->lastlp = nlps;
315 
316  *result = SCIP_DIDNOTFIND;
317 
318  /* perform random rounding */
319  SCIPdebugMessage("executing rand LP-rounding heuristic: %d fractionals\n", nlpcands);
320  SCIP_CALL( performRandRounding(scip, heurdata, sol, lpcands, nlpcands, propagate, result) );
321 
322  return SCIP_OKAY;
323 }
324 
325 /*
326  * Callback methods
327  */
328 
329 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
330 static
331 SCIP_DECL_HEURCOPY(heurCopyRandrounding)
332 { /*lint --e{715}*/
333  assert(scip != NULL);
334  assert(heur != NULL);
335  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
336 
337  /* call inclusion method of primal heuristic */
338  SCIP_CALL( SCIPincludeHeurRandrounding(scip) );
339 
340  return SCIP_OKAY;
341 }
342 
343 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
344 static
345 SCIP_DECL_HEURFREE(heurFreeRandrounding) /*lint --e{715}*/
346 { /*lint --e{715}*/
347  SCIP_HEURDATA* heurdata;
348 
349  assert(heur != NULL);
350  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
351  assert(scip != NULL);
352 
353  /* free heuristic data */
354  heurdata = SCIPheurGetData(heur);
355  assert(heurdata != NULL);
356  SCIPfreeMemory(scip, &heurdata);
357  SCIPheurSetData(heur, NULL);
358 
359  return SCIP_OKAY;
360 }
361 
362 /** initialization method of primal heuristic (called after problem was transformed) */
363 static
364 SCIP_DECL_HEURINIT(heurInitRandrounding) /*lint --e{715}*/
365 { /*lint --e{715}*/
366  SCIP_HEURDATA* heurdata;
367 
368  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
369  heurdata = SCIPheurGetData(heur);
370  assert(heurdata != NULL);
371 
372  /* create heuristic data */
373  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
374  heurdata->lastlp = -1;
375  heurdata->randseed = DEFAULT_RANDSEED;
376 
377  return SCIP_OKAY;
378 }
379 
380 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
381 static
382 SCIP_DECL_HEUREXIT(heurExitRandrounding) /*lint --e{715}*/
383 { /*lint --e{715}*/
384  SCIP_HEURDATA* heurdata;
385 
386  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
387 
388  /* free heuristic data */
389  heurdata = SCIPheurGetData(heur);
390  assert(heurdata != NULL);
391  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
392 
393  return SCIP_OKAY;
394 }
395 
396 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
397 static
398 SCIP_DECL_HEURINITSOL(heurInitsolRandrounding)
399 {
400  SCIP_HEURDATA* heurdata;
401 
402  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
403 
404  heurdata = SCIPheurGetData(heur);
405  assert(heurdata != NULL);
406  heurdata->lastlp = -1;
407 
408  /* change the heuristic's timingmask, if it should be called only once per node */
409  if( heurdata->oncepernode )
410  SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_AFTERLPNODE);
411 
412  return SCIP_OKAY;
413 }
414 
415 
416 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
417 static
418 SCIP_DECL_HEUREXITSOL(heurExitsolRandrounding)
419 {
420  /* reset the timing mask to its default value */
421  SCIPheurSetTimingmask(heur, HEUR_TIMING);
422 
423  return SCIP_OKAY;
424 }
425 
426 /** execution method of primal heuristic */
427 static
428 SCIP_DECL_HEUREXEC(heurExecRandrounding) /*lint --e{715}*/
429 { /*lint --e{715}*/
430  SCIP_HEURDATA* heurdata;
431  SCIP_Bool propagate;
432 
433  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
434  assert(result != NULL);
435  assert(SCIPhasCurrentNodeLP(scip));
436 
437  *result = SCIP_DIDNOTRUN;
438 
439  /* only call heuristic, if an optimal LP solution is at hand or if relaxation solution is available */
440  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL && ! SCIPisRelaxSolValid(scip) )
441  return SCIP_OKAY;
442 
443  /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
444  if( SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)) )
445  return SCIP_OKAY;
446 
447  /* get heuristic data */
448  heurdata = SCIPheurGetData(heur);
449  assert(heurdata != NULL);
450 
451  /* don't call heuristic, if we have already processed the current LP solution but no relaxation solution is available */
452  if ( SCIPgetNLPs(scip) == heurdata->lastlp && ! SCIPisRelaxSolValid(scip) )
453  return SCIP_OKAY;
454 
455  propagate = (!heurdata->propagateonlyroot || SCIPgetDepth(scip) == 0);
456 
457  /* try to round LP solution */
458  SCIP_CALL( performLPRandRounding(scip, heurdata, heurtiming, propagate, result) );
459 
460  return SCIP_OKAY;
461 }
462 
463 /*
464  * heuristic specific interface methods
465  */
466 
467 /** creates the rand rounding heuristic and includes it in SCIP */
468 SCIP_RETCODE SCIPincludeHeurRandrounding(
469  SCIP* scip /**< SCIP data structure */
470  )
471 {
472  SCIP_HEURDATA* heurdata;
473  SCIP_HEUR* heur;
474 
475  /* create heuristic data */
476  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
477 
478  /* include primal heuristic */
479  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
480  HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
481  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRandrounding, heurdata) );
482  assert(heur != NULL);
483 
484  /* set non-NULL pointers to callback methods */
485  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRandrounding) );
486  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRandrounding) );
487  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRandrounding) );
488  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolRandrounding) );
489  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolRandrounding) );
490  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRandrounding) );
491 
492  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/oncepernode",
493  "should the heuristic only be called once per node?",
494  &heurdata->oncepernode, TRUE, DEFAULT_ONCEPERNODE, NULL, NULL) );
495  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/usesimplerounding", "should the heuristic apply the variable lock strategy of simple rounding, if possible?",
496  &heurdata->usesimplerounding, TRUE, DEFAULT_USESIMPLEROUNDING, NULL, NULL) );
497  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/propagateonlyroot",
498  "should the probing part of the heuristic be applied exclusively at the root node?",
499  &heurdata->propagateonlyroot, TRUE, DEFAULT_PROPAGATEONLYROOT, NULL, NULL) );
500  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/maxproprounds",
501  "limit of rounds for each propagation call",
502  &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS,
503  -1, INT_MAX, NULL, NULL) );
504  return SCIP_OKAY;
505 }
506