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