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