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