Scippy

SCIP

Solving Constraint Integer Programs

presol_trivial.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-2018 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 presol_trivial.c
17  * @brief trivial presolver: round fractional bounds on integer variables, fix variables with equal bounds
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "scip/presol_trivial.h"
24 #include "scip/pub_message.h"
25 #include "scip/pub_presol.h"
26 #include "scip/pub_var.h"
27 #include "scip/scip_message.h"
28 #include "scip/scip_numerics.h"
29 #include "scip/scip_presol.h"
30 #include "scip/scip_prob.h"
31 #include "scip/scip_var.h"
32 #include <string.h>
33 
34 #define PRESOL_NAME "trivial"
35 #define PRESOL_DESC "round fractional bounds on integers, fix variables with equal bounds"
36 #define PRESOL_PRIORITY +9000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
37 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
38 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
39 
40 #ifdef FIXSIMPLEVALUE
41 #define MAXDNOM 10000LL /**< maximal denominator for simple rational fixed values */
42 #endif
43 
44 
45 /*
46  * Callback methods of presolver
47  */
48 
49 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
50 static
51 SCIP_DECL_PRESOLCOPY(presolCopyTrivial)
52 { /*lint --e{715}*/
53  assert(scip != NULL);
54  assert(presol != NULL);
55  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
56 
57  /* call inclusion method of presolver */
59 
60  return SCIP_OKAY;
61 }
62 
63 
64 /** presolving execution method */
65 static
66 SCIP_DECL_PRESOLEXEC(presolExecTrivial)
67 { /*lint --e{715}*/
68  SCIP_VAR** vars;
69  int nvars;
70  int v;
71 
72  assert(result != NULL);
73 
74  *result = SCIP_DIDNOTFIND;
75 
76  /* get the problem variables */
77  vars = SCIPgetVars(scip);
78  nvars = SCIPgetNVars(scip);
79 
80  /* scan the variables for trivial bound reductions
81  * (loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array)
82  */
83  for( v = nvars-1; v >= 0; --v )
84  {
85  SCIP_Real lb;
86  SCIP_Real ub;
87  SCIP_Bool infeasible;
88  SCIP_Bool fixed;
89 
90  /* get variable's bounds */
91  lb = SCIPvarGetLbGlobal(vars[v]);
92  ub = SCIPvarGetUbGlobal(vars[v]);
93 
94  /* is variable integral? */
95  if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS )
96  {
97  SCIP_Real newlb;
98  SCIP_Real newub;
99 
100  /* round fractional bounds on integer variables */
101  newlb = SCIPfeasCeil(scip, lb);
102  newub = SCIPfeasFloor(scip, ub);
103 
104  /* check bounds on variable for infeasibility */
105  if( newlb > newub + 0.5 )
106  {
108  "problem infeasible: integral variable <%s> has bounds [%.17f,%.17f] rounded to [%.17f,%.17f]\n",
109  SCIPvarGetName(vars[v]), lb, ub, newlb, newub);
110  *result = SCIP_CUTOFF;
111  return SCIP_OKAY;
112  }
113 
114  /* fix variables with equal bounds */
115  if( newlb > newub - 0.5 )
116  {
117  SCIPdebugMsg(scip, "fixing integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n", SCIPvarGetName(vars[v]), lb, ub, newlb, newub);
118  SCIP_CALL( SCIPfixVar(scip, vars[v], newlb, &infeasible, &fixed) );
119  if( infeasible )
120  {
121  SCIPdebugMsg(scip, " -> infeasible fixing\n");
122  *result = SCIP_CUTOFF;
123  return SCIP_OKAY;
124  }
125  assert(fixed);
126  (*nfixedvars)++;
127  }
128  else
129  {
130  /* round fractional bounds */
131  if( !SCIPisFeasEQ(scip, lb, newlb) )
132  {
133  SCIPdebugMsg(scip, "rounding lower bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
134  SCIPvarGetName(vars[v]), lb, ub, newlb, ub);
135  SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlb) );
136  (*nchgbds)++;
137  }
138  if( !SCIPisFeasEQ(scip, ub, newub) )
139  {
140  SCIPdebugMsg(scip, "rounding upper bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
141  SCIPvarGetName(vars[v]), newlb, ub, newlb, newub);
142  SCIP_CALL( SCIPchgVarUb(scip, vars[v], newub) );
143  (*nchgbds)++;
144  }
145  }
146  }
147  else
148  {
149  /* check bounds on continuous variable for infeasibility */
150  if( SCIPisFeasGT(scip, lb, ub) )
151  {
153  "problem infeasible: continuous variable <%s> has bounds [%.17f,%.17f]\n",
154  SCIPvarGetName(vars[v]), lb, ub);
155  *result = SCIP_CUTOFF;
156  return SCIP_OKAY;
157  }
158 
159  /* fix variables with equal bounds */
160  if( SCIPisEQ(scip, lb, ub) )
161  {
162  SCIP_Real fixval;
163 
164 #ifdef FIXSIMPLEVALUE
165  fixval = SCIPselectSimpleValue(lb - 0.9 * SCIPepsilon(scip), ub + 0.9 * SCIPepsilon(scip), MAXDNOM);
166 #else
167  fixval = (lb + ub)/2;
168 #endif
169  SCIPdebugMsg(scip, "fixing continuous variable <%s>[%.17f,%.17f] to %.17f\n", SCIPvarGetName(vars[v]), lb, ub, fixval);
170  SCIP_CALL( SCIPfixVar(scip, vars[v], fixval, &infeasible, &fixed) );
171  if( infeasible )
172  {
173  SCIPdebugMsg(scip, " -> infeasible fixing\n");
174  *result = SCIP_CUTOFF;
175  return SCIP_OKAY;
176  }
177  assert(fixed);
178  (*nfixedvars)++;
179  }
180  }
181  }
182 
183  return SCIP_OKAY;
184 }
185 
186 
187 /*
188  * presolver specific interface methods
189  */
190 
191 /** creates the trivial presolver and includes it in SCIP */
193  SCIP* scip /**< SCIP data structure */
194  )
195 {
196  SCIP_PRESOL* presolptr;
197 
198  /* include presolver */
200 
201  assert(presolptr != NULL);
202 
203  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyTrivial) );
204 
205  return SCIP_OKAY;
206 }
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip_presol.c:174
#define NULL
Definition: def.h:239
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
#define PRESOL_TIMING
public methods for presolving plugins
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
public methods for problem variables
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
Definition: misc.c:9132
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4613
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP variables
trivial presolver: round fractional bounds on integer variables, fix variables with equal bounds ...
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17353
#define PRESOL_NAME
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4703
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:296
SCIP_RETCODE SCIPincludePresolTrivial(SCIP *scip)
#define SCIP_Bool
Definition: def.h:62
#define PRESOL_DESC
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:589
static SCIP_DECL_PRESOLCOPY(presolCopyTrivial)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8168
#define MAXDNOM
Definition: cons_linear.c:172
static SCIP_DECL_PRESOLEXEC(presolExecTrivial)
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
public methods for presolvers
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:209
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
#define SCIP_Real
Definition: def.h:150
public methods for message handling
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16894
#define PRESOL_MAXROUNDS
#define PRESOL_PRIORITY
public methods for global and local (sub)problems