Scippy

SCIP

Solving Constraint Integer Programs

heur_fixandinfer.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-2016 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_fixandinfer.c
17  * @brief fix-and-infer primal heuristic
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/heur_fixandinfer.h"
27 
28 
29 #define HEUR_NAME "fixandinfer"
30 #define HEUR_DESC "iteratively fixes variables and propagates inferences"
31 #define HEUR_DISPCHAR 'I'
32 #define HEUR_PRIORITY -500000
33 #define HEUR_FREQ -1 /* at the moment, the heuristic seems to be useless */
34 #define HEUR_FREQOFS 0
35 #define HEUR_MAXDEPTH -1
36 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
37 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
38 
39 #define MAXDIVEDEPTH 100
40 
41 
42 /*
43  * Default parameter settings
44  */
45 
46 #define DEFAULT_PROPROUNDS 0 /**< maximal number of propagation rounds in probing subproblems */
47 #define DEFAULT_MINFIXINGS 100 /**< minimal number of fixings to apply before dive may be aborted */
48 
49 
50 /*
51  * Data structures
52  */
53 
54 /** primal heuristic data */
55 struct SCIP_HeurData
56 {
57  int proprounds; /**< maximal number of propagation rounds in probing subproblems */
58  int minfixings; /**< minimal number of fixings to apply before dive may be aborted */
59 };
60 
61 
62 /*
63  * Local methods
64  */
65 
66 /** selects a variable and fixes it to its current pseudo solution value */
67 static
69  SCIP* scip, /**< SCIP data structure */
70  SCIP_VAR** pseudocands, /**< array of unfixed variables */
71  int npseudocands, /**< number of unfixed variables */
72  SCIP_Real large /**< large value to be used instead of infinity */
73  )
74 {
75  SCIP_VAR* var;
76  SCIP_Real bestscore;
77  SCIP_Real score;
78  SCIP_Real solval;
79  int bestcand;
80  int ncands;
81  int c;
82 
83  assert(pseudocands != NULL);
84  assert(npseudocands > 0);
85 
86  /* if existing, choose one of the highest priority binary variables; if no high priority binary variables
87  * exist, choose a variable among all unfixed integral variables
88  */
89  ncands = SCIPgetNPrioPseudoBranchBins(scip);
90  if( ncands == 0 )
91  ncands = npseudocands;
92 
93  /* select variable to tighten the domain for */
94  bestscore = -SCIPinfinity(scip);
95  bestcand = -1;
96  for( c = 0; c < ncands; ++c )
97  {
98  score = SCIPgetVarAvgInferenceScore(scip, pseudocands[c]);
99  if( score > bestscore )
100  {
101  bestscore = score;
102  bestcand = c;
103  }
104  }
105  assert(bestcand != -1);
106 
107  /* fix variable to its current pseudo solution value */
108  var = pseudocands[bestcand];
109  solval = SCIPgetVarSol(scip, var);
110 
111  /* adapt solution value if it is infinite */
112  if( SCIPisInfinity(scip, solval) )
113  {
114  SCIP_Real lb;
115  assert(SCIPisInfinity(scip, SCIPvarGetUbLocal(var)));
116  lb = SCIPvarGetLbLocal(var);
117 
118  /* adapt fixing value by changing it to a large value */
119  if( SCIPisInfinity(scip, -lb) )
120  solval = SCIPceil(scip, large);
121  else if( !SCIPisInfinity(scip, SCIPceil(scip, lb+large)) )
122  solval = SCIPceil(scip, lb+large);
123  }
124  else if( SCIPisInfinity(scip, -solval) )
125  {
126  SCIP_Real ub;
127  assert(SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)));
128  ub = SCIPvarGetUbLocal(var);
129 
130  /* adapt fixing value by changing it to a large negative value */
131  if( SCIPisInfinity(scip, ub) )
132  solval = SCIPfloor(scip, -large);
133  else if( !SCIPisInfinity(scip, -SCIPfloor(scip, ub-large)) )
134  solval = SCIPfloor(scip, ub-large);
135  }
136 
137  assert(SCIPisFeasIntegral(scip, solval)); /* in probing, we always have the pseudo solution */
138  SCIPdebugMessage(" -> fixed variable <%s>[%g,%g] = %g (%d candidates left)\n",
139  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), solval, npseudocands - 1);
140  SCIP_CALL( SCIPfixVarProbing(scip, var, solval) );
141 
142  return SCIP_OKAY;
143 }
144 
145 
146 /*
147  * Callback methods of primal heuristic
148  */
149 
150 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
151 static
152 SCIP_DECL_HEURCOPY(heurCopyFixandinfer)
153 { /*lint --e{715}*/
154  assert(scip != NULL);
155  assert(heur != NULL);
156  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
157 
158  /* call inclusion method of primal heuristic */
160 
161  return SCIP_OKAY;
162 }
163 
164 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
165 static
166 SCIP_DECL_HEURFREE(heurFreeFixandinfer) /*lint --e{715}*/
167 { /*lint --e{715}*/
168  SCIP_HEURDATA* heurdata;
169 
170  /* free heuristic data */
171  heurdata = SCIPheurGetData(heur);
172  assert(heurdata != NULL);
173  SCIPfreeMemory(scip, &heurdata);
174  SCIPheurSetData(heur, NULL);
175 
176  return SCIP_OKAY;
177 }
178 
179 
180 /** execution method of primal heuristic */
181 static
182 SCIP_DECL_HEUREXEC(heurExecFixandinfer)
183 { /*lint --e{715}*/
184  SCIP_HEURDATA* heurdata;
185  SCIP_VAR** cands;
186  int ncands;
187  int startncands;
188  int divedepth;
189  SCIP_Bool cutoff;
190  SCIP_Real large;
191 
192  *result = SCIP_DIDNOTRUN;
193 
194  /* do not call heuristic of node was already detected to be infeasible */
195  if( nodeinfeasible )
196  return SCIP_OKAY;
197 
198  /* we cannot run on problems with continuous variables */
199  if( SCIPgetNContVars(scip) > 0 )
200  return SCIP_OKAY;
201 
202  /* get unfixed variables */
203  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) );
204  if( ncands == 0 )
205  return SCIP_OKAY;
206 
207  /* get heuristic data */
208  heurdata = SCIPheurGetData(heur);
209  assert(heurdata != NULL);
210 
211  /* fix variables and propagate inferences as long as the problem is still feasible and there are
212  * unfixed integral variables
213  */
214  cutoff = FALSE;
215  divedepth = 0;
216  startncands = ncands;
217 
218  /* start probing */
220 
222  {
224  return SCIP_OKAY;
225  }
226 
227  SCIPdebugMessage("starting fix-and-infer heuristic with %d unfixed integral variables\n", ncands);
228 
229  *result = SCIP_DIDNOTFIND;
230 
231  /* create next probing node */
233 
234  /* determine large value to set variables to */
235  large = SCIPinfinity(scip);
236  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
237  large = 0.1 / SCIPfeastol(scip);
238 
239  while( !cutoff && ncands > 0
240  && (divedepth < heurdata->minfixings || (startncands - ncands) * 2 * MAXDIVEDEPTH >= startncands * divedepth)
241  && !SCIPisStopped(scip) )
242  {
243  divedepth++;
244 
245  /* fix next variable */
246  SCIP_CALL( fixVariable(scip, cands, ncands, large) );
247 
248  /* propagate the fixing */
249  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->proprounds, &cutoff, NULL) );
250 
251  /* get remaining unfixed variables */
252  if( !cutoff )
253  {
254  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) );
255  }
256  }
257 
258  /* check, if we are still feasible */
259  if( cutoff )
260  {
261  SCIPdebugMessage("propagation detected a cutoff\n");
262  }
263  else if( ncands == 0 )
264  {
265  SCIP_Bool success;
266 
267  success = FALSE;
268 
269  /* try to add solution to SCIP */
270  SCIP_CALL( SCIPtryCurrentSol(scip, heur, FALSE, FALSE, TRUE, &success) );
271 
272  if( success )
273  {
274  SCIPdebugMessage("found primal feasible solution\n");
275  *result = SCIP_FOUNDSOL;
276  }
277  else
278  {
279  SCIPdebugMessage("primal solution was rejected\n");
280  }
281  }
282  else
283  {
284  SCIPdebugMessage("probing was aborted (probing depth: %d, fixed: %d/%d)", divedepth, startncands - ncands, startncands);
285  }
286 
287  /* end probing */
289 
290  return SCIP_OKAY;
291 }
292 
293 
294 /*
295  * primal heuristic specific interface methods
296  */
297 
298 /** creates the fix-and-infer primal heuristic and includes it in SCIP */
300  SCIP* scip /**< SCIP data structure */
301  )
302 {
303  SCIP_HEURDATA* heurdata;
304  SCIP_HEUR* heur;
305 
306  /* create Fixandinfer primal heuristic data */
307  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
308 
309  /* include primal heuristic */
310  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
312  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFixandinfer, heurdata) );
313 
314  assert(heur != NULL);
315 
316  /* set non-NULL pointers to callback methods */
317  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyFixandinfer) );
318  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeFixandinfer) );
319 
320  /* fixandinfer heuristic parameters */
322  "heuristics/fixandinfer/proprounds",
323  "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)",
324  &heurdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) );
326  "heuristics/fixandinfer/minfixings",
327  "minimal number of fixings to apply before dive may be aborted",
328  &heurdata->minfixings, TRUE, DEFAULT_MINFIXINGS, 0, INT_MAX, NULL, NULL) );
329 
330  return SCIP_OKAY;
331 }
#define SCIPallocMemory(scip, ptr)
Definition: scip.h:20526
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16443
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:41648
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1147
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip.c:7297
#define HEUR_FREQ
SCIP_RETCODE SCIPincludeHeurFixandinfer(SCIP *scip)
#define HEUR_DISPCHAR
#define NULL
Definition: lpi_spx.cpp:130
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17113
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1125
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, unsigned int timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip.c:7252
static SCIP_RETCODE fixVariable(SCIP *scip, SCIP_VAR **pseudocands, int npseudocands, SCIP_Real large)
#define HEUR_DESC
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip.c:32552
#define FALSE
Definition: def.h:56
static SCIP_DECL_HEUREXEC(heurExecFixandinfer)
static SCIP_DECL_HEURFREE(heurFreeFixandinfer)
#define TRUE
Definition: def.h:55
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_CALL(x)
Definition: def.h:266
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:42008
#define SCIPdebugMessage
Definition: pub_message.h:77
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:10878
static SCIP_DECL_HEURCOPY(heurCopyFixandinfer)
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:3573
#define DEFAULT_PROPROUNDS
#define SCIPfreeMemory(scip, ptr)
Definition: scip.h:20542
SCIP_RETCODE SCIPtryCurrentSol(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool printreason, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:36380
#define HEUR_MAXDEPTH
#define MAXDIVEDEPTH
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:41758
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip.c:33464
#define HEUR_TIMING
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:41637
int SCIPgetDepthLimit(SCIP *scip)
Definition: scip.c:38190
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1068
#define DEFAULT_MINFIXINGS
int SCIPgetNPrioPseudoBranchBins(SCIP *scip)
Definition: scip.c:33526
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17123
#define SCIP_Bool
Definition: def.h:53
fix-and-infer primal heuristic
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip.c:32415
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip.c:32153
#define HEUR_PRIORITY
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip.c:32285
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:38140
#define HEUR_USESSUBSCIP
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:41770
#define HEUR_NAME
#define HEUR_FREQOFS
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip.c:7313
#define SCIP_Real
Definition: def.h:127
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip.c:32190
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:41146
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:17628
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1058
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:23877