Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_gcglinesdiving.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_gcglinesdiving.c
29  * @brief LP diving heuristic that fixes variables with a large difference to their root solution
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_gcglinesdiving.h"
40 #include "heur_origdiving.h"
41 #include "gcg.h"
42 
43 
44 #define HEUR_NAME "gcglinesdiving"
45 #define HEUR_DESC "LP diving heuristic that chooses fixings following the line from root solution to current solution"
46 #define HEUR_DISPCHAR 'l'
47 #define HEUR_PRIORITY -1006000
48 #define HEUR_FREQ 10
49 #define HEUR_FREQOFS 6
50 #define HEUR_MAXDEPTH -1
51 
52 
53 /*
54  * Default diving rule specific parameter settings
55  */
56 
57 
58 
59 /* locally defined diving heuristic data */
60 struct GCG_DivingData
61 {
62  SCIP_SOL* rootsol; /**< relaxation solution at the root node */
63  SCIP_Bool firstrun; /**< is the heuristic running for the first time? */
64 };
65 
66 
67 /*
68  * Local methods
69  */
70 
71 /** get relaxation solution of root node (in original variables) */
72 static
73 SCIP_RETCODE getRootRelaxSol(
74  SCIP* scip, /**< SCIP data structure */
75  SCIP_SOL** rootsol /**< pointer to store root relaxation solution */
76  )
77 {
78  SCIP* masterprob;
79  SCIP_SOL* masterrootsol;
80  SCIP_VAR** mastervars;
81  int nmastervars;
82  int i;
83 
84  /* get master problem */
85  masterprob = GCGgetMasterprob(scip);
86  assert(masterprob != NULL);
87 
88  /* allocate memory for master root LP solution */
89  SCIP_CALL( SCIPcreateSol(masterprob, &masterrootsol, NULL) );
90 
91  /* get master variable information */
92  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
93  assert(mastervars != NULL);
94  assert(nmastervars >= 0);
95 
96  /* store root LP values in working master solution */
97  for( i = 0; i < nmastervars; i++ )
98  SCIP_CALL( SCIPsetSolVal(masterprob, masterrootsol, mastervars[i], SCIPvarGetRootSol(mastervars[i])) );
99 
100  /* calculate original root LP solution */
101  SCIP_CALL( GCGtransformMastersolToOrigsol(scip, masterrootsol, rootsol) );
102 
103  /* free memory */
104  SCIP_CALL( SCIPfreeSol(masterprob, &masterrootsol) );
105 
106  return SCIP_OKAY;
107 }
108 
109 
110 /*
111  * Callback methods of primal heuristic
112  */
113 
114 /** destructor of diving heuristic to free user data (called when GCG is exiting) */
115 static
116 GCG_DECL_DIVINGFREE(heurFreeGcglinesdiving) /*lint --e{715}*/
117 { /*lint --e{715}*/
118  GCG_DIVINGDATA* divingdata;
119 
120  assert(heur != NULL);
121  assert(scip != NULL);
122 
123  /* free diving rule specific data */
124  divingdata = GCGheurGetDivingDataOrig(heur);
125  assert(divingdata != NULL);
126  SCIPfreeMemory(scip, &divingdata);
127  GCGheurSetDivingDataOrig(heur, NULL);
128 
129  return SCIP_OKAY;
130 }
131 
132 
133 /** initialization method of diving heuristic (called after problem was transformed) */
134 static
135 GCG_DECL_DIVINGINIT(heurInitGcglinesdiving) /*lint --e{715}*/
136 { /*lint --e{715}*/
137  GCG_DIVINGDATA* divingdata;
138 
139  assert(heur != NULL);
140 
141  /* get diving data */
142  divingdata = GCGheurGetDivingDataOrig(heur);
143  assert(divingdata != NULL);
144 
145  /* initialize data */
146  divingdata->firstrun = TRUE;
147  divingdata->rootsol = NULL;
148 
149  return SCIP_OKAY;
150 }
151 
152 
153 /** deinitialization method of diving heuristic (called before transformed problem is freed) */
154 static
155 GCG_DECL_DIVINGEXIT(heurExitGcglinesdiving) /*lint --e{715}*/
156 { /*lint --e{715}*/
157  GCG_DIVINGDATA* divingdata;
158 
159  assert(heur != NULL);
160 
161  /* get diving data */
162  divingdata = GCGheurGetDivingDataOrig(heur);
163  assert(divingdata != NULL);
164 
165  assert(divingdata->firstrun == TRUE || divingdata->rootsol != NULL);
166 
167  /* free root relaxation solution */
168  if( divingdata->rootsol != NULL )
169  SCIP_CALL( SCIPfreeSol(scip, &divingdata->rootsol) );
170 
171  return SCIP_OKAY;
172 }
173 
174 
175 /** execution initialization method of diving heuristic (called when execution of diving heuristic is about to begin) */
176 static
177 GCG_DECL_DIVINGINITEXEC(heurInitexecGcglinesdiving) /*lint --e{715}*/
178 { /*lint --e{715}*/
179  GCG_DIVINGDATA* divingdata;
180 
181  assert(heur != NULL);
182 
183  /* get diving data */
184  divingdata = GCGheurGetDivingDataOrig(heur);
185  assert(divingdata != NULL);
186 
187  /* if the heuristic is running for the first time, the root relaxation solution needs to be stored */
188  if( divingdata->firstrun )
189  {
190  assert(divingdata->rootsol == NULL);
191  SCIP_CALL( getRootRelaxSol(scip, &divingdata->rootsol) );
192  assert(divingdata->rootsol != NULL);
193  divingdata->firstrun = FALSE;
194  }
195 
196  return SCIP_OKAY;
197 }
198 
199 
200 /** variable selection method of diving heuristic;
201  * finds best candidate variable w.r.t. the root LP solution:
202  * - in the projected space of fractional variables, extend the line segment connecting the root solution and
203  * the current LP solution up to the point, where one of the fractional variables becomes integral
204  * - round this variable to the integral value
205  */
206 static
207 GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcglinesdiving) /*lint --e{715}*/
208 { /*lint --e{715}*/
209  GCG_DIVINGDATA* divingdata;
210  SCIP_VAR** lpcands;
211  SCIP_Real* lpcandssol;
212  int nlpcands;
213  SCIP_Real bestdistquot;
214  int c;
215 
216  /* check preconditions */
217  assert(scip != NULL);
218  assert(heur != NULL);
219  assert(bestcand != NULL);
220  assert(bestcandmayround != NULL);
221  assert(bestcandroundup != NULL);
222 
223  /* get diving data */
224  divingdata = GCGheurGetDivingDataOrig(heur);
225  assert(divingdata != NULL);
226  assert(divingdata->rootsol != NULL);
227 
228  /* get fractional variables that should be integral */
229  SCIP_CALL( SCIPgetExternBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL, NULL, NULL) );
230  assert(lpcands != NULL);
231  assert(lpcandssol != NULL);
232 
233  *bestcandmayround = TRUE;
234  bestdistquot = SCIPinfinity(scip);
235 
236  /* get best candidate */
237  for( c = 0; c < nlpcands; ++c )
238  {
239  SCIP_VAR* var;
240  SCIP_Bool roundup;
241  SCIP_Real distquot;
242  SCIP_Real solval;
243  SCIP_Real rootsolval;
244 
245  int i;
246 
247  var = lpcands[c];
248 
249  /* if the variable is on the tabu list, do not choose it */
250  for( i = 0; i < tabulistsize; ++i )
251  if( tabulist[i] == var )
252  break;
253  if( i < tabulistsize )
254  continue;
255 
256  solval = lpcandssol[c];
257  rootsolval = SCIPgetSolVal(scip, divingdata->rootsol, var);
258 
259  /* calculate distance to integral value divided by distance to root solution */
260  if( SCIPisLT(scip, solval, rootsolval) )
261  {
262  roundup = FALSE;
263  distquot = (solval - SCIPfeasFloor(scip, solval)) / (rootsolval - solval);
264 
265  /* avoid roundable candidates */
266  if( SCIPvarMayRoundDown(var) )
267  distquot *= 1000.0;
268  }
269  else if( SCIPisGT(scip, solval, rootsolval) )
270  {
271  roundup = TRUE;
272  distquot = (SCIPfeasCeil(scip, solval) - solval) / (solval - rootsolval);
273 
274  /* avoid roundable candidates */
275  if( SCIPvarMayRoundUp(var) )
276  distquot *= 1000.0;
277  }
278  else
279  {
280  roundup = FALSE;
281  distquot = SCIPinfinity(scip);
282  }
283 
284  /* check, if candidate is new best candidate */
285  if( distquot < bestdistquot )
286  {
287  *bestcand = var;
288  *bestcandmayround = SCIPvarMayRoundDown(var) || SCIPvarMayRoundUp(var);
289  *bestcandroundup = roundup;
290  bestdistquot = distquot;
291  }
292  }
293 
294  return SCIP_OKAY;
295 }
296 
297 
298 /*
299  * primal heuristic specific interface methods
300  */
301 
302 /** creates the gcglinesdiving heuristic and includes it in GCG */
304  SCIP* scip /**< SCIP data structure */
305  )
306 {
307  SCIP_HEUR* heur;
308  GCG_DIVINGDATA* divingdata;
309 
310  /* create gcglinesdiving primal heuristic data */
311  SCIP_CALL( SCIPallocMemory(scip, &divingdata) );
312 
313  /* include diving heuristic */
314  SCIP_CALL( GCGincludeDivingHeurOrig(scip, &heur,
316  HEUR_MAXDEPTH, heurFreeGcglinesdiving, heurInitGcglinesdiving, heurExitGcglinesdiving, NULL, NULL,
317  heurInitexecGcglinesdiving, NULL, heurSelectVarGcglinesdiving, divingdata) );
318 
319  assert(heur != NULL);
320 
321  return SCIP_OKAY;
322 }
GCG_DIVINGDATA * GCGheurGetDivingDataOrig(SCIP_HEUR *heur)
GCG interface methods.
static GCG_DECL_DIVINGFREE(heurFreeGcglinesdiving)
static GCG_DECL_DIVINGINITEXEC(heurInitexecGcglinesdiving)
static GCG_DECL_DIVINGSELECTVAR(heurSelectVarGcglinesdiving)
SCIP_RETCODE GCGincludeHeurGcglinesdiving(SCIP *scip)
#define HEUR_NAME
primal heuristic interface for LP diving heuristics on the original variables
#define HEUR_DISPCHAR
#define HEUR_DESC
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
#define HEUR_PRIORITY
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_RETCODE GCGtransformMastersolToOrigsol(SCIP *scip, SCIP_SOL *mastersol, SCIP_SOL **origsol)
Definition: misc.c:120
LP diving heuristic that fixes variables with a large difference to their root solution.
void GCGheurSetDivingDataOrig(SCIP_HEUR *heur, GCG_DIVINGDATA *divingdata)
#define HEUR_FREQOFS
static GCG_DECL_DIVINGEXIT(heurExitGcglinesdiving)
#define HEUR_MAXDEPTH
static SCIP_RETCODE getRootRelaxSol(SCIP *scip, SCIP_SOL **rootsol)
#define HEUR_FREQ
static GCG_DECL_DIVINGINIT(heurInitGcglinesdiving)