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