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