heur_gcgcoefdiving.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_gcgcoefdiving.h"
40 #include "heur_origdiving.h"
41 #include "gcg.h"
42 
43 
44 #define HEUR_NAME "gcgcoefdiving"
45 #define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. the matrix coefficients"
46 #define HEUR_DISPCHAR 'c'
47 #define HEUR_PRIORITY -1001000
48 #define HEUR_FREQ 10
49 #define HEUR_FREQOFS 1
50 #define HEUR_MAXDEPTH -1
51 
52 
53 /*
54  * Default diving rule specific parameter settings
55  */
56 
57 #define DEFAULT_USEMASTERLOCKS FALSE
60 /* locally defined diving heuristic data */
62 {
63  SCIP_Bool usemasterlocks;
64 };
65 
66 
67 /*
68  * local methods
69  */
70 
72 static
74  SCIP_VAR* origvar,
75  SCIP_VAR* mastervar
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 
127 static
128 SCIP_RETCODE getNLocksDown(
129  SCIP* scip,
130  SCIP_VAR* var,
131  int* nlocksdown
132  )
133 {
134  SCIP* masterprob;
135  SCIP_VAR** mastervars;
136  SCIP_VAR** origmastervars;
137  SCIP_Real* origmastervals;
138  int nmastervars;
139  int norigmastervars;
140  SCIP_Real roundval;
141 
142  int i;
143 
144  /* get master problem */
145  masterprob = GCGgetMasterprob(scip);
146  assert(masterprob != NULL);
147 
148  /* get master variable information */
149  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
150 
151  /* get master variables in which the original variable appears */
152  origmastervars = GCGoriginalVarGetMastervars(var);
153  origmastervals = GCGoriginalVarGetMastervals(var);
154  norigmastervars = GCGoriginalVarGetNMastervars(var);
155 
156  roundval = SCIPfeasFloor(scip, SCIPgetRelaxSolVal(scip, var));
157  *nlocksdown = 0;
158 
159  /* calculate locks = the sum of down-locks of all master variables
160  * which would have to be fixed to zero if the original variable were rounded down
161  */
162  if( SCIPisFeasNegative(masterprob, roundval) )
163  {
164  for( i = 0; i < nmastervars; ++i )
165  {
166  if( areVarsInSameBlock(var, mastervars[i] )
167  && !SCIPisFeasZero(masterprob, SCIPgetSolVal(masterprob, NULL, mastervars[i])) )
168  *nlocksdown += SCIPvarGetNLocksDown(mastervars[i]);
169  }
170  for( i = 0; i < norigmastervars; ++i )
171  if( !SCIPisFeasZero(masterprob, SCIPgetSolVal(masterprob, NULL, origmastervars[i]) )
172  && SCIPisFeasLE(masterprob, origmastervals[i], roundval) )
173  *nlocksdown -= SCIPvarGetNLocksDown(origmastervars[i]);
174  }
175  else
176  {
177  for( i = 0; i < norigmastervars; ++i )
178  if( !SCIPisFeasZero(masterprob, SCIPgetSolVal(masterprob, NULL, origmastervars[i]) )
179  && SCIPisFeasGT(masterprob, origmastervals[i], roundval) )
180  *nlocksdown += SCIPvarGetNLocksDown(origmastervars[i]);
181  }
182  assert(*nlocksdown >= 0);
183 
184  return SCIP_OKAY;
185 }
186 
188 static
189 SCIP_RETCODE getNLocksUp(
190  SCIP* scip,
191  SCIP_VAR* var,
192  int* nlocksup
193  )
194 {
195  SCIP* masterprob;
196  SCIP_VAR** mastervars;
197  SCIP_VAR** origmastervars;
198  SCIP_Real* origmastervals;
199  int nmastervars;
200  int norigmastervars;
201  SCIP_Real roundval;
202 
203  int i;
204 
205  /* get master problem */
206  masterprob = GCGgetMasterprob(scip);
207  assert(masterprob != NULL);
208 
209  /* get master variable information */
210  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
211 
212  /* get master variables in which the original variable appears */
213  origmastervars = GCGoriginalVarGetMastervars(var);
214  origmastervals = GCGoriginalVarGetMastervals(var);
215  norigmastervars = GCGoriginalVarGetNMastervars(var);
216 
217  roundval = SCIPfeasCeil(scip, SCIPgetRelaxSolVal(scip, var));
218  *nlocksup = 0;
219 
220  /* calculate locks = the sum of down-locks of all master variables
221  * which would have to be fixed to zero if the original variable were rounded up
222  */
223  if( SCIPisFeasPositive(masterprob, roundval) )
224  {
225  for( i = 0; i < nmastervars; ++i )
226  {
227  if( areVarsInSameBlock(var, mastervars[i] )
228  && !SCIPisFeasZero(masterprob, SCIPgetSolVal(masterprob, NULL, mastervars[i])) )
229  *nlocksup += SCIPvarGetNLocksDown(mastervars[i]);
230  }
231  for( i = 0; i < norigmastervars; ++i )
232  if( !SCIPisFeasZero(masterprob, SCIPgetSolVal(masterprob, NULL, origmastervars[i]) )
233  && SCIPisFeasGE(masterprob, origmastervals[i], roundval) )
234  *nlocksup -= SCIPvarGetNLocksDown(origmastervars[i]);
235  }
236  else
237  {
238  for( i = 0; i < norigmastervars; ++i )
239  if( !SCIPisFeasZero(masterprob, SCIPgetSolVal(masterprob, NULL, origmastervars[i]) )
240  && SCIPisFeasLT(masterprob, origmastervals[i], roundval) )
241  *nlocksup += SCIPvarGetNLocksDown(origmastervars[i]);
242  }
243  assert(*nlocksup >= 0);
244 
245  return SCIP_OKAY;
246 }
247 
248 
249 /*
250  * Callback methods
251  */
252 
254 static
255 GCG_DECL_DIVINGFREE(heurFreeGcgcoefdiving) /*lint --e{715}*/
256 { /*lint --e{715}*/
257  GCG_DIVINGDATA* divingdata;
258 
259  assert(heur != NULL);
260  assert(scip != NULL);
261 
262  /* free diving rule specific data */
263  divingdata = GCGheurGetDivingDataOrig(heur);
264  assert(divingdata != NULL);
265  SCIPfreeMemory(scip, &divingdata);
266  GCGheurSetDivingDataOrig(heur, NULL);
267 
268  return SCIP_OKAY;
269 }
270 
271 
280 static
281 GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgcoefdiving) /*lint --e{715}*/
282 { /*lint --e{715}*/
283  GCG_DIVINGDATA* divingdata;
284  SCIP_VAR** lpcands;
285  SCIP_Real* lpcandssol;
286  int nlpcands;
287  SCIP_Bool bestcandmayrounddown;
288  SCIP_Bool bestcandmayroundup;
289  int bestnviolrows; /* number of violated rows for best candidate */
290  SCIP_Real bestcandfrac; /* fractionality of best candidate */
291  int c;
292 
293  /* check preconditions */
294  assert(scip != NULL);
295  assert(heur != NULL);
296  assert(bestcand != NULL);
297  assert(bestcandmayround != NULL);
298  assert(bestcandroundup != NULL);
299 
300  /* get diving data */
301  divingdata = GCGheurGetDivingDataOrig(heur);
302  assert(divingdata != NULL);
303 
304  /* get fractional variables that should be integral */
305  SCIP_CALL( SCIPgetExternBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL, NULL, NULL) );
306  assert(lpcands != NULL);
307  assert(lpcandssol != NULL);
308 
309  bestcandmayrounddown = TRUE;
310  bestcandmayroundup = TRUE;
311  bestnviolrows = INT_MAX;
312  bestcandfrac = SCIP_INVALID;
313 
314  /* get best candidate */
315  for( c = 0; c < nlpcands; ++c )
316  {
317  SCIP_VAR* var;
318 
319  int nlocksdown;
320  int nlocksup;
321  int nviolrows;
322 
323  int i;
324 
325  SCIP_Bool mayrounddown;
326  SCIP_Bool mayroundup;
327  SCIP_Bool roundup;
328  SCIP_Real frac;
329 
330  var = lpcands[c];
331  frac = lpcandssol[c] - SCIPfloor(scip, lpcandssol[c]);
332 
333  /* if the variable is on the tabu list, do not choose it */
334  for( i = 0; i < tabulistsize; ++i )
335  if( tabulist[i] == var )
336  break;
337  if( i < tabulistsize )
338  continue;
339 
340  if( divingdata->usemasterlocks )
341  {
342  SCIP_CALL( getNLocksDown(scip, var, &nlocksdown) );
343  SCIP_CALL( getNLocksUp(scip, var, &nlocksup) );
344  mayrounddown = nlocksdown == 0;
345  mayroundup = nlocksup == 0;
346  }
347  else
348  {
349  nlocksdown = SCIPvarGetNLocksDown(var);
350  nlocksup = SCIPvarGetNLocksUp(var);
351  mayrounddown = SCIPvarMayRoundDown(var);
352  mayroundup = SCIPvarMayRoundUp(var);
353  }
354 
355  if( mayrounddown || mayroundup )
356  {
357  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
358  if( bestcandmayrounddown || bestcandmayroundup )
359  {
360  /* choose rounding direction:
361  * - if variable may be rounded in both directions, round corresponding to the fractionality
362  * - otherwise, round in the infeasible direction, because feasible direction is tried by rounding
363  * the current fractional solution
364  */
365  if( mayrounddown && mayroundup )
366  roundup = (frac > 0.5);
367  else
368  roundup = mayrounddown;
369 
370  if( roundup )
371  {
372  frac = 1.0 - frac;
373  nviolrows = nlocksup;
374  }
375  else
376  nviolrows = nlocksdown;
377 
378  /* penalize too small fractions */
379  if( frac < 0.01 )
380  nviolrows *= 100;
381 
382  /* prefer decisions on binary variables */
383  if( !SCIPvarIsBinary(var) )
384  nviolrows *= 100;
385 
386  /* check, if candidate is new best candidate */
387  assert(0.0 < frac && frac < 1.0);
388  if( nviolrows + frac < bestnviolrows + bestcandfrac )
389  {
390  *bestcand = var;
391  bestnviolrows = nviolrows;
392  bestcandfrac = frac;
393  bestcandmayrounddown = mayrounddown;
394  bestcandmayroundup = mayroundup;
395  *bestcandroundup = roundup;
396  }
397  }
398  }
399  else
400  {
401  /* the candidate may not be rounded */
402  roundup = (nlocksdown > nlocksup || (nlocksdown == nlocksup && frac > 0.5));
403  if( roundup )
404  {
405  nviolrows = nlocksup;
406  frac = 1.0 - frac;
407  }
408  else
409  nviolrows = nlocksdown;
410 
411  /* penalize too small fractions */
412  if( frac < 0.01 )
413  nviolrows *= 100;
414 
415  /* prefer decisions on binary variables */
416  if( !SCIPvarIsBinary(var) )
417  nviolrows *= 100;
418 
419  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
420  assert(0.0 < frac && frac < 1.0);
421  if( bestcandmayrounddown || bestcandmayroundup || nviolrows + frac < bestnviolrows + bestcandfrac )
422  {
423  *bestcand = var;
424  bestnviolrows = nviolrows;
425  bestcandfrac = frac;
426  bestcandmayrounddown = FALSE;
427  bestcandmayroundup = FALSE;
428  *bestcandroundup = roundup;
429  }
430  assert(bestcandfrac < SCIP_INVALID);
431  }
432  }
433 
434  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
435 
436  return SCIP_OKAY;
437 }
438 
439 
440 /*
441  * heuristic specific interface methods
442  */
443 
446  SCIP* scip
447  )
448 {
449  SCIP_HEUR* heur;
450  GCG_DIVINGDATA* divingdata;
451 
452  /* create gcgcoefdiving primal heuristic data */
453  SCIP_CALL( SCIPallocMemory(scip, &divingdata) );
454 
455  /* include diving heuristic */
456  SCIP_CALL( GCGincludeDivingHeurOrig(scip, &heur,
458  HEUR_MAXDEPTH, heurFreeGcgcoefdiving, NULL, NULL, NULL, NULL, NULL, NULL,
459  heurSelectVarGcgcoefdiving, divingdata) );
460 
461  assert(heur != NULL);
462 
463  /* add gcgcoefdiving specific parameters */
464  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/usemasterlocks",
465  "calculate the number of locks w.r.t. the master LP?",
466  &divingdata->usemasterlocks, TRUE, DEFAULT_USEMASTERLOCKS, NULL, NULL) );
467 
468  return SCIP_OKAY;
469 }
470 
#define HEUR_FREQ
GCG interface methods.
#define HEUR_NAME
#define HEUR_DESC
static SCIP_Bool areVarsInSameBlock(SCIP_VAR *origvar, SCIP_VAR *mastervar)
#define HEUR_DISPCHAR
static GCG_DECL_DIVINGFREE(heurFreeGcgcoefdiving)
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3838
GCG_DIVINGDATA * GCGheurGetDivingDataOrig(SCIP_HEUR *heur)
LP diving heuristic that chooses fixings w.r.t. the matrix coefficients.
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 DEFAULT_USEMASTERLOCKS
SCIP_Bool usemasterlocks
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
static SCIP_RETCODE getNLocksUp(SCIP *scip, SCIP_VAR *var, int *nlocksup)
primal heuristic interface for LP diving heuristics on the original variables
#define HEUR_MAXDEPTH
static SCIP_RETCODE getNLocksDown(SCIP *scip, SCIP_VAR *var, int *nlocksdown)
#define HEUR_FREQOFS
static GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgcoefdiving)
SCIP_RETCODE GCGincludeHeurGcgcoefdiving(SCIP *scip)
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)