Scippy

SCIP

Solving Constraint Integer Programs

prop_dualfix.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 prop_dualfix.c
17  * @brief fixing roundable variables to best bound
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "scip/prop_dualfix.h"
25 #include "scip/pub_message.h"
26 #include "scip/pub_prop.h"
27 #include "scip/pub_var.h"
28 #include "scip/scip_general.h"
29 #include "scip/scip_message.h"
30 #include "scip/scip_numerics.h"
31 #include "scip/scip_prob.h"
32 #include "scip/scip_probing.h"
33 #include "scip/scip_prop.h"
34 #include "scip/scip_tree.h"
35 #include "scip/scip_var.h"
36 #include <string.h>
37 
38 #define PROP_NAME "dualfix"
39 #define PROP_DESC "roundable variables dual fixing"
40 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP
41 #define PROP_PRIORITY +8000000 /**< propagation priority */
42 #define PROP_FREQ 0 /**< propagation frequency */
43 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found
44  * reductions? */
45 #define PROP_PRESOL_PRIORITY +8000000 /**< priority of the propagator (>= 0: before, < 0: after constraint handlers) */
46 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of propving rounds the propver participates in (-1: no limit) */
47 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
48 
49 
50 /**@name Local methods
51  *
52  * @{
53  */
54 
55 /** perform dual presolving */
56 static
58  SCIP* scip, /**< SCIP data structure */
59  int* nfixedvars, /**< pointer to store number of fixed variables */
60  SCIP_Bool* unbounded, /**< pointer to store if an unboundness was detected */
61  SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
62  )
63 {
64  SCIP_VAR** vars;
65  int nvars;
66  int v;
67 
68  /* get active problem variables */
69  vars = SCIPgetVars(scip);
70  nvars = SCIPgetNVars(scip);
71 
72  /* look for fixable variables
73  * loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array
74  */
75  for( v = nvars - 1; v >= 0; --v )
76  {
77  SCIP_VAR* var;
79  SCIP_Real obj;
80  SCIP_Bool infeasible;
81  SCIP_Bool fixed;
82 
83  var = vars[v];
84  assert(var != NULL);
85 
86  /* don't perform dual presolving operations on deleted variables */
87  if( SCIPvarIsDeleted(var) )
88  continue;
89 
90  /* ignore already fixed variables (use feasibility tolerance since this is used in SCIPfixVar() */
91  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
92  continue;
93 
94  obj = SCIPvarGetObj(var);
95 
96  /* if the objective coefficient of the variable is 0 and it may be rounded both
97  * up and down, then fix it to the closest feasible value to 0 */
98  if( SCIPisZero(scip, obj) && SCIPvarMayRoundDown(var) && SCIPvarMayRoundUp(var) )
99  {
100  SCIP_Real roundbound;
101 
102  bound = SCIPvarGetLbGlobal(var);
103  if( SCIPisLT(scip, bound, 0.0) )
104  {
105  if( SCIPisLE(scip, 0.0, SCIPvarGetUbGlobal(var)) )
106  bound = 0.0;
107  else
108  {
109  /* try to take an integer value, only for polishing */
110  roundbound = SCIPfloor(scip, SCIPvarGetUbGlobal(var));
111 
112  if( roundbound < bound )
113  bound = SCIPvarGetUbGlobal(var);
114  else
115  bound = roundbound;
116  }
117  }
118  else
119  {
120  /* try to take an integer value, only for polishing */
121  roundbound = SCIPceil(scip, bound);
122 
123  if( roundbound < SCIPvarGetUbGlobal(var) )
124  bound = roundbound;
125  }
126  SCIPdebugMsg(scip, "fixing variable <%s> with objective 0 to %g\n", SCIPvarGetName(var), bound);
127  }
128  else
129  {
130  /* if it is always possible to round variable in direction of objective value, fix it to its proper bound */
131  if( SCIPvarMayRoundDown(var) && !SCIPisNegative(scip, obj) )
132  {
133  bound = SCIPvarGetLbGlobal(var);
134  if ( SCIPisInfinity(scip, -bound) )
135  {
136  /* variable can be fixed to -infinity */
137  if ( SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING )
138  {
139  /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this
140  * consistently. We thus have to ignore this (should better be handled in presolving). */
141  continue;
142  }
143  if ( SCIPisZero(scip, obj) && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 1 )
144  {
145  /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is
146  * clever enough to set/aggregate the variable to something more useful than -infinity and do nothing
147  * here. */
148  continue;
149  }
150  }
151  SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d uplocks to lower bound %g\n",
153  }
154  else if( SCIPvarMayRoundUp(var) && !SCIPisPositive(scip, obj) )
155  {
156  bound = SCIPvarGetUbGlobal(var);
157  if ( SCIPisInfinity(scip, bound) )
158  {
159  /* variable can be fixed to infinity */
160  if ( SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING )
161  {
162  /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this
163  * consistently. We thus have to ignore this (should better be handled in presolving). */
164  continue;
165  }
166  if ( SCIPisZero(scip, obj) && SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 1 )
167  {
168  /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is
169  * clever enough to set/aggregate the variable to something more useful than +infinity and do nothing
170  * here */
171  continue;
172  }
173  }
174  SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d downlocks to upper bound %g\n",
176  }
177  else
178  continue;
179  }
180 
181  if( SCIPisInfinity(scip, REALABS(bound)) && !SCIPisZero(scip, obj) )
182  {
183  SCIPdebugMsg(scip, " -> unbounded fixing\n");
185  "problem infeasible or unbounded: variable <%s> with objective %.15g can be made infinitely %s\n",
186  SCIPvarGetName(var), SCIPvarGetObj(var), bound < 0.0 ? "small" : "large");
187  *unbounded = TRUE;
188  return SCIP_OKAY;
189  }
190 
191  /* apply the fixing */
192  SCIPdebugMsg(scip, "apply fixing of variable %s to %g\n", SCIPvarGetName(var), bound);
193  SCIP_CALL( SCIPfixVar(scip, var, bound, &infeasible, &fixed) );
194 
195  if( infeasible )
196  {
197  SCIPdebugMsg(scip, " -> infeasible fixing\n");
198  *cutoff = TRUE;
199  return SCIP_OKAY;
200  }
201 
202  assert(fixed || (SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPisFeasEQ(scip, bound, SCIPvarGetLbLocal(var))
203  && SCIPisFeasEQ(scip, bound, SCIPvarGetUbLocal(var))));
204  (*nfixedvars)++;
205  }
206 
207  return SCIP_OKAY;
208 }
209 
210 /**@} */
211 
212 /**@name Callback methods
213  *
214  * @{
215  */
216 
217 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
218 static
219 SCIP_DECL_PROPCOPY(propCopyDualfix)
220 { /*lint --e{715}*/
221  assert(scip != NULL);
222  assert(prop != NULL);
223  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
224 
225  /* call inclusion method of propagator */
227 
228  return SCIP_OKAY;
229 }
230 
231 /** presolving method of propagator */
232 static
233 SCIP_DECL_PROPPRESOL(propPresolDualfix)
234 { /*lint --e{715}*/
235  SCIP_Bool cutoff;
236  SCIP_Bool unbounded;
237  int oldnfixedvars;
238 
239  assert(prop != NULL);
240  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
241  assert(result != NULL);
242 
243  *result = SCIP_DIDNOTRUN;
244 
245  if( !SCIPallowDualReds(scip) )
246  return SCIP_OKAY;
247 
248  cutoff = FALSE;
249  unbounded = FALSE;
250  oldnfixedvars = *nfixedvars;
251 
252  SCIP_CALL( performDualfix(scip, nfixedvars, &unbounded, &cutoff) );
253 
254  /* evaluate propagation result */
255  if( cutoff )
256  *result = SCIP_CUTOFF;
257  else if( unbounded )
258  *result = SCIP_UNBOUNDED;
259  else if( *nfixedvars > oldnfixedvars )
260  *result = SCIP_SUCCESS;
261  else
262  *result = SCIP_DIDNOTFIND;
263 
264  return SCIP_OKAY;
265 }
266 
267 /** execution method of propagator */
268 static
269 SCIP_DECL_PROPEXEC(propExecDualfix)
270 { /*lint --e{715}*/
271  int nfixedvars;
272  SCIP_Bool cutoff;
273  SCIP_Bool unbounded;
274 
275  assert(prop != NULL);
276  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
277  assert(result != NULL);
278 
279  *result = SCIP_DIDNOTRUN;
280 
281  /** @warning Don't run in probing or in repropagation since this can lead to wrong conclusion
282  *
283  * do not run if propagation w.r.t. current objective is not allowed
284  */
286  return SCIP_OKAY;
287 
288  cutoff = FALSE;
289  unbounded = FALSE;
290  nfixedvars = 0;
291 
292  SCIP_CALL( performDualfix(scip, &nfixedvars, &unbounded, &cutoff) );
293 
294  /* evaluate propagation result */
295  if( cutoff )
296  *result = SCIP_CUTOFF;
297  else if( unbounded )
298  *result = SCIP_UNBOUNDED;
299  else if( nfixedvars > 0 )
300  *result = SCIP_REDUCEDDOM;
301  else
302  *result = SCIP_DIDNOTFIND;
303 
304  return SCIP_OKAY;
305 }
306 
307 
308 /**@} */
309 
310 /**@name Interface methods
311  *
312  * @{
313  */
314 
315 /** creates the dual fixing propagator and includes it in SCIP */
317  SCIP* scip /**< SCIP data structure */
318  )
319 {
320  SCIP_PROP* prop;
321 
322  /* include propagator */
324  assert(prop != NULL);
325 
326  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyDualfix) );
328 
329  return SCIP_OKAY;
330 }
331 
332 /**@} */
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
static SCIP_DECL_PROPPRESOL(propPresolDualfix)
Definition: prop_dualfix.c:234
#define NULL
Definition: def.h:253
SCIP_EXPORT int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3241
static long bound
#define PROP_PRIORITY
Definition: prop_dualfix.c:41
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1987
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:215
#define FALSE
Definition: def.h:73
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17200
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
public methods for problem variables
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
#define PROP_PRESOL_MAXROUNDS
Definition: prop_dualfix.c:47
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:135
public methods for SCIP variables
SCIP_EXPORT SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition: var.c:3327
#define PROP_TIMING
Definition: prop_dualfix.c:40
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:141
public methods for numerical tolerances
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for the branch-and-bound tree
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16738
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1942
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:931
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:87
#define PROP_FREQ
Definition: prop_dualfix.c:42
#define REALABS(x)
Definition: def.h:188
#define SCIP_CALL(x)
Definition: def.h:365
#define PROP_PRESOL_PRIORITY
Definition: prop_dualfix.c:46
SCIP_RETCODE SCIPincludePropDualfix(SCIP *scip)
Definition: prop_dualfix.c:317
SCIP_EXPORT SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition: var.c:3338
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17362
#define PROP_DELAY
Definition: prop_dualfix.c:43
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip_var.c:8506
static SCIP_DECL_PROPEXEC(propExecDualfix)
Definition: prop_dualfix.c:270
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8180
SCIP_EXPORT SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
Definition: var.c:16959
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17408
SCIP_EXPORT int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3184
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17418
general public methods
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17352
public methods for the probing mode
public methods for message output
#define SCIP_Real
Definition: def.h:164
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message handling
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:269
public methods for propagator plugins
#define PROP_NAME
Definition: prop_dualfix.c:38
#define PROP_DESC
Definition: prop_dualfix.c:39
static SCIP_RETCODE performDualfix(SCIP *scip, int *nfixedvars, SCIP_Bool *unbounded, SCIP_Bool *cutoff)
Definition: prop_dualfix.c:58
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:104
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:355
fixing roundable variables to best bound
public methods for global and local (sub)problems
static SCIP_DECL_PROPCOPY(propCopyDualfix)
Definition: prop_dualfix.c:220
#define PROP_PRESOLTIMING
Definition: prop_dualfix.c:48
public methods for propagators