heur_gcgguideddiving.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-2018 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 
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_gcgguideddiving.h"
40 #include "heur_origdiving.h"
41 #include "gcg.h"
42 
43 
44 #define HEUR_NAME "gcgguideddiving"
45 #define HEUR_DESC "LP diving heuristic that chooses fixings in direction of incumbent solutions"
46 #define HEUR_DISPCHAR 'g'
47 #define HEUR_PRIORITY -1007000
48 #define HEUR_FREQ 10
49 #define HEUR_FREQOFS 7
50 #define HEUR_MAXDEPTH -1
51 
52 
53 /*
54  * Default diving rule specific parameter settings
55  */
56 
57 #define DEFAULT_USEMASTERFRACS FALSE
60 /* locally defined diving heuristic data */
61 struct GCG_DivingData
62 {
63  SCIP_Bool usemasterfracs;
64  SCIP_SOL* bestsol;
65 };
66 
67 
68 /*
69  * local methods
70  */
71 
73 static
75  SCIP_VAR* origvar,
76  SCIP_VAR* mastervar
77  )
78 {
79  int origblock;
80  int masterblock;
81 
82  /* get the blocks the variables belong to */
83  origblock = GCGvarGetBlock(origvar);
84  masterblock = GCGvarGetBlock(mastervar);
85 
86  /* the original variable is a linking variable:
87  * check whether the master variable is either its direct copy
88  * or in one of its blocks
89  */
90  if( GCGoriginalVarIsLinking(origvar) )
91  {
92  assert(origblock == -2);
93  if( masterblock == -1 )
94  {
95  SCIP_VAR** mastervars;
96 
97  mastervars = GCGoriginalVarGetMastervars(origvar);
98 
99  return mastervars[0] == mastervar;
100  }
101  else
102  {
103  assert(masterblock >= 0);
104  return GCGisLinkingVarInBlock(origvar, masterblock);
105  }
106  }
107  /* the original variable was directly copied to the master problem:
108  * check whether the master variable is its copy
109  */
110  else if( origblock == -1 )
111  {
112  SCIP_VAR** mastervars;
113 
114  mastervars = GCGoriginalVarGetMastervars(origvar);
115  assert(GCGoriginalVarGetNMastervars(origvar) == 1);
116 
117  return mastervars[0] == mastervar;
118  }
119  /* the original variable belongs to exactly one block */
120  else
121  {
122  assert(origblock >= 0);
123  return origblock == masterblock;
124  }
125 }
126 
131 static
132 SCIP_RETCODE getMasterDownFrac(
133  SCIP* scip,
134  SCIP_VAR* var,
135  SCIP_Real* frac
136  )
137 {
138  SCIP* masterprob;
139  SCIP_VAR** mastervars;
140  SCIP_VAR** origmastervars;
141  SCIP_Real* origmastervals;
142  int nmastervars;
143  int norigmastervars;
144  SCIP_Real roundval;
145  SCIP_Real masterlpval;
146 
147  int i;
148 
149  /* get master problem */
150  masterprob = GCGgetMasterprob(scip);
151  assert(masterprob != NULL);
152 
153  /* get master variable information */
154  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
155 
156  /* get master variables in which the original variable appears */
157  origmastervars = GCGoriginalVarGetMastervars(var);
158  origmastervals = GCGoriginalVarGetMastervals(var);
159  norigmastervars = GCGoriginalVarGetNMastervars(var);
160 
161  roundval = SCIPfeasFloor(scip, SCIPgetRelaxSolVal(scip, var));
162  *frac = 0.0;
163 
164  /* calculate sum of fractionalities over all master variables
165  * which would violate the new original variable bound
166  */
167  if( SCIPisFeasNegative(masterprob, roundval) )
168  {
169  for( i = 0; i < nmastervars; ++i )
170  {
171  if( areVarsInSameBlock(var, mastervars[i]) )
172  {
173  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
174  *frac += SCIPfeasFrac(masterprob, masterlpval);
175  }
176  }
177  for( i = 0; i < norigmastervars; ++i )
178  {
179  masterlpval = SCIPgetSolVal(masterprob, NULL, origmastervars[i]);
180  if( SCIPisFeasLE(masterprob, origmastervals[i], roundval) )
181  *frac -= SCIPfeasFrac(masterprob, masterlpval);
182  }
183  }
184  else
185  {
186  for( i = 0; i < norigmastervars; ++i )
187  {
188  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
189  if( SCIPisFeasGT(masterprob, origmastervals[i], roundval) )
190  *frac += SCIPfeasFrac(masterprob, masterlpval);
191  }
192  }
193 
194  return SCIP_OKAY;
195 }
196 
201 static
202 SCIP_RETCODE getMasterUpFrac(
203  SCIP* scip,
204  SCIP_VAR* var,
205  SCIP_Real* frac
206  )
207 {
208  SCIP* masterprob;
209  SCIP_VAR** mastervars;
210  SCIP_VAR** origmastervars;
211  SCIP_Real* origmastervals;
212  int nmastervars;
213  int norigmastervars;
214  SCIP_Real roundval;
215  SCIP_Real masterlpval;
216 
217  int i;
218 
219  /* get master problem */
220  masterprob = GCGgetMasterprob(scip);
221  assert(masterprob != NULL);
222 
223  /* get master variable information */
224  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
225 
226  /* get master variables in which the original variable appears */
227  origmastervars = GCGoriginalVarGetMastervars(var);
228  origmastervals = GCGoriginalVarGetMastervals(var);
229  norigmastervars = GCGoriginalVarGetNMastervars(var);
230 
231  roundval = SCIPfeasCeil(scip, SCIPgetRelaxSolVal(scip, var));
232  *frac = 0.0;
233 
234  /* calculate sum of fractionalities over all master variables
235  * which would violate the new original variable bound
236  */
237  if( SCIPisFeasPositive(masterprob, roundval) )
238  {
239  for( i = 0; i < nmastervars; ++i )
240  {
241  if( areVarsInSameBlock(var, mastervars[i]) )
242  {
243  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
244  *frac += SCIPfeasFrac(masterprob, masterlpval);
245  }
246  }
247  for( i = 0; i < norigmastervars; ++i )
248  {
249  masterlpval = SCIPgetSolVal(masterprob, NULL, origmastervars[i]);
250  if( SCIPisFeasGE(masterprob, origmastervals[i], roundval) )
251  *frac -= SCIPfeasFrac(masterprob, masterlpval);
252  }
253  }
254  else
255  {
256  for( i = 0; i < norigmastervars; ++i )
257  {
258  masterlpval = SCIPgetSolVal(masterprob, NULL, mastervars[i]);
259  if( SCIPisFeasLT(masterprob, origmastervals[i], roundval) )
260  *frac += SCIPfeasFrac(masterprob, masterlpval);
261  }
262  }
263 
264  return SCIP_OKAY;
265 }
266 
267 
268 /*
269  * Callback methods
270  */
271 
272 
274 static
275 GCG_DECL_DIVINGFREE(heurFreeGcgguideddiving) /*lint --e{715}*/
276 { /*lint --e{715}*/
277  GCG_DIVINGDATA* divingdata;
278 
279  assert(heur != NULL);
280  assert(scip != NULL);
281 
282  /* free diving rule specific data */
283  divingdata = GCGheurGetDivingDataOrig(heur);
284  assert(divingdata != NULL);
285  SCIPfreeMemory(scip, &divingdata);
286  GCGheurSetDivingDataOrig(heur, NULL);
287 
288  return SCIP_OKAY;
289 }
290 
291 
293 static
294 GCG_DECL_DIVINGINITEXEC(heurInitexecGcgguideddiving) /*lint --e{715}*/
295 { /*lint --e{715}*/
296  GCG_DIVINGDATA* divingdata;
297 
298  assert(heur != NULL);
299 
300  /* get diving data */
301  divingdata = GCGheurGetDivingDataOrig(heur);
302  assert(divingdata != NULL);
303 
304  /* store a copy of the best solution */
305  SCIP_CALL( SCIPcreateSolCopy(scip, &divingdata->bestsol, SCIPgetBestSol(scip)) );
306 
307  return SCIP_OKAY;
308 }
309 
310 
312 static
313 GCG_DECL_DIVINGEXITEXEC(heurExitexecGcgguideddiving) /*lint --e{715}*/
314 { /*lint --e{715}*/
315  GCG_DIVINGDATA* divingdata;
316 
317  assert(heur != NULL);
318 
319  /* get diving data */
320  divingdata = GCGheurGetDivingDataOrig(heur);
321  assert(divingdata != NULL);
322 
323  /* free copied best solution */
324  SCIP_CALL( SCIPfreeSol(scip, &divingdata->bestsol) );
325 
326  return SCIP_OKAY;
327 }
328 
329 
342 static
343 GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgguideddiving) /*lint --e{715}*/
344 { /*lint --e{715}*/
345  GCG_DIVINGDATA* divingdata;
346  SCIP_VAR** lpcands;
347  SCIP_Real* lpcandssol;
348  SCIP_Real* lpcandsfrac;
349  int nlpcands;
350  SCIP_Real bestobjgain;
351  SCIP_Real bestscore; /* fractionality of best candidate */
352  SCIP_Bool bestcandmayrounddown;
353  SCIP_Bool bestcandmayroundup;
354  int c;
355 
356  /* check preconditions */
357  assert(scip != NULL);
358  assert(heur != NULL);
359  assert(bestcand != NULL);
360  assert(bestcandmayround != NULL);
361  assert(bestcandroundup != NULL);
362 
363  /* get diving data */
364  divingdata = GCGheurGetDivingDataOrig(heur);
365  assert(divingdata != NULL);
366  assert(divingdata->bestsol != NULL);
367 
368  /* get fractional variables that should be integral */
369  SCIP_CALL( SCIPgetExternBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL, NULL, NULL) );
370  assert(lpcands != NULL);
371  assert(lpcandsfrac != NULL);
372  assert(lpcandssol != NULL);
373 
374  bestcandmayrounddown = TRUE;
375  bestcandmayroundup = TRUE;
376  bestobjgain = SCIPinfinity(scip);
377  bestscore = SCIP_INVALID;
378 
379  /* get best candidate */
380  for( c = 0; c < nlpcands; ++c )
381  {
382  SCIP_VAR* var;
383  SCIP_Bool mayrounddown;
384  SCIP_Bool mayroundup;
385  SCIP_Bool roundup;
386  SCIP_Real frac;
387  SCIP_Real obj;
388  SCIP_Real score;
389  SCIP_Real solval;
390  SCIP_Real bestsolval;
391 
392  int i;
393 
394  var = lpcands[c];
395 
396  /* if the variable is on the tabu list, do not choose it */
397  for( i = 0; i < tabulistsize; ++i )
398  if( tabulist[i] == var )
399  break;
400  if( i < tabulistsize )
401  continue;
402 
403  mayrounddown = SCIPvarMayRoundDown(var);
404  mayroundup = SCIPvarMayRoundUp(var);
405  solval = lpcandssol[c];
406  frac = lpcandsfrac[c];
407  obj = SCIPvarGetObj(var);
408  bestsolval = SCIPgetSolVal(scip, divingdata->bestsol, var);
409 
410  /* select default rounding direction */
411  roundup = (solval < bestsolval);
412 
413  if( mayrounddown || mayroundup )
414  {
415  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
416  if( bestcandmayrounddown || bestcandmayroundup )
417  {
418  SCIP_Real objgain;
419 
420  /* choose rounding direction:
421  * - if variable may be rounded in both directions, round corresponding to its value in incumbent solution
422  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
423  * the current fractional solution with SCIProundSol()
424  */
425  if( !mayrounddown || !mayroundup )
426  roundup = mayrounddown;
427 
428  if( roundup )
429  {
430  frac = 1.0 - frac;
431  objgain = frac*obj;
432  }
433  else
434  objgain = -frac*obj;
435 
436  /* penalize too small fractions */
437  if( frac < 0.01 )
438  objgain *= 1000.0;
439 
440  /* prefer decisions on binary variables */
441  if( !SCIPvarIsBinary(var) )
442  objgain *= 1000.0;
443 
444  if( divingdata->usemasterfracs )
445  {
446  SCIP_Real downfrac;
447  SCIP_Real upfrac;
448 
449  SCIP_CALL( getMasterDownFrac(scip, var, &downfrac) );
450  SCIP_CALL( getMasterUpFrac(scip, var, &upfrac) );
451  score = roundup ? upfrac : downfrac;
452  }
453  else
454  score = frac;
455 
456  /* check, if candidate is new best candidate */
457  if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && score < bestscore) )
458  {
459  *bestcand = var;
460  bestobjgain = objgain;
461  bestscore = score;
462  bestcandmayrounddown = mayrounddown;
463  bestcandmayroundup = mayroundup;
464  *bestcandroundup = roundup;
465  }
466  }
467  }
468  else
469  {
470  /* the candidate may not be rounded */
471 
472  if( divingdata->usemasterfracs )
473  {
474  SCIP_Real downfrac;
475  SCIP_Real upfrac;
476 
477  SCIP_CALL( getMasterDownFrac(scip, var, &downfrac) );
478  SCIP_CALL( getMasterUpFrac(scip, var, &upfrac) );
479  score = roundup ? upfrac : downfrac;
480  }
481  else
482  score = roundup? 1.0 - frac : frac;
483 
484  /* penalize too small fractions */
485  if( score < 0.01 )
486  score += 10.0;
487 
488  /* prefer decisions on binary variables */
489  if( !SCIPvarIsBinary(var) )
490  score *= 1000.0;
491 
492  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
493  if( bestcandmayrounddown || bestcandmayroundup || score < bestscore )
494  {
495  *bestcand = var;
496  bestscore = score;
497  bestcandmayrounddown = FALSE;
498  bestcandmayroundup = FALSE;
499  *bestcandroundup = roundup;
500  }
501  }
502  }
503 
504  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
505 
506  return SCIP_OKAY;
507 }
508 
509 
510 /*
511  * heuristic specific interface methods
512  */
513 
516  SCIP* scip
517  )
518 {
519  SCIP_HEUR* heur;
520  GCG_DIVINGDATA* divingdata;
521 
522  /* create gcgguideddiving primal heuristic data */
523  SCIP_CALL( SCIPallocMemory(scip, &divingdata) );
524 
525  /* include diving heuristic */
526  SCIP_CALL( GCGincludeDivingHeurOrig(scip, &heur,
528  HEUR_MAXDEPTH, heurFreeGcgguideddiving, NULL, NULL, NULL, NULL, heurInitexecGcgguideddiving,
529  heurExitexecGcgguideddiving, heurSelectVarGcgguideddiving, divingdata) );
530 
531  assert(heur != NULL);
532 
533  /* add gcgguideddiving specific parameters */
534  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/usemasterfracs",
535  "calculate the fractionalities w.r.t. the master LP?",
536  &divingdata->usemasterfracs, TRUE, DEFAULT_USEMASTERFRACS, NULL, NULL) );
537 
538  return SCIP_OKAY;
539 }
540 
SCIP_Bool usemasterfracs
static GCG_DECL_DIVINGINITEXEC(heurInitexecGcgguideddiving)
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
GCG interface methods.
static SCIP_Bool areVarsInSameBlock(SCIP_VAR *origvar, SCIP_VAR *mastervar)
SCIP_RETCODE GCGincludeHeurGcgguideddiving(SCIP *scip)
LP diving heuristic that chooses fixings in direction of incumbent solutions.
static GCG_DECL_DIVINGEXITEXEC(heurExitexecGcgguideddiving)
static SCIP_RETCODE getMasterUpFrac(SCIP *scip, SCIP_VAR *var, SCIP_Real *frac)
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
GCG_DIVINGDATA * GCGheurGetDivingDataOrig(SCIP_HEUR *heur)
#define HEUR_NAME
static GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgguideddiving)
#define HEUR_DESC
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)
SCIP_Bool GCGisLinkingVarInBlock(SCIP_VAR *var, int block)
Definition: gcgvar.c:965
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:176
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:936
primal heuristic interface for LP diving heuristics on the original variables
static GCG_DECL_DIVINGFREE(heurFreeGcgguideddiving)
static SCIP_RETCODE getMasterDownFrac(SCIP *scip, SCIP_VAR *var, SCIP_Real *frac)
#define HEUR_FREQOFS
#define DEFAULT_USEMASTERFRACS
#define HEUR_FREQ
int GCGoriginalVarGetNMastervars(SCIP_VAR *var)
Definition: gcgvar.c:545
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:561
#define HEUR_PRIORITY
SCIP_Real * GCGoriginalVarGetMastervals(SCIP_VAR *var)
Definition: gcgvar.c:577
void GCGheurSetDivingDataOrig(SCIP_HEUR *heur, GCG_DIVINGDATA *divingdata)