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