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-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 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 "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  SCIPdebugMsg(scip, "fixing integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n", SCIPvarGetName(vars[v]), lb, ub, newlb, newub);
113  SCIP_CALL( SCIPfixVar(scip, vars[v], newlb, &infeasible, &fixed) );
114  if( infeasible )
115  {
116  SCIPdebugMsg(scip, " -> infeasible fixing\n");
117  *result = SCIP_CUTOFF;
118  return SCIP_OKAY;
119  }
120  assert(fixed);
121  (*nfixedvars)++;
122  }
123  else
124  {
125  /* round fractional bounds */
126  if( !SCIPisFeasEQ(scip, lb, newlb) )
127  {
128  SCIPdebugMsg(scip, "rounding lower bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
129  SCIPvarGetName(vars[v]), lb, ub, newlb, ub);
130  SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlb) );
131  (*nchgbds)++;
132  }
133  if( !SCIPisFeasEQ(scip, ub, newub) )
134  {
135  SCIPdebugMsg(scip, "rounding upper bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
136  SCIPvarGetName(vars[v]), newlb, ub, newlb, newub);
137  SCIP_CALL( SCIPchgVarUb(scip, vars[v], newub) );
138  (*nchgbds)++;
139  }
140  }
141  }
142  else
143  {
144  /* check bounds on continuous variable for infeasibility */
145  if( SCIPisFeasGT(scip, lb, ub) )
146  {
148  "problem infeasible: continuous variable <%s> has bounds [%.17f,%.17f]\n",
149  SCIPvarGetName(vars[v]), lb, ub);
150  *result = SCIP_CUTOFF;
151  return SCIP_OKAY;
152  }
153 
154  /* fix variables with equal bounds */
155  if( SCIPisEQ(scip, lb, ub) )
156  {
157  SCIP_Real fixval;
158 
159 #ifdef FIXSIMPLEVALUE
160  fixval = SCIPselectSimpleValue(lb - 0.9 * SCIPepsilon(scip), ub + 0.9 * SCIPepsilon(scip), MAXDNOM);
161 #else
162  fixval = (lb + ub)/2;
163 #endif
164  SCIPdebugMsg(scip, "fixing continuous variable <%s>[%.17f,%.17f] to %.17f\n", SCIPvarGetName(vars[v]), lb, ub, fixval);
165  SCIP_CALL( SCIPfixVar(scip, vars[v], fixval, &infeasible, &fixed) );
166  if( infeasible )
167  {
168  SCIPdebugMsg(scip, " -> infeasible fixing\n");
169  *result = SCIP_CUTOFF;
170  return SCIP_OKAY;
171  }
172  assert(fixed);
173  (*nfixedvars)++;
174  }
175  }
176  }
177 
178  return SCIP_OKAY;
179 }
180 
181 
182 /*
183  * presolver specific interface methods
184  */
185 
186 /** creates the trivial presolver and includes it in SCIP */
188  SCIP* scip /**< SCIP data structure */
189  )
190 {
191  SCIP_PRESOL* presolptr;
192 
193  /* include presolver */
195 
196  assert(presolptr != NULL);
197 
198  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyTrivial) );
199 
200  return SCIP_OKAY;
201 }
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:6854
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46086
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
#define PRESOL_TIMING
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
Definition: misc.c:8482
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21611
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
trivial presolver: round fractional bounds on integer variables, fix variables with equal bounds ...
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:45246
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46223
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46211
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
#define PRESOL_NAME
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21701
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
#define NULL
Definition: lpi_spx1.cpp:137
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1353
SCIP_RETCODE SCIPincludePresolTrivial(SCIP *scip)
#define SCIP_Bool
Definition: def.h:61
#define PRESOL_DESC
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
static SCIP_DECL_PRESOLCOPY(presolCopyTrivial)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25141
#define MAXDNOM
Definition: cons_linear.c:144
static SCIP_DECL_PRESOLEXEC(presolExecTrivial)
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6889
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
#define SCIP_Real
Definition: def.h:135
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
#define PRESOL_MAXROUNDS
#define PRESOL_PRIORITY