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-2019 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 visit 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 "scip/heur_fixandinfer.h"
24 #include "scip/pub_heur.h"
25 #include "scip/pub_message.h"
26 #include "scip/pub_var.h"
27 #include "scip/scip_branch.h"
28 #include "scip/scip_general.h"
29 #include "scip/scip_heur.h"
30 #include "scip/scip_mem.h"
31 #include "scip/scip_message.h"
32 #include "scip/scip_numerics.h"
33 #include "scip/scip_param.h"
34 #include "scip/scip_prob.h"
35 #include "scip/scip_probing.h"
36 #include "scip/scip_sol.h"
37 #include "scip/scip_tree.h"
38 #include "scip/scip_var.h"
39 #include <string.h>
40 
41 #define HEUR_NAME "fixandinfer"
42 #define HEUR_DESC "iteratively fixes variables and propagates inferences"
43 #define HEUR_DISPCHAR 'I'
44 #define HEUR_PRIORITY -500000
45 #define HEUR_FREQ -1 /* at the moment, the heuristic seems to be useless */
46 #define HEUR_FREQOFS 0
47 #define HEUR_MAXDEPTH -1
48 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
49 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
50 
51 #define MAXDIVEDEPTH 100
52 
53 
54 /*
55  * Default parameter settings
56  */
57 
58 #define DEFAULT_PROPROUNDS 0 /**< maximal number of propagation rounds in probing subproblems */
59 #define DEFAULT_MINFIXINGS 100 /**< minimal number of fixings to apply before dive may be aborted */
60 
61 
62 /*
63  * Data structures
64  */
65 
66 /** primal heuristic data */
67 struct SCIP_HeurData
68 {
69  int proprounds; /**< maximal number of propagation rounds in probing subproblems */
70  int minfixings; /**< minimal number of fixings to apply before dive may be aborted */
71 };
72 
73 
74 /*
75  * Local methods
76  */
77 
78 /** selects a variable and fixes it to its current pseudo solution value */
79 static
81  SCIP* scip, /**< SCIP data structure */
82  SCIP_VAR** pseudocands, /**< array of unfixed variables */
83  int npseudocands, /**< number of unfixed variables */
84  SCIP_Real large /**< large value to be used instead of infinity */
85  )
86 {
87  SCIP_VAR* var;
88  SCIP_Real bestscore;
89  SCIP_Real score;
90  SCIP_Real solval;
91  int bestcand;
92  int ncands;
93  int c;
94 
95  assert(pseudocands != NULL);
96  assert(npseudocands > 0);
97 
98  /* if existing, choose one of the highest priority binary variables; if no high priority binary variables
99  * exist, choose a variable among all unfixed integral variables
100  */
101  ncands = SCIPgetNPrioPseudoBranchBins(scip);
102  if( ncands == 0 )
103  ncands = npseudocands;
104 
105  /* select variable to tighten the domain for */
106  bestscore = -SCIPinfinity(scip);
107  bestcand = -1;
108  for( c = 0; c < ncands; ++c )
109  {
110  score = SCIPgetVarAvgInferenceScore(scip, pseudocands[c]);
111  if( score > bestscore )
112  {
113  bestscore = score;
114  bestcand = c;
115  }
116  }
117  assert(bestcand != -1);
118 
119  /* fix variable to its current pseudo solution value */
120  var = pseudocands[bestcand];
121  solval = SCIPgetVarSol(scip, var);
122 
123  /* adapt solution value if it is infinite */
124  if( SCIPisInfinity(scip, solval) )
125  {
126  SCIP_Real lb;
127  assert(SCIPisInfinity(scip, SCIPvarGetUbLocal(var)));
128  lb = SCIPvarGetLbLocal(var);
129 
130  /* adapt fixing value by changing it to a large value */
131  if( SCIPisInfinity(scip, -lb) )
132  solval = SCIPceil(scip, large);
133  else if( !SCIPisInfinity(scip, SCIPceil(scip, lb+large)) )
134  solval = SCIPceil(scip, lb+large);
135  }
136  else if( SCIPisInfinity(scip, -solval) )
137  {
138  SCIP_Real ub;
139  assert(SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)));
140  ub = SCIPvarGetUbLocal(var);
141 
142  /* adapt fixing value by changing it to a large negative value */
143  if( SCIPisInfinity(scip, ub) )
144  solval = SCIPfloor(scip, -large);
145  else if( !SCIPisInfinity(scip, -SCIPfloor(scip, ub-large)) )
146  solval = SCIPfloor(scip, ub-large);
147  }
148 
149  assert(SCIPisFeasIntegral(scip, solval)); /* in probing, we always have the pseudo solution */
150  SCIPdebugMsg(scip, " -> fixed variable <%s>[%g,%g] = %g (%d candidates left)\n",
151  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), solval, npseudocands - 1);
152  SCIP_CALL( SCIPfixVarProbing(scip, var, solval) );
153 
154  return SCIP_OKAY;
155 }
156 
157 
158 /*
159  * Callback methods of primal heuristic
160  */
161 
162 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
163 static
164 SCIP_DECL_HEURCOPY(heurCopyFixandinfer)
165 { /*lint --e{715}*/
166  assert(scip != NULL);
167  assert(heur != NULL);
168  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
169 
170  /* call inclusion method of primal heuristic */
172 
173  return SCIP_OKAY;
174 }
175 
176 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
177 static
178 SCIP_DECL_HEURFREE(heurFreeFixandinfer) /*lint --e{715}*/
179 { /*lint --e{715}*/
180  SCIP_HEURDATA* heurdata;
181 
182  /* free heuristic data */
183  heurdata = SCIPheurGetData(heur);
184  assert(heurdata != NULL);
185  SCIPfreeBlockMemory(scip, &heurdata);
186  SCIPheurSetData(heur, NULL);
187 
188  return SCIP_OKAY;
189 }
190 
191 
192 /** execution method of primal heuristic */
193 static
194 SCIP_DECL_HEUREXEC(heurExecFixandinfer)
195 { /*lint --e{715}*/
196  SCIP_HEURDATA* heurdata;
197  SCIP_VAR** cands;
198  int ncands;
199  int startncands;
200  int divedepth;
201  SCIP_Bool cutoff;
202  SCIP_Real large;
203 
204  *result = SCIP_DIDNOTRUN;
205 
206  /* do not call heuristic of node was already detected to be infeasible */
207  if( nodeinfeasible )
208  return SCIP_OKAY;
209 
210  /* we cannot run on problems with continuous variables */
211  if( SCIPgetNContVars(scip) > 0 )
212  return SCIP_OKAY;
213 
214  /* get unfixed variables */
215  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) );
216  if( ncands == 0 )
217  return SCIP_OKAY;
218 
219  /* get heuristic data */
220  heurdata = SCIPheurGetData(heur);
221  assert(heurdata != NULL);
222 
223  /* fix variables and propagate inferences as long as the problem is still feasible and there are
224  * unfixed integral variables
225  */
226  cutoff = FALSE;
227  divedepth = 0;
228  startncands = ncands;
229 
230  /* start probing */
232 
234  {
236  return SCIP_OKAY;
237  }
238 
239  SCIPdebugMsg(scip, "starting fix-and-infer heuristic with %d unfixed integral variables\n", ncands);
240 
241  *result = SCIP_DIDNOTFIND;
242 
243  /* create next probing node */
245 
246  /* determine large value to set variables to */
247  large = SCIPinfinity(scip);
248  if( !SCIPisInfinity(scip, 0.1 / SCIPfeastol(scip)) )
249  large = 0.1 / SCIPfeastol(scip);
250 
251  while( !cutoff && ncands > 0
252  && (divedepth < heurdata->minfixings || (startncands - ncands) * 2 * MAXDIVEDEPTH >= startncands * divedepth)
253  && !SCIPisStopped(scip) )
254  {
255  divedepth++;
256 
257  /* fix next variable */
258  SCIP_CALL( fixVariable(scip, cands, ncands, large) );
259 
260  /* propagate the fixing */
261  SCIP_CALL( SCIPpropagateProbing(scip, heurdata->proprounds, &cutoff, NULL) );
262 
263  /* get remaining unfixed variables */
264  if( !cutoff )
265  {
266  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, NULL) );
267  }
268  }
269 
270  /* check, if we are still feasible */
271  if( cutoff )
272  {
273  SCIPdebugMsg(scip, "propagation detected a cutoff\n");
274  }
275  else if( ncands == 0 )
276  {
277  SCIP_Bool success;
278 
279  success = FALSE;
280 
281  /* try to add solution to SCIP */
282  SCIP_CALL( SCIPtryCurrentSol(scip, heur, FALSE, FALSE, FALSE, TRUE, &success) );
283 
284  if( success )
285  {
286  SCIPdebugMsg(scip, "found primal feasible solution\n");
287  *result = SCIP_FOUNDSOL;
288  }
289  else
290  {
291  SCIPdebugMsg(scip, "primal solution was rejected\n");
292  }
293  }
294  else
295  {
296  SCIPdebugMsg(scip, "probing was aborted (probing depth: %d, fixed: %d/%d)", divedepth, startncands - ncands, startncands);
297  }
298 
299  /* end probing */
301 
302  return SCIP_OKAY;
303 }
304 
305 
306 /*
307  * primal heuristic specific interface methods
308  */
309 
310 /** creates the fix-and-infer primal heuristic and includes it in SCIP */
312  SCIP* scip /**< SCIP data structure */
313  )
314 {
315  SCIP_HEURDATA* heurdata;
316  SCIP_HEUR* heur;
317 
318  /* create Fixandinfer primal heuristic data */
319  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
320 
321  /* include primal heuristic */
322  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
324  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFixandinfer, heurdata) );
325 
326  assert(heur != NULL);
327 
328  /* set non-NULL pointers to callback methods */
329  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyFixandinfer) );
330  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeFixandinfer) );
331 
332  /* fixandinfer heuristic parameters */
334  "heuristics/fixandinfer/proprounds",
335  "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)",
336  &heurdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) );
338  "heuristics/fixandinfer/minfixings",
339  "minimal number of fixings to apply before dive may be aborted",
340  &heurdata->minfixings, TRUE, DEFAULT_MINFIXINGS, 0, INT_MAX, NULL, NULL) );
341 
342  return SCIP_OKAY;
343 }
SCIP_RETCODE SCIPtryCurrentSol(SCIP *scip, SCIP_HEUR *heur, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3311
SCIP_Real SCIPfeastol(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2167
#define NULL
Definition: def.h:253
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:686
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
public methods for SCIP parameter handling
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:408
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:155
public methods for memory management
#define HEUR_FREQ
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
#define HEUR_DISPCHAR
static SCIP_RETCODE fixVariable(SCIP *scip, SCIP_VAR **pseudocands, int npseudocands, SCIP_Real large)
#define HEUR_DESC
#define FALSE
Definition: def.h:73
static SCIP_DECL_HEUREXEC(heurExecFixandinfer)
static SCIP_DECL_HEURFREE(heurFreeFixandinfer)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
public methods for problem variables
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEURCOPY(heurCopyFixandinfer)
public methods for numerical tolerances
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:722
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_heur.c:107
public methods for the branch-and-bound tree
#define DEFAULT_PROPROUNDS
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
#define HEUR_MAXDEPTH
#define MAXDIVEDEPTH
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:250
#define HEUR_TIMING
#define SCIP_CALL(x)
Definition: def.h:365
public methods for primal heuristic plugins and divesets
#define DEFAULT_MINFIXINGS
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:637
#define SCIP_Bool
Definition: def.h:70
fix-and-infer primal heuristic
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:565
#define HEUR_PRIORITY
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17408
#define SCIP_MAXTREEDEPTH
Definition: def.h:301
#define HEUR_USESSUBSCIP
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17418
public methods for branching rule plugins and branching
general public methods
SCIP_RETCODE SCIPincludeHeurFixandinfer(SCIP *scip)
public methods for solutions
#define HEUR_NAME
#define HEUR_FREQOFS
public methods for the probing mode
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:152
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:109
public methods for message output
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_param.c:73
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:2309
#define SCIP_Real
Definition: def.h:164
public methods for message handling
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:168
int SCIPgetNPrioPseudoBranchBins(SCIP *scip)
Definition: scip_branch.c:784
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9300
public methods for primal heuristics
public methods for global and local (sub)problems