Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_gcgfracdiving.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file heur_gcgfracdiving.c
29  * @brief LP diving heuristic that chooses fixings w.r.t. the fractionalities
30  * @author Tobias Achterberg
31  * @author Christian Puchert
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 #include <string.h>
38 
39 #include "heur_gcgfracdiving.h"
40 #include "heur_origdiving.h"
41 #include "gcg.h"
42 
43 
44 #define HEUR_NAME "gcgfracdiving"
45 #define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the fractionalities"
46 #define HEUR_DISPCHAR 'f'
47 #define HEUR_PRIORITY -1003000
48 #define HEUR_FREQ 10
49 #define HEUR_FREQOFS 3
50 #define HEUR_MAXDEPTH -1
51 
52 
53 /*
54  * Default diving rule specific parameter settings
55  */
56 
57 #define DEFAULT_USEMASTERFRACS FALSE /**< calculate the fractionalities w.r.t. the master LP? */
58 
59 
60 /* locally defined diving heuristic data */
61 struct GCG_DivingData
62 {
63  SCIP_Bool usemasterfracs; /**< calculate the fractionalities w.r.t. the master LP? */
64 };
65 
66 
67 /*
68  * local methods
69  */
70 
71 /** check whether an original variable and a master variable belong to the same block */
72 static
74  SCIP_VAR* origvar, /**< original variable */
75  SCIP_VAR* mastervar /**< master variable */
76  )
77 {
78  int origblock;
79  int masterblock;
80 
81  /* get the blocks the variables belong to */
82  origblock = GCGvarGetBlock(origvar);
83  masterblock = GCGvarGetBlock(mastervar);
84 
85  /* the original variable is a linking variable:
86  * check whether the master variable is either its direct copy
87  * or in one of its blocks
88  */
89  if( GCGoriginalVarIsLinking(origvar) )
90  {
91  assert(origblock == -2);
92  if( masterblock == -1 )
93  {
94  SCIP_VAR** mastervars;
95 
96  mastervars = GCGoriginalVarGetMastervars(origvar);
97 
98  return mastervars[0] == mastervar;
99  }
100  else
101  {
102  assert(masterblock >= 0);
103  return GCGisLinkingVarInBlock(origvar, masterblock);
104  }
105  }
106  /* the original variable was directly copied to the master problem:
107  * check whether the master variable is its copy
108  */
109  else if( origblock == -1 )
110  {
111  SCIP_VAR** mastervars;
112 
113  mastervars = GCGoriginalVarGetMastervars(origvar);
114  assert(GCGoriginalVarGetNMastervars(origvar) == 1);
115 
116  return mastervars[0] == mastervar;
117  }
118  /* the original variable belongs to exactly one block */
119  else
120  {
121  assert(origblock >= 0);
122  return origblock == masterblock;
123  }
124 }
125 
126 /** get the 'down' fractionality of an original variable w.r.t. the master problem;
127  * this is the sum of the fractionalities of the master variables
128  * which would have to be fixed to zero if the original variable were rounded down
129  */
130 static
131 SCIP_RETCODE getMasterDownFrac(
132  SCIP* scip, /**< SCIP data structure */
133  SCIP_VAR* var, /**< original variable to get fractionality for */
134  SCIP_Real* frac /**< pointer to store fractionality */
135  )
136 {
137  SCIP* masterprob;
138  SCIP_VAR** mastervars;
139  SCIP_VAR** origmastervars;
140  SCIP_Real* origmastervals;
141  int nmastervars;
142  int norigmastervars;
143  SCIP_Real roundval;
144  SCIP_Real masterlpval;
145 
146  int i;
147 
148  /* get master problem */
149  masterprob = GCGgetMasterprob(scip);
150  assert(masterprob != NULL);
151 
152  /* get master variable information */
153  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
154 
155  /* get master variables in which the original variable appears */
156  origmastervars = GCGoriginalVarGetMastervars(var);
157  origmastervals = GCGoriginalVarGetMastervals(var);
158  norigmastervars = GCGoriginalVarGetNMastervars(var);
159 
160  roundval = SCIPfeasFloor(scip, SCIPgetRelaxSolVal(scip, var));
161  *frac = 0.0;
162 
163  /* calculate sum of fractionalities over all master variables
164  * which would violate the new original variable bound
165  */
166  if( SCIPisFeasNegative(masterprob, roundval) )
167  {
168  for( i = 0; i < nmastervars; ++i )
169  {
170  if( areVarsInSameBlock(var, mastervars[i]) )
171  {
172  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
173  *frac += SCIPfeasFrac(masterprob, masterlpval);
174  }
175  }
176  for( i = 0; i < norigmastervars; ++i )
177  {
178  masterlpval = SCIPgetSolVal(masterprob, NULL, origmastervars[i]);
179  if( SCIPisFeasLE(masterprob, origmastervals[i], roundval) )
180  *frac -= SCIPfeasFrac(masterprob, masterlpval);
181  }
182  }
183  else
184  {
185  for( i = 0; i < norigmastervars; ++i )
186  {
187  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
188  if( SCIPisFeasGT(masterprob, origmastervals[i], roundval) )
189  *frac += SCIPfeasFrac(masterprob, masterlpval);
190  }
191  }
192 
193  return SCIP_OKAY;
194 }
195 
196 /** get the 'up' fractionality of an original variable w.r.t. the master problem;
197  * this is the sum of the fractionalities of the master variables
198  * which would have to be fixed to zero if the original variable were rounded up
199  */
200 static
201 SCIP_RETCODE getMasterUpFrac(
202  SCIP* scip, /**< SCIP data structure */
203  SCIP_VAR* var, /**< original variable to get fractionality for */
204  SCIP_Real* frac /**< pointer to store fractionality */
205  )
206 {
207  SCIP* masterprob;
208  SCIP_VAR** mastervars;
209  SCIP_VAR** origmastervars;
210  SCIP_Real* origmastervals;
211  int nmastervars;
212  int norigmastervars;
213  SCIP_Real roundval;
214  SCIP_Real masterlpval;
215 
216  int i;
217 
218  /* get master problem */
219  masterprob = GCGgetMasterprob(scip);
220  assert(masterprob != NULL);
221 
222  /* get master variable information */
223  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
224 
225  /* get master variables in which the original variable appears */
226  origmastervars = GCGoriginalVarGetMastervars(var);
227  origmastervals = GCGoriginalVarGetMastervals(var);
228  norigmastervars = GCGoriginalVarGetNMastervars(var);
229 
230  roundval = SCIPfeasCeil(scip, SCIPgetRelaxSolVal(scip, var));
231  *frac = 0.0;
232 
233  /* calculate sum of fractionalities over all master variables
234  * which would violate the new original variable bound
235  */
236  if( SCIPisFeasPositive(masterprob, roundval) )
237  {
238  for( i = 0; i < nmastervars; ++i )
239  {
240  if( areVarsInSameBlock(var, mastervars[i]) )
241  {
242  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
243  *frac += SCIPfeasFrac(masterprob, masterlpval);
244  }
245  }
246  for( i = 0; i < norigmastervars; ++i )
247  {
248  masterlpval = SCIPgetSolVal(masterprob, NULL, origmastervars[i]);
249  if( SCIPisFeasGE(masterprob, origmastervals[i], roundval) )
250  *frac -= SCIPfeasFrac(masterprob, masterlpval);
251  }
252  }
253  else
254  {
255  for( i = 0; i < norigmastervars; ++i )
256  {
257  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
258  if( SCIPisFeasLT(masterprob, origmastervals[i], roundval) )
259  *frac += SCIPfeasFrac(masterprob, masterlpval);
260  }
261  }
262 
263  return SCIP_OKAY;
264 }
265 
266 
267 /*
268  * Callback methods
269  */
270 
271 /** destructor of diving heuristic to free user data (called when GCG is exiting) */
272 static
273 GCG_DECL_DIVINGFREE(heurFreeGcgfracdiving) /*lint --e{715}*/
274 { /*lint --e{715}*/
275  GCG_DIVINGDATA* divingdata;
276 
277  assert(heur != NULL);
278  assert(scip != NULL);
279 
280  /* free diving rule specific data */
281  divingdata = GCGheurGetDivingDataOrig(heur);
282  assert(divingdata != NULL);
283  SCIPfreeMemory(scip, &divingdata);
284  GCGheurSetDivingDataOrig(heur, NULL);
285 
286  return SCIP_OKAY;
287 }
288 
289 
290 /** variable selection method of diving heuristic;
291  * finds best candidate variable w.r.t. fractionality:
292  * - prefer variables that may not be rounded without destroying LP feasibility:
293  * - of these variables, round least fractional variable in corresponding direction
294  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
295  * - round variable with least increasing objective value
296  * - binary variables are preferred
297  */
298 static
299 GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgfracdiving) /*lint --e{715}*/
300 { /*lint --e{715}*/
301  GCG_DIVINGDATA* divingdata;
302  SCIP_VAR** lpcands;
303  SCIP_Real* lpcandssol;
304  int nlpcands;
305  SCIP_Real bestobjgain;
306  SCIP_Real bestfrac; /* fractionality of best candidate */
307  SCIP_Bool bestcandmayrounddown;
308  SCIP_Bool bestcandmayroundup;
309  int c;
310 
311  /* check preconditions */
312  assert(scip != NULL);
313  assert(heur != NULL);
314  assert(bestcand != NULL);
315  assert(bestcandmayround != NULL);
316  assert(bestcandroundup != NULL);
317 
318  /* get diving data */
319  divingdata = GCGheurGetDivingDataOrig(heur);
320  assert(divingdata != NULL);
321 
322  /* get fractional variables that should be integral */
323  SCIP_CALL( SCIPgetExternBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL, NULL, NULL) );
324  assert(lpcands != NULL);
325  assert(lpcandssol != NULL);
326 
327  bestcandmayrounddown = TRUE;
328  bestcandmayroundup = TRUE;
329  bestobjgain = SCIPinfinity(scip);
330  bestfrac = SCIP_INVALID;
331 
332  /* get best candidate */
333  for( c = 0; c < nlpcands; ++c )
334  {
335  SCIP_VAR* var;
336  SCIP_Bool mayrounddown;
337  SCIP_Bool mayroundup;
338  SCIP_Bool roundup;
339  SCIP_Real frac;
340  SCIP_Real origfrac;
341  SCIP_Real downfrac;
342  SCIP_Real upfrac;
343  SCIP_Real obj;
344 
345  int i;
346 
347  var = lpcands[c];
348 
349  /* if the variable is on the tabu list, do not choose it */
350  for( i = 0; i < tabulistsize; ++i )
351  if( tabulist[i] == var )
352  break;
353  if( i < tabulistsize )
354  continue;
355 
356  mayrounddown = SCIPvarMayRoundDown(var);
357  mayroundup = SCIPvarMayRoundUp(var);
358  SCIP_CALL( getMasterDownFrac(scip, var, &downfrac) );
359  SCIP_CALL( getMasterUpFrac(scip, var, &upfrac) );
360  origfrac = lpcandssol[c] - SCIPfloor(scip, lpcandssol[c]);
361  obj = SCIPvarGetObj(var);
362 
363  if( mayrounddown || mayroundup )
364  {
365  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
366  if( bestcandmayrounddown || bestcandmayroundup )
367  {
368  SCIP_Real objgain;
369 
370  /* choose rounding direction:
371  * - if variable may be rounded in both directions, round corresponding to the fractionality
372  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
373  * the current fractional solution
374  */
375  if( mayrounddown && mayroundup )
376  roundup = divingdata->usemasterfracs ? (upfrac < downfrac) : (origfrac > 0.5);
377  else
378  roundup = mayrounddown;
379 
380  if( roundup )
381  {
382  origfrac = 1.0 - origfrac;
383  objgain = origfrac*obj;
384  }
385  else
386  objgain = -origfrac*obj;
387 
388  if( divingdata->usemasterfracs )
389  frac = MIN(downfrac, upfrac);
390  else
391  frac = origfrac;
392 
393  /* penalize too small fractions */
394  if( frac < 0.01 )
395  objgain *= 1000.0;
396 
397  /* prefer decisions on binary variables */
398  if( !SCIPvarIsBinary(var) )
399  objgain *= 1000.0;
400 
401  /* check, if candidate is new best candidate */
402  if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
403  {
404  *bestcand = var;
405  bestobjgain = objgain;
406  bestfrac = frac;
407  bestcandmayrounddown = mayrounddown;
408  bestcandmayroundup = mayroundup;
409  *bestcandroundup = roundup;
410  }
411  }
412  }
413  else
414  {
415  /* the candidate may not be rounded */
416  if( divingdata->usemasterfracs )
417  {
418  if( downfrac < upfrac )
419  {
420  roundup = FALSE;
421  frac = downfrac;
422  }
423  else
424  {
425  roundup = TRUE;
426  frac = upfrac;
427  }
428  }
429  else
430  {
431  if( origfrac < 0.5 )
432  {
433  roundup = FALSE;
434  frac = origfrac;
435  }
436  else
437  {
438  roundup = TRUE;
439  frac = 1.0 - origfrac;
440  }
441  }
442 
443  /* penalize too small fractions */
444  if( frac < 0.01 )
445  frac += 10.0;
446 
447  /* prefer decisions on binary variables */
448  if( !SCIPvarIsBinary(var) )
449  frac *= 1000.0;
450 
451  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
452  if( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
453  {
454  *bestcand = var;
455  bestfrac = frac;
456  bestcandmayrounddown = FALSE;
457  bestcandmayroundup = FALSE;
458  *bestcandroundup = roundup;
459  }
460  assert(bestfrac < SCIP_INVALID);
461  }
462  }
463 
464  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
465 
466  return SCIP_OKAY;
467 }
468 
469 
470 /*
471  * heuristic specific interface methods
472  */
473 
474 /** creates the gcgfracdiving heuristic and includes it in GCG */
476  SCIP* scip /**< SCIP data structure */
477  )
478 {
479  SCIP_HEUR* heur;
480  GCG_DIVINGDATA* divingdata;
481 
482  /* create gcgcoefdiving primal heuristic data */
483  SCIP_CALL( SCIPallocMemory(scip, &divingdata) );
484 
485  /* include diving heuristic */
486  SCIP_CALL( GCGincludeDivingHeurOrig(scip, &heur,
488  HEUR_MAXDEPTH, heurFreeGcgfracdiving, NULL, NULL, NULL, NULL, NULL, NULL,
489  heurSelectVarGcgfracdiving, divingdata) );
490 
491  assert(heur != NULL);
492 
493  /* add gcgfracdiving specific parameters */
494  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/usemasterfracs",
495  "calculate the fractionalities w.r.t. the master LP?",
496  &divingdata->usemasterfracs, TRUE, DEFAULT_USEMASTERFRACS, NULL, NULL) );
497 
498  return SCIP_OKAY;
499 }
500 
GCG_DIVINGDATA * GCGheurGetDivingDataOrig(SCIP_HEUR *heur)
#define HEUR_NAME
GCG interface methods.
int GCGoriginalVarGetNMastervars(SCIP_VAR *var)
Definition: gcgvar.c:569
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:587
SCIP_Bool GCGisLinkingVarInBlock(SCIP_VAR *var, int block)
Definition: gcgvar.c:1064
#define DEFAULT_USEMASTERFRACS
SCIP_RETCODE GCGincludeHeurGcgfracdiving(SCIP *scip)
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:1033
primal heuristic interface for LP diving heuristics on the original variables
#define HEUR_DESC
static GCG_DECL_DIVINGFREE(heurFreeGcgfracdiving)
SCIP_Real * GCGoriginalVarGetMastervals(SCIP_VAR *var)
Definition: gcgvar.c:605
#define HEUR_FREQ
#define HEUR_MAXDEPTH
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
SCIP_RETCODE GCGincludeDivingHeurOrig(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, GCG_DECL_DIVINGFREE((*divingfree)), GCG_DECL_DIVINGINIT((*divinginit)), GCG_DECL_DIVINGEXIT((*divingexit)), GCG_DECL_DIVINGINITSOL((*divinginitsol)), GCG_DECL_DIVINGEXITSOL((*divingexitsol)), GCG_DECL_DIVINGINITEXEC((*divinginitexec)), GCG_DECL_DIVINGEXITEXEC((*divingexitexec)), GCG_DECL_DIVINGSELECTVAR((*divingselectvar)), GCG_DIVINGDATA *divingdata)
#define HEUR_DISPCHAR
void GCGheurSetDivingDataOrig(SCIP_HEUR *heur, GCG_DIVINGDATA *divingdata)
#define HEUR_PRIORITY
#define HEUR_FREQOFS
static SCIP_Bool areVarsInSameBlock(SCIP_VAR *origvar, SCIP_VAR *mastervar)
static GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgfracdiving)
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:182
static SCIP_RETCODE getMasterUpFrac(SCIP *scip, SCIP_VAR *var, SCIP_Real *frac)
static SCIP_RETCODE getMasterDownFrac(SCIP *scip, SCIP_VAR *var, SCIP_Real *frac)
LP diving heuristic that chooses fixings w.r.t. the fractionalities.
SCIP_Bool usemasterfracs