Scippy

SCIP

Solving Constraint Integer Programs

heur_bound.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_bound.c
17  * @brief heuristic which fixes all integer variables to a bound (lower/upper) and solves the remaining LP
18  * @author Gerald Gamrath
19  *
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/scip.h"
28 #include "scip/heur_bound.h"
29 
30 #ifdef SCIP_STATISTIC
31 #include "scip/clock.h"
32 #endif
33 
34 #define HEUR_NAME "bound"
35 #define HEUR_DESC "heuristic which fixes all integer variables to a bound and solves the remaining LP"
36 #define HEUR_DISPCHAR 'H'
37 #define HEUR_PRIORITY -1107000
38 #define HEUR_FREQ -1
39 #define HEUR_FREQOFS 0
40 #define HEUR_MAXDEPTH -1
41 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
42 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
43 
44 #define DEFAULT_ONLYWITHOUTSOL TRUE /**< Should heuristic only be executed if no primal solution was found, yet? */
45 #define DEFAULT_MAXPROPROUNDS 0 /* maximum number of propagation rounds during probing */
46 #define DEFAULT_BOUND 'l' /**< to which bound should integer variables be fixed? */
47 
48 
49 /*
50  * Data structures
51  */
52 
53 /** primal heuristic data */
54 struct SCIP_HeurData
55 {
56  SCIP_Bool onlywithoutsol; /**< Should heuristic only be executed if no primal solution was found, yet? */
57  int maxproprounds; /**< maximum number of propagation rounds during probing */
58  char bound; /**< to which bound should integer variables be fixed? */
59 };
60 
61 /*
62  * Local methods
63  */
64 
65 /** main procedure of the bound heuristic */
66 static
68  SCIP* scip, /**< original SCIP data structure */
69  SCIP_HEUR* heur, /**< heuristic */
70  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
71  SCIP_Bool lower, /**< should integer variables be fixed to their lower bound? */
72  SCIP_RESULT* result /**< pointer to store the result */
73  )
74 {
75  SCIP_VAR** vars;
76  SCIP_VAR* var;
77  SCIP_Bool infeasible = FALSE;
78  int maxproprounds;
79  int nbinvars;
80  int nintvars;
81  int nvars;
82  int v;
83 
84  /* get variable data of original problem */
85  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
86 
87  maxproprounds = heurdata->maxproprounds;
88  if( maxproprounds == -2 )
89  maxproprounds = 0;
90 
91 
92  /* only look at binary and integer variables */
93  nvars = nbinvars + nintvars;
94 
95  /* stop if we would have infinite fixings */
96  if( lower )
97  {
98  for( v = 0; v < nvars; ++v )
99  {
100  if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(vars[v])) )
101  return SCIP_OKAY;
102  }
103  }
104  else
105  {
106  for( v = 0; v < nvars; ++v )
107  {
108  if( SCIPisInfinity(scip, SCIPvarGetUbLocal(vars[v])) )
109  return SCIP_OKAY;
110  }
111  }
112 
113  /* start probing */
114  SCIP_CALL( SCIPstartProbing(scip) );
115 
116  for( v = 0; v < nvars; ++v )
117  {
118  var = vars[v];
119 
120  assert(SCIPvarGetType(var) < SCIP_VARTYPE_IMPLINT);
121 
122  /* skip variables which are already fixed */
123  if( SCIPvarGetLbLocal(var) + 0.5 > SCIPvarGetUbLocal(var) )
124  continue;
125 
126  /* fix variable to lower bound */
127  if( lower )
128  {
129  SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetLbLocal(var)) );
130  SCIPdebugMsg(scip, "fixing %d: variable <%s> to lower bound <%g> (%d pseudo cands)\n",
132  }
133  /* fix variable to upper bound */
134  else
135  {
136  SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) );
137  SCIPdebugMsg(scip, "fixing %d: variable <%s> to upper bound <%g> (%d pseudo cands)\n",
139  }
140 
141  /* propagate fixings */
142  if( heurdata->maxproprounds != 0 )
143  {
144  SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &infeasible, NULL) );
145  }
146 
147  /* try to repair probing */
148  if( infeasible )
149  {
150 #if 0
152 
153  /* fix the last variable, which was fixed the reverse bound */
154  SCIP_CALL( SCIPfixVarProbing(scip, var, SCIPvarGetUbLocal(var)) );
155 
156  /* propagate fixings */
157  SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, &infeasible, NULL) );
158 
159  SCIPdebugMsg(scip, "backtracking ended with %sfeasible problem\n", (infeasible ? "in" : ""));
160 
161  if( infeasible )
162 #endif
163  break;
164  }
165  }
166 
167  SCIPdebugMsg(scip, "probing ended with %sfeasible problem\n", infeasible ? "in" : "");
168 
169  /*************************** Probing LP Solving ***************************/
170 
171  /* solve lp only if the problem is still feasible */
172  if( !infeasible )
173  {
174  SCIP_LPSOLSTAT lpstatus;
175  SCIP_Bool lperror;
176 
177  SCIPdebugMsg(scip, "starting solving bound-heur LP at time %g, LP iterations: %" SCIP_LONGINT_FORMAT "\n",
179 
180  /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
181  * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
182  * SCIP will stop.
183  */
184 #ifdef NDEBUG
185  {
186  SCIP_Bool retstat;
187  retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL);
188  if( retstat != SCIP_OKAY )
189  {
190  SCIPwarningMessage(scip, "Error while solving LP in bound heuristic; LP solve terminated with code <%d>\n",
191  retstat);
192  }
193  }
194 #else
195  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) );
196 #endif
197  SCIPdebugMsg(scip, "ending solving bound-heur LP at time %g\n", SCIPgetSolvingTime(scip));
198 
199  lpstatus = SCIPgetLPSolstat(scip);
200 
201  SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
202  SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus);
203 
204  /* check if this is a feasible solution */
205  if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror )
206  {
207  SCIP_SOL* newsol;
208  SCIP_Bool stored;
209  SCIP_Bool success;
210 
211  /* create temporary solution */
212  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
213 
214  /* copy the current LP solution to the working solution */
215  SCIP_CALL( SCIPlinkLPSol(scip, newsol) );
216 
217  SCIP_CALL( SCIProundSol(scip, newsol, &success) );
218 
219  if( success )
220  {
221  SCIPdebugMsg(scip, "bound heuristic found roundable primal solution: obj=%g\n",
222  SCIPgetSolOrigObj(scip, newsol));
223 
224  /* check solution for feasibility, and add it to solution store if possible.
225  * Neither integrality nor feasibility of LP rows have to be checked, because they
226  * are guaranteed by the heuristic at this stage.
227  */
228 #ifdef SCIP_DEBUG
229  SCIP_CALL( SCIPtrySol(scip, newsol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) );
230 #else
231  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) );
232 #endif
233 
234  if( stored )
235  {
236  SCIPdebugMsg(scip, "found feasible solution:\n");
237  *result = SCIP_FOUNDSOL;
238  }
239  }
240 
241  /* free solution */
242  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
243  }
244  }
245 
246  /* exit probing mode */
247  SCIP_CALL( SCIPendProbing(scip) );
248 
249  return SCIP_OKAY;
250 }
251 
252 
253 /*
254  * Callback methods of primal heuristic
255  */
256 
257 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
258 static
259 SCIP_DECL_HEURCOPY(heurCopyBound)
260 { /*lint --e{715}*/
261  assert(scip != NULL);
262  assert(heur != NULL);
263  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
264 
265  /* call inclusion method of heuristic */
267 
268  return SCIP_OKAY;
269 }
270 
271 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
272 static
273 SCIP_DECL_HEURFREE(heurFreeBound)
274 { /*lint --e{715}*/
275  SCIP_HEURDATA* heurdata;
276 
277  /* free heuristic data */
278  heurdata = SCIPheurGetData(heur);
279 
280  SCIPfreeBlockMemory(scip, &heurdata);
281  SCIPheurSetData(heur, NULL);
282 
283  return SCIP_OKAY;
284 }
285 
286 /** execution method of primal heuristic */
287 static
288 SCIP_DECL_HEUREXEC(heurExecBound)
289 { /*lint --e{715}*/
290  SCIP_HEURDATA* heurdata;
291 
292  assert(heur != NULL);
293  assert(scip != NULL);
294  assert(result != NULL);
295 
296  *result = SCIP_DIDNOTRUN;
297 
298  if( SCIPgetNPseudoBranchCands(scip) == 0 )
299  return SCIP_OKAY;
300 
301  if( !SCIPhasCurrentNodeLP(scip) )
302  return SCIP_OKAY;
303 
304  heurdata = SCIPheurGetData(heur);
305  assert(heurdata != NULL);
306 
307  *result = SCIP_DIDNOTFIND;
308 
309  if( SCIPisStopped(scip) )
310  return SCIP_OKAY;
311 
312  /* stop execution method if there is already a primal feasible solution at hand */
313  if( SCIPgetBestSol(scip) != NULL && heurdata->onlywithoutsol )
314  return SCIP_OKAY;
315 
316  SCIPdebugMsg(scip, "apply bound heuristic at node %lld\n",
318 
319  if( !SCIPisLPConstructed(scip) )
320  {
321  SCIP_Bool cutoff;
322 
323  SCIP_CALL( SCIPconstructLP(scip, &cutoff) );
324 
325  /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
326  if( cutoff )
327  {
329  return SCIP_OKAY;
330  }
331 
333  }
334 
335  if( heurdata->bound == 'l' || heurdata->bound == 'b' )
336  {
337  SCIP_CALL(applyBoundHeur(scip, heur, heurdata, TRUE, result) );
338  }
339  if( heurdata->bound == 'u' || heurdata->bound == 'b' )
340  {
341  SCIP_CALL(applyBoundHeur(scip, heur, heurdata, FALSE, result) );
342  }
343 
344  return SCIP_OKAY;
345 }
346 
347 /*
348  * primal heuristic specific interface methods
349  */
350 
351 /** creates the bound primal heuristic and includes it in SCIP */
353  SCIP* scip /**< SCIP data structure */
354  )
355 {
356  SCIP_HEURDATA* heurdata;
357  SCIP_HEUR* heur;
358 
359  /* create bound primal heuristic data */
360  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
361 
362  /* include primal heuristic */
363  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
365  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecBound, heurdata) );
366 
367  assert(heur != NULL);
368 
369  /* set non-NULL pointers to callback methods */
370  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyBound) );
371  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeBound) );
372 
373  /* add bound heuristic parameters */
374 
375  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlywithoutsol",
376  "Should heuristic only be executed if no primal solution was found, yet?",
377  &heurdata->onlywithoutsol, TRUE, DEFAULT_ONLYWITHOUTSOL, NULL, NULL) );
378 
379  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds",
380  "maximum number of propagation rounds during probing (-1 infinity, -2 parameter settings)",
381  &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) );
382 
383  SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/bound",
384  "to which bound should integer variables be fixed? ('l'ower, 'u'pper, or 'b'oth)",
385  &heurdata->bound, FALSE, DEFAULT_BOUND, "lub", NULL, NULL) );
386 
387  return SCIP_OKAY;
388 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:37672
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:45137
#define HEUR_PRIORITY
Definition: heur_bound.c:37
static SCIP_DECL_HEURCOPY(heurCopyBound)
Definition: heur_bound.c:259
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:40453
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip.c:35152
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip.c:41382
static SCIP_DECL_HEUREXEC(heurExecBound)
Definition: heur_bound.c:288
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip.c:35125
#define DEFAULT_MAXPROPROUNDS
Definition: heur_bound.c:45
#define HEUR_DESC
Definition: heur_bound.c:35
internal methods for clocks and timing issues
static long bound
#define HEUR_FREQ
Definition: heur_bound.c:38
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip.c:36492
SCIP_RETCODE SCIPincludeHeurBound(SCIP *scip)
Definition: heur_bound.c:352
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11505
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:40796
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:7999
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip.c:28810
#define HEUR_FREQOFS
Definition: heur_bound.c:39
enum SCIP_LPSolStat SCIP_LPSOLSTAT
Definition: type_lp.h:42
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1102
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define SCIPdebugMsg
Definition: scip.h:451
#define HEUR_DISPCHAR
Definition: heur_bound.c:36
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4202
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
Definition: scip.c:28787
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7143
static SCIP_RETCODE applyBoundHeur(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_Bool lower, SCIP_RESULT *result)
Definition: heur_bound.c:67
#define DEFAULT_BOUND
Definition: heur_bound.c:46
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1181
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:8060
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:35477
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip.c:35337
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:35187
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
#define NULL
Definition: lpi_spx1.cpp:137
#define HEUR_MAXDEPTH
Definition: heur_bound.c:40
#define SCIP_CALL(x)
Definition: def.h:306
static SCIP_DECL_HEURFREE(heurFreeBound)
Definition: heur_bound.c:273
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip.c:35713
#define DEFAULT_ONLYWITHOUTSOL
Definition: heur_bound.c:44
#define HEUR_USESSUBSCIP
Definition: heur_bound.c:42
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28769
#define HEUR_NAME
Definition: heur_bound.c:34
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip.c:39073
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37631
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38090
SCIP_RETCODE SCIPflushLP(SCIP *scip)
Definition: scip.c:28834
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:39749
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:38931
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4286
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define HEUR_TIMING
Definition: heur_bound.c:41
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:8044
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:35055
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1092
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4176
heuristic which fixes all integer variables to a bound (lower/upper) and solves the remaining LP ...
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip.c:37005