Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_gcgsimplerounding.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_gcgsimplerounding.c
29  * @brief simple and fast LP rounding heuristic
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_gcgsimplerounding.h"
40 #include "gcg.h"
41 
42 
43 #define HEUR_NAME "gcgsimplerounding"
44 #define HEUR_DESC "simple and fast LP rounding heuristic on original variables"
45 #define HEUR_DISPCHAR 'r'
46 #define HEUR_PRIORITY 0
47 #define HEUR_FREQ 1
48 #define HEUR_FREQOFS 0
49 #define HEUR_MAXDEPTH -1
50 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
51 #define HEUR_USESSUBSCIP FALSE
52 
53 
54 /* locally defined heuristic data */
55 struct SCIP_HeurData
56 {
57  SCIP_SOL* sol; /**< working solution */
58  SCIP_Longint lastlp; /**< last LP number where the heuristic was applied */
59  int nroundablevars; /**< number of variables that can be rounded (-1 if not yet calculated) */
60 };
61 
62 
63 
64 
65 /*
66  * Callback methods
67  */
68 
69 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
70 #define heurCopyGcgsimplerounding NULL
71 
72 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
73 #define heurFreeGcgsimplerounding NULL
74 
75 
76 /** initialization method of primal heuristic (called after problem was transformed) */
77 static
78 SCIP_DECL_HEURINIT(heurInitGcgsimplerounding) /*lint --e{715}*/
79 { /*lint --e{715}*/
80  SCIP_HEURDATA* heurdata;
81 
82  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
83  assert(SCIPheurGetData(heur) == NULL);
84 
85  /* create heuristic data */
86  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
87  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
88  heurdata->lastlp = -1;
89  heurdata->nroundablevars = -1;
90  SCIPheurSetData(heur, heurdata);
91 
92  return SCIP_OKAY;
93 }
94 
95 
96 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
97 static
98 SCIP_DECL_HEUREXIT(heurExitGcgsimplerounding) /*lint --e{715}*/
99 { /*lint --e{715}*/
100  SCIP_HEURDATA* heurdata;
101 
102  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
103 
104  /* free heuristic data */
105  heurdata = SCIPheurGetData(heur);
106  assert(heurdata != NULL);
107  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
108  SCIPfreeMemory(scip, &heurdata);
109  SCIPheurSetData(heur, NULL);
110 
111  return SCIP_OKAY;
112 }
113 
114 
115 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
116 static
117 SCIP_DECL_HEURINITSOL(heurInitsolGcgsimplerounding)
118 {
119  SCIP_HEURDATA* heurdata;
120 
121  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
122 
123  heurdata = SCIPheurGetData(heur);
124  assert(heurdata != NULL);
125  heurdata->lastlp = -1;
126 
127  return SCIP_OKAY;
128 }
129 
130 
131 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
132 #define heurExitsolGcgsimplerounding NULL
133 
134 
135 /** execution method of primal heuristic */
136 static
137 SCIP_DECL_HEUREXEC(heurExecGcgsimplerounding) /*lint --e{715}*/
138 { /*lint --e{715}*/
139  SCIP* masterprob;
140  SCIP_HEURDATA* heurdata;
141  SCIP_SOL* sol;
142  SCIP_VAR** lpcands;
143  SCIP_Real* lpcandssol;
144  SCIP_Longint nlps;
145  int nlpcands;
146  int c;
147 
148  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
149  assert(result != NULL);
150 
151  /* get master problem */
152  masterprob = GCGgetMasterprob(scip);
153  assert(masterprob != NULL);
154 
155  *result = SCIP_DIDNOTRUN;
156 
157  /* do not execute the heuristic on invalid relaxation solutions
158  * (which is the case if the node has been cut off)
159  */
160  if( !SCIPisRelaxSolValid(scip) )
161  {
162  SCIPdebugMessage("skipping GCG simple rounding: invalid relaxation solution\n");
163  return SCIP_OKAY;
164  }
165 
166  /* only call heuristic, if an optimal LP solution is at hand */
167  if( SCIPgetStage(masterprob) > SCIP_STAGE_SOLVING || SCIPgetLPSolstat(masterprob) != SCIP_LPSOLSTAT_OPTIMAL )
168  return SCIP_OKAY;
169 
170  /* get heuristic data */
171  heurdata = SCIPheurGetData(heur);
172  assert(heurdata != NULL);
173 
174  /* on our first call, calculate the number of roundable variables */
175  if( heurdata->nroundablevars == -1 )
176  {
177  SCIP_VAR** vars;
178  int nvars;
179  int nroundablevars;
180  int i;
181 
182  vars = SCIPgetVars(scip);
183  nvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
184  nroundablevars = 0;
185  for( i = 0; i < nvars; ++i )
186  {
187  if( SCIPvarMayRoundDown(vars[i]) || SCIPvarMayRoundUp(vars[i]) )
188  nroundablevars++;
189  }
190  heurdata->nroundablevars = nroundablevars;
191  }
192 
193  /* don't call heuristic if there are no roundable variables */
194  if( heurdata->nroundablevars == 0 )
195  return SCIP_OKAY;
196 
197  /* don't call heuristic, if we have already processed the current LP solution */
198  nlps = SCIPgetNLPs(masterprob);
199  if( nlps == heurdata->lastlp )
200  return SCIP_OKAY;
201  heurdata->lastlp = nlps;
202 
203  /* get fractional variables, that should be integral */
204  SCIP_CALL( SCIPgetExternBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, NULL, NULL, NULL) );
205 
206  /* only call heuristic, if LP solution is fractional */
207  if( nlpcands == 0 )
208  return SCIP_OKAY;
209 
210  /* don't call heuristic, if there are more fractional variables than roundable ones */
211  if( nlpcands > heurdata->nroundablevars )
212  return SCIP_OKAY;
213 
214  *result = SCIP_DIDNOTFIND;
215 
216  SCIPdebugMessage("executing GCG simple rounding heuristic: %d fractionals\n", nlpcands);
217 
218  /* get the working solution from heuristic's local data */
219  sol = heurdata->sol;
220  assert(sol != NULL);
221 
222  /* copy the current LP solution to the working solution */
223  SCIP_CALL( SCIPlinkRelaxSol(scip, sol) );
224 
225  /* round all roundable fractional columns in the corresponding direction as long as no unroundable column was found */
226  for( c = 0; c < nlpcands; ++c )
227  {
228  SCIP_VAR* var;
229  SCIP_Real oldsolval;
230  SCIP_Real newsolval;
231  SCIP_Bool mayrounddown;
232  SCIP_Bool mayroundup;
233 
234  oldsolval = lpcandssol[c];
235  assert(!SCIPisFeasIntegral(scip, oldsolval));
236  var = lpcands[c];
237  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
238  mayrounddown = SCIPvarMayRoundDown(var);
239  mayroundup = SCIPvarMayRoundUp(var);
240  SCIPdebugMessage("GCG simple rounding heuristic: var <%s>, val=%g, rounddown=%u, roundup=%u\n",
241  SCIPvarGetName(var), oldsolval, mayrounddown, mayroundup);
242 
243  /* choose rounding direction */
244  if( mayrounddown && mayroundup )
245  {
246  /* we can round in both directions: round in objective function direction */
247  if( SCIPvarGetObj(var) >= 0.0 )
248  newsolval = SCIPfeasFloor(scip, oldsolval);
249  else
250  newsolval = SCIPfeasCeil(scip, oldsolval);
251  }
252  else if( mayrounddown )
253  newsolval = SCIPfeasFloor(scip, oldsolval);
254  else if( mayroundup )
255  newsolval = SCIPfeasCeil(scip, oldsolval);
256  else
257  break;
258 
259  /* store new solution value */
260  SCIP_CALL( SCIPsetSolVal(scip, sol, var, newsolval) );
261  }
262 
263  /* check, if rounding was successful */
264  if( c == nlpcands )
265  {
266  SCIP_Bool stored;
267 
268  /* check solution for feasibility, and add it to solution store if possible
269  * neither integrality nor feasibility of LP rows has to be checked, because all fractional
270  * variables were already moved in feasible direction to the next integer
271  */
272  SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, FALSE, FALSE, FALSE, &stored) );
273 
274  if( stored )
275  {
276 #ifdef SCIP_DEBUG
277  SCIPdebugMessage("found feasible rounded solution:\n");
278  SCIPprintSol(scip, sol, NULL, FALSE);
279 #endif
280  *result = SCIP_FOUNDSOL;
281  }
282  }
283 
284  return SCIP_OKAY;
285 }
286 
287 
288 
289 
290 /*
291  * heuristic specific interface methods
292  */
293 
294 /** creates the GCG simple rounding heuristic and includes it in SCIP */
296  SCIP* scip /**< SCIP data structure */
297  )
298 {
299  /* include heuristic */
300  SCIP_CALL( SCIPincludeHeur(scip, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
302  heurCopyGcgsimplerounding, heurFreeGcgsimplerounding, heurInitGcgsimplerounding, heurExitGcgsimplerounding,
303  heurInitsolGcgsimplerounding, heurExitsolGcgsimplerounding, heurExecGcgsimplerounding,
304  NULL) );
305 
306  return SCIP_OKAY;
307 }
308 
#define HEUR_TIMING
GCG interface methods.
static SCIP_DECL_HEUREXEC(heurExecGcgsimplerounding)
#define HEUR_MAXDEPTH
#define HEUR_DISPCHAR
SCIP_Longint lastlp
static SCIP_DECL_HEUREXIT(heurExitGcgsimplerounding)
SCIP_SOL * sol
#define HEUR_FREQOFS
SCIP_RETCODE SCIPincludeHeurGcgsimplerounding(SCIP *scip)
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
#define HEUR_DESC
static SCIP_DECL_HEURINIT(heurInitGcgsimplerounding)
#define heurExitsolGcgsimplerounding
#define HEUR_USESSUBSCIP
#define HEUR_PRIORITY
simple and fast LP rounding heuristic
#define HEUR_FREQ
#define HEUR_NAME
static SCIP_DECL_HEURINITSOL(heurInitsolGcgsimplerounding)
#define heurFreeGcgsimplerounding
#define heurCopyGcgsimplerounding