Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_gcgveclendiving.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_gcgveclendiving.c
29  * @brief LP diving heuristic that rounds variables with long column vectors
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_gcgveclendiving.h"
40 #include "heur_origdiving.h"
41 #include "gcg.h"
42 
43 
44 #define HEUR_NAME "gcgveclendiving"
45 #define HEUR_DESC "LP diving heuristic that rounds variables with long column vectors"
46 #define HEUR_DISPCHAR 'v'
47 #define HEUR_PRIORITY -1003100
48 #define HEUR_FREQ 10
49 #define HEUR_FREQOFS 4
50 #define HEUR_MAXDEPTH -1
51 
52 
53 /*
54  * Default diving rule specific parameter settings
55  */
56 
57 #define DEFAULT_USEMASTERSCORES FALSE /**< calculate vector length scores w.r.t. the master LP? */
58 
59 
60 /* locally defined diving heuristic data */
61 struct GCG_DivingData
62 {
63  SCIP_Bool usemasterscores; /**< calculate vector length scores w.r.t. the master LP? */
64  SCIP_Real* masterscores; /**< vector length based scores for the master variables */
65 };
66 
67 
68 /*
69  * local methods
70  */
71 
72 /** for a variable, calculate the vector length score w.r.t. the original problem */
73 static
74 SCIP_RETCODE calculateScoreOrig(
75  SCIP* scip, /**< SCIP data structure */
76  SCIP_VAR* var, /**< variable to calculate score for */
77  SCIP_Real frac, /**< the variable's fractionality in the current LP solution */
78  SCIP_Real* score, /**< pointer to return the score */
79  SCIP_Bool* roundup /**< pointer to return whether the variable is rounded up */
80  )
81 {
82  SCIP_Real obj;
83  SCIP_Real objdelta;
84  int colveclen;
85 
86  obj = SCIPvarGetObj(var);
87  *roundup = (obj >= 0.0);
88  objdelta = (*roundup ? (1.0-frac)*obj : -frac * obj);
89  assert(objdelta >= 0.0);
90 
91  colveclen = (SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN ? SCIPcolGetNNonz(SCIPvarGetCol(var)) : 0);
92 
93  /* smaller score is better */
94  *score = (objdelta + SCIPsumepsilon(scip))/((SCIP_Real)colveclen+1.0);
95 
96  /* prefer decisions on binary variables */
97  if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
98  *score *= 1000.0;
99 
100  return SCIP_OKAY;
101 }
102 
103 /** check whether an original variable and a master variable belong to the same block */
104 static
106  SCIP_VAR* origvar, /**< original variable */
107  SCIP_VAR* mastervar /**< master variable */
108  )
109 {
110  int origblock;
111  int masterblock;
112 
113  /* get the blocks the variables belong to */
114  origblock = GCGvarGetBlock(origvar);
115  masterblock = GCGvarGetBlock(mastervar);
116 
117  /* the original variable is a linking variable:
118  * check whether the master variable is either its direct copy
119  * or in one of its blocks
120  */
121  if( GCGoriginalVarIsLinking(origvar) )
122  {
123  assert(origblock == -2);
124  if( masterblock == -1 )
125  {
126  SCIP_VAR** mastervars;
127 
128  mastervars = GCGoriginalVarGetMastervars(origvar);
129 
130  return mastervars[0] == mastervar;
131  }
132  else
133  {
134  assert(masterblock >= 0);
135  return GCGisLinkingVarInBlock(origvar, masterblock);
136  }
137  }
138  /* the original variable was directly copied to the master problem:
139  * check whether the master variable is its copy
140  */
141  else if( origblock == -1 )
142  {
143  SCIP_VAR** mastervars;
144 
145  mastervars = GCGoriginalVarGetMastervars(origvar);
146  assert(GCGoriginalVarGetNMastervars(origvar) == 1);
147 
148  return mastervars[0] == mastervar;
149  }
150  /* the original variable belongs to exactly one block */
151  else
152  {
153  assert(origblock >= 0);
154  return origblock == masterblock;
155  }
156 }
157 
158 /** get the 'down' score of an original variable w.r.t. the master problem;
159  * this is the sum of the vector length scores of the master variables
160  * which would have to be fixed to zero if the original variable were rounded down
161  */
162 static
163 SCIP_RETCODE getMasterDownScore(
164  SCIP* scip, /**< SCIP data structure */
165  GCG_DIVINGDATA* divingdata, /**< diving heuristic data */
166  SCIP_VAR* var, /**< original variable to get fractionality for */
167  SCIP_Real* score /**< pointer to store fractionality */
168  )
169 {
170  SCIP* masterprob;
171  SCIP_VAR** mastervars;
172  SCIP_Real* origmastervals;
173  int nmastervars;
174  int norigmastervars;
175  SCIP_Real roundval;
176 
177  int i;
178 
179  /* get master problem */
180  masterprob = GCGgetMasterprob(scip);
181  assert(masterprob != NULL);
182 
183  /* get master variable information */
184  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
185 
186  /* get master variables in which the original variable appears */
187  origmastervals = GCGoriginalVarGetMastervals(var);
188  norigmastervars = GCGoriginalVarGetNMastervars(var);
189 
190  roundval = SCIPfeasFloor(scip, SCIPgetRelaxSolVal(scip, var));
191  *score = 0.0;
192 
193  /* calculate sum of scores over all master variables
194  * which would violate the new original variable bound
195  */
196  if( SCIPisFeasNegative(masterprob, roundval) )
197  {
198  for( i = 0; i < nmastervars; ++i )
199  if( areVarsInSameBlock(var, mastervars[i]) )
200  *score += divingdata->masterscores[i];
201  for( i = 0; i < norigmastervars; ++i )
202  if( SCIPisFeasLE(masterprob, origmastervals[i], roundval) )
203  *score -= divingdata->masterscores[i];
204  }
205  else
206  {
207  for( i = 0; i < norigmastervars; ++i )
208  if( SCIPisFeasGT(masterprob, origmastervals[i], roundval) )
209  *score += divingdata->masterscores[i];
210  }
211 
212  return SCIP_OKAY;
213 }
214 
215 /** get the 'up' score of an original variable w.r.t. the master problem;
216  * this is the sum of the scores of the master variables
217  * which would have to be fixed to zero if the original variable were rounded up
218  */
219 static
220 SCIP_RETCODE getMasterUpScore(
221  SCIP* scip, /**< SCIP data structure */
222  GCG_DIVINGDATA* divingdata, /**< diving heuristic data */
223  SCIP_VAR* var, /**< original variable to get fractionality for */
224  SCIP_Real* score /**< pointer to store fractionality */
225  )
226 {
227  SCIP* masterprob;
228  SCIP_VAR** mastervars;
229  SCIP_Real* origmastervals;
230  int nmastervars;
231  int norigmastervars;
232  SCIP_Real roundval;
233 
234  int i;
235 
236  /* get master problem */
237  masterprob = GCGgetMasterprob(scip);
238  assert(masterprob != NULL);
239 
240  /* get master variable information */
241  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
242 
243  /* get master variables in which the original variable appears */
244  origmastervals = GCGoriginalVarGetMastervals(var);
245  norigmastervars = GCGoriginalVarGetNMastervars(var);
246 
247  roundval = SCIPfeasCeil(scip, SCIPgetRelaxSolVal(scip, var));
248  *score = 0.0;
249 
250  /* calculate sum of scores over all master variables
251  * which would violate the new original variable bound
252  */
253  if( SCIPisFeasPositive(masterprob, roundval) )
254  {
255  for( i = 0; i < nmastervars; ++i )
256  if( areVarsInSameBlock(var, mastervars[i]) )
257  *score += divingdata->masterscores[i];
258  for( i = 0; i < norigmastervars; ++i )
259  if( SCIPisFeasGE(masterprob, origmastervals[i], roundval) )
260  *score -= divingdata->masterscores[i];
261  }
262  else
263  {
264  for( i = 0; i < norigmastervars; ++i )
265  if( SCIPisFeasLT(masterprob, origmastervals[i], roundval) )
266  *score += divingdata->masterscores[i];
267  }
268 
269  return SCIP_OKAY;
270 }
271 
272 /** for a variable, calculate the vector length score w.r.t. the master problem */
273 static
274 SCIP_RETCODE calculateScoreMaster(
275  SCIP* scip, /**< SCIP data structure */
276  GCG_DIVINGDATA* divingdata, /**< diving heuristic data */
277  SCIP_VAR* var, /**< variable to calculate score for */
278  SCIP_Real* score, /**< pointer to return the score */
279  SCIP_Bool* roundup /**< pointer to return whether the variable is rounded up */
280  )
281 {
282  SCIP_Real downscore;
283  SCIP_Real upscore;
284 
285  /* calculate scores for rounding down or up */
286  SCIP_CALL( getMasterDownScore(scip, divingdata, var, &downscore) );
287  SCIP_CALL( getMasterUpScore(scip, divingdata, var, &upscore) );
288 
289  *score = MIN(downscore, upscore);
290  *roundup = upscore <= downscore;
291 
292  /* prefer decisions on binary variables */
293  if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
294  *score *= 1000.0;
295 
296  return SCIP_OKAY;
297 }
298 
299 
300 /*
301  * Callback methods
302  */
303 
304 
305 /** destructor of diving heuristic to free user data (called when GCG is exiting) */
306 static
307 GCG_DECL_DIVINGFREE(heurFreeGcgveclendiving) /*lint --e{715}*/
308 { /*lint --e{715}*/
309  GCG_DIVINGDATA* divingdata;
310 
311  assert(heur != NULL);
312  assert(scip != NULL);
313 
314  /* free diving rule specific data */
315  divingdata = GCGheurGetDivingDataOrig(heur);
316  assert(divingdata != NULL);
317  SCIPfreeMemory(scip, &divingdata);
318  GCGheurSetDivingDataOrig(heur, NULL);
319 
320  return SCIP_OKAY;
321 }
322 
323 
324 /** execution initialization method of diving heuristic (called when execution of diving heuristic is about to begin) */
325 static
326 GCG_DECL_DIVINGINITEXEC(heurInitexecGcgveclendiving) /*lint --e{715}*/
327 { /*lint --e{715}*/
328  GCG_DIVINGDATA* divingdata;
329  SCIP* masterprob;
330  SCIP_SOL* masterlpsol;
331  SCIP_VAR** mastervars;
332  int nmastervars;
333 
334  int i;
335 
336  assert(heur != NULL);
337 
338  /* get diving data */
339  divingdata = GCGheurGetDivingDataOrig(heur);
340  assert(divingdata != NULL);
341 
342  /* do not collect vector length scores on master variables if not used */
343  if( !divingdata->usemasterscores )
344  return SCIP_OKAY;
345 
346  /* get master problem */
347  masterprob = GCGgetMasterprob(scip);
348  assert(masterprob != NULL);
349 
350  /* get master variables */
351  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
352 
353  /* allocate memory */
354  SCIP_CALL( SCIPallocBufferArray(scip, &divingdata->masterscores, nmastervars) );
355  SCIP_CALL( SCIPcreateSol(masterprob, &masterlpsol, NULL) );
356 
357  /* get master LP solution */
358  SCIP_CALL( SCIPlinkLPSol(masterprob, masterlpsol) );
359 
360  /* for each master variable, calculate a score */
361  for( i = 0; i < nmastervars; ++i )
362  {
363  SCIP_VAR* mastervar;
364  SCIP_Real objdelta;
365  int colveclen;
366 
367  mastervar = mastervars[i];
368  objdelta = SCIPfeasFrac(masterprob, SCIPgetSolVal(masterprob, masterlpsol, mastervar)) * SCIPvarGetObj(mastervar);
369  objdelta = ABS(objdelta);
370  colveclen = (SCIPvarGetStatus(mastervar) == SCIP_VARSTATUS_COLUMN ? SCIPcolGetNNonz(SCIPvarGetCol(mastervar)) : 0);
371  divingdata->masterscores[i] = (objdelta + SCIPsumepsilon(scip))/((SCIP_Real)colveclen+1.0);
372  }
373 
374  /* free memory */
375  SCIP_CALL( SCIPfreeSol(masterprob, &masterlpsol) );
376 
377  return SCIP_OKAY;
378 }
379 
380 
381 /** execution deinitialization method of diving heuristic (called when execution data is freed) */
382 static
383 GCG_DECL_DIVINGEXITEXEC(heurExitexecGcgveclendiving) /*lint --e{715}*/
384 { /*lint --e{715}*/
385  GCG_DIVINGDATA* divingdata;
386 
387  assert(heur != NULL);
388 
389  /* get diving data */
390  divingdata = GCGheurGetDivingDataOrig(heur);
391  assert(divingdata != NULL);
392 
393  /* memory needs to to be freed if vector length scores on master variables were not used */
394  if( !divingdata->usemasterscores )
395  return SCIP_OKAY;
396 
397  /* free memory */
398  SCIPfreeBufferArray(scip, &divingdata->masterscores);
399 
400  return SCIP_OKAY;
401 }
402 
403 
404 /** variable selection method of diving heuristic;
405  * finds best candidate variable w.r.t. vector length:
406  * - round variables in direction where objective value gets worse; for zero objective coefficient, round upwards
407  * - round variable with least objective value deficit per row the variable appears in
408  * (we want to "fix" as many rows as possible with the least damage to the objective function)
409  */
410 static
411 GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgveclendiving) /*lint --e{715}*/
412 { /*lint --e{715}*/
413  GCG_DIVINGDATA* divingdata;
414  SCIP_VAR** lpcands;
415  SCIP_Real* lpcandssol;
416  int nlpcands;
417  SCIP_Real bestscore;
418  int c;
419 
420  /* check preconditions */
421  assert(scip != NULL);
422  assert(heur != NULL);
423  assert(bestcand != NULL);
424  assert(bestcandmayround != NULL);
425  assert(bestcandroundup != NULL);
426 
427  /* get diving data */
428  divingdata = GCGheurGetDivingDataOrig(heur);
429  assert(divingdata != NULL);
430 
431  /* get fractional variables that should be integral */
432  SCIP_CALL( SCIPgetExternBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL, NULL, NULL) );
433  assert(lpcands != NULL);
434  assert(lpcandssol != NULL);
435 
436  bestscore = SCIP_REAL_MAX;
437 
438  /* get best candidate */
439  for( c = 0; c < nlpcands; ++c )
440  {
441  SCIP_Real score;
442  SCIP_Bool roundup;
443 
444  int i;
445 
446  /* if the variable is on the tabu list, do not choose it */
447  for( i = 0; i < tabulistsize; ++i )
448  if( tabulist[i] == lpcands[c] )
449  break;
450  if( i < tabulistsize )
451  continue;
452 
453  /* calculate score */
454  if( divingdata->usemasterscores )
455  {
456  SCIP_CALL( calculateScoreMaster(scip, divingdata, lpcands[c], &score, &roundup) );
457  }
458  else
459  {
460  SCIP_CALL( calculateScoreOrig(scip, lpcands[c], lpcandssol[c] - SCIPfloor(scip, lpcandssol[c]), &score, &roundup) );
461  }
462 
463  /* check whether the variable is roundable */
464  *bestcandmayround = *bestcandmayround && (SCIPvarMayRoundDown(lpcands[c]) || SCIPvarMayRoundUp(lpcands[c]));
465 
466  /* check, if candidate is new best candidate */
467  if( score < bestscore )
468  {
469  *bestcand = lpcands[c];
470  bestscore = score;
471  *bestcandroundup = roundup;
472  }
473  }
474 
475  return SCIP_OKAY;
476 }
477 
478 
479 /*
480  * heuristic specific interface methods
481  */
482 
483 /** creates the gcgveclendiving heuristic and includes it in GCG */
485  SCIP* scip /**< SCIP data structure */
486  )
487 {
488  SCIP_HEUR* heur;
489  GCG_DIVINGDATA* divingdata;
490 
491  /* create gcgguideddiving primal heuristic data */
492  SCIP_CALL( SCIPallocMemory(scip, &divingdata) );
493 
494  /* include diving heuristic */
495  SCIP_CALL( GCGincludeDivingHeurOrig(scip, &heur,
497  HEUR_MAXDEPTH, heurFreeGcgveclendiving, NULL, NULL, NULL, NULL, heurInitexecGcgveclendiving,
498  heurExitexecGcgveclendiving, heurSelectVarGcgveclendiving, divingdata) );
499 
500  assert(heur != NULL);
501 
502  /* add gcgveclendiving specific parameters */
503  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/usemasterscores",
504  "calculate vector length scores w.r.t. the master LP?",
505  &divingdata->usemasterscores, TRUE, DEFAULT_USEMASTERSCORES, NULL, NULL) );
506 
507  return SCIP_OKAY;
508 }
509 
GCG_DIVINGDATA * GCGheurGetDivingDataOrig(SCIP_HEUR *heur)
SCIP_Real * masterscores
#define DEFAULT_USEMASTERSCORES
#define HEUR_PRIORITY
GCG interface methods.
SCIP_RETCODE GCGincludeHeurGcgveclendiving(SCIP *scip)
int GCGoriginalVarGetNMastervars(SCIP_VAR *var)
Definition: gcgvar.c:569
static SCIP_RETCODE getMasterUpScore(SCIP *scip, GCG_DIVINGDATA *divingdata, SCIP_VAR *var, SCIP_Real *score)
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:587
SCIP_Bool GCGisLinkingVarInBlock(SCIP_VAR *var, int block)
Definition: gcgvar.c:1064
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:1033
primal heuristic interface for LP diving heuristics on the original variables
SCIP_Real * GCGoriginalVarGetMastervals(SCIP_VAR *var)
Definition: gcgvar.c:605
#define HEUR_FREQ
static GCG_DECL_DIVINGINITEXEC(heurInitexecGcgveclendiving)
static GCG_DECL_DIVINGFREE(heurFreeGcgveclendiving)
static GCG_DECL_DIVINGEXITEXEC(heurExitexecGcgveclendiving)
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
#define HEUR_DESC
static SCIP_RETCODE getMasterDownScore(SCIP *scip, GCG_DIVINGDATA *divingdata, SCIP_VAR *var, SCIP_Real *score)
#define HEUR_FREQOFS
LP diving heuristic that rounds variables with long column vectors.
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)
static SCIP_RETCODE calculateScoreMaster(SCIP *scip, GCG_DIVINGDATA *divingdata, SCIP_VAR *var, SCIP_Real *score, SCIP_Bool *roundup)
void GCGheurSetDivingDataOrig(SCIP_HEUR *heur, GCG_DIVINGDATA *divingdata)
static SCIP_RETCODE calculateScoreOrig(SCIP *scip, SCIP_VAR *var, SCIP_Real frac, SCIP_Real *score, SCIP_Bool *roundup)
#define HEUR_DISPCHAR
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:182
static SCIP_Bool areVarsInSameBlock(SCIP_VAR *origvar, SCIP_VAR *mastervar)
#define HEUR_NAME
#define HEUR_MAXDEPTH
static GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcgveclendiving)