Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_masterfracdiving.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_masterfracdiving.c
29  * @brief master 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_masterfracdiving.h"
40 #include "heur_masterdiving.h"
41 
42 
43 #define HEUR_NAME "masterfracdiving"
44 #define HEUR_DESC "master LP diving heuristic that chooses fixings w.r.t. the fractionalities"
45 #define HEUR_DISPCHAR 'f'
46 #define HEUR_PRIORITY -1003000
47 #define HEUR_FREQ 10
48 #define HEUR_FREQOFS 3
49 #define HEUR_MAXDEPTH -1
50 
51 
52 /*
53  * Callback methods
54  */
55 
56 /** variable selection method of diving heuristic;
57  * finds best candidate variable w.r.t. fractionality:
58  * - prefer variables that may not be rounded without destroying LP feasibility:
59  * - of these variables, round least fractional variable in corresponding direction
60  * - if all remaining fractional variables may be rounded without destroying LP feasibility:
61  * - round variable with least increasing objective value
62  * - binary variables are preferred
63  */
64 static
65 GCG_DECL_DIVINGSELECTVAR(heurSelectVarMasterfracdiving) /*lint --e{715}*/
66 { /*lint --e{715}*/
67  SCIP_VAR** lpcands;
68  SCIP_Real* lpcandssol;
69  SCIP_Real* lpcandsfrac;
70  int nlpcands;
71  SCIP_Real bestobjgain;
72  SCIP_Real bestfrac;
73  SCIP_Bool bestcandmayrounddown;
74  SCIP_Bool bestcandmayroundup;
75  int c;
76 
77  /* check preconditions */
78  assert(scip != NULL);
79  assert(heur != NULL);
80  assert(bestcand != NULL);
81  assert(bestcandmayround != NULL);
82 
83  /* get fractional variables that should be integral */
84  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
85  assert(lpcands != NULL);
86  assert(lpcandsfrac != NULL);
87  assert(lpcandssol != NULL);
88 
89  bestcandmayrounddown = TRUE;
90  bestcandmayroundup = TRUE;
91  bestobjgain = SCIPinfinity(scip);
92  bestfrac = SCIP_INVALID;
93 
94  for( c = 0; c < nlpcands; ++c )
95  {
96  SCIP_VAR* var;
97  SCIP_Bool mayrounddown;
98  SCIP_Bool mayroundup;
99  SCIP_Real frac;
100  SCIP_Real obj;
101 
102  int i;
103 
104  var = lpcands[c];
105 
106  mayrounddown = SCIPvarMayRoundDown(var);
107  mayroundup = SCIPvarMayRoundUp(var);
108  frac = lpcandsfrac[c];
109  obj = SCIPvarGetObj(var);
110 
111  /* if the variable is on the tabu list, do not choose it */
112  for( i = 0; i < tabulistsize; ++i )
113  if( tabulist[i] == var )
114  break;
115  if( i < tabulistsize )
116  continue;
117 
118  if( mayrounddown || mayroundup )
119  {
120  /* the candidate may be rounded: choose this candidate only, if the best candidate may also be rounded */
121  if( bestcandmayrounddown || bestcandmayroundup )
122  {
123  SCIP_Real objgain;
124 
125  objgain = (1.0-frac)*obj;
126 
127  /* penalize too small fractions */
128  if( ABS(1.0 - frac) < 0.01 )
129  objgain *= 1000.0;
130 
131  /* prefer decisions on binary variables */
132  if( !SCIPvarIsBinary(var) )
133  objgain *= 1000.0;
134 
135  /* check, if candidate is new best candidate */
136  if( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac > bestfrac) )
137  {
138  *bestcand = var;
139  bestobjgain = objgain;
140  bestfrac = frac;
141  bestcandmayrounddown = mayrounddown;
142  bestcandmayroundup = mayroundup;
143  }
144  }
145  }
146  else
147  {
148  /* penalize too small fractions */
149  if( ABS(1.0-frac) < 0.01 )
150  frac += 10.0;
151 
152  /* prefer decisions on binary variables */
153  if( !SCIPvarIsBinary(var) )
154  frac *= 1000.0;
155 
156  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
157  if( bestcandmayrounddown || bestcandmayroundup || frac > bestfrac )
158  {
159  *bestcand = var;
160  bestfrac = frac;
161  bestcandmayrounddown = FALSE;
162  bestcandmayroundup = FALSE;
163  }
164  assert(bestfrac < SCIP_INVALID);
165  }
166  }
167 
168  *bestcandmayround = bestcandmayroundup || bestcandmayrounddown;
169 
170  return SCIP_OKAY;
171 }
172 
173 
174 /*
175  * heuristic specific interface methods
176  */
177 
178 /** creates the masterfracdiving heuristic and includes it in GCG */
180  SCIP* scip /**< SCIP data structure */
181  )
182 {
183  SCIP_HEUR* heur;
184 
185  /* include diving heuristic */
186  SCIP_CALL( GCGincludeDivingHeurMaster(scip, &heur,
188  HEUR_MAXDEPTH, NULL, NULL, NULL, NULL, NULL, NULL, NULL, heurSelectVarMasterfracdiving, NULL) );
189 
190  assert(heur != NULL);
191 
192  return SCIP_OKAY;
193 }
194 
#define HEUR_DISPCHAR
master LP diving heuristic that chooses fixings w.r.t. the fractionalities
#define HEUR_PRIORITY
static GCG_DECL_DIVINGSELECTVAR(heurSelectVarMasterfracdiving)
#define HEUR_MAXDEPTH
#define HEUR_NAME
#define HEUR_FREQOFS
#define HEUR_FREQ
primal heuristic interface for LP diving heuristics on the master variables
SCIP_RETCODE GCGincludeHeurMasterfracdiving(SCIP *scip)
#define HEUR_DESC
SCIP_RETCODE GCGincludeDivingHeurMaster(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)