Scippy

GCG

Branch-and-Price & Column Generation for Everyone

presol_roundbound.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-2021 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_roundbound.c
17  * @brief roundbound presolver: round fractional bounds on integer variables
18  * @author Tobias Achterberg
19  * @author Michael Bastubbe
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 "presol_roundbound.h"
28 
29 
30 #define PRESOL_NAME "roundbound"
31 #define PRESOL_DESC "roundbound presolver: round fractional bounds on integers"
32 #define PRESOL_PRIORITY +9000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
33 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
34 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
35 
36 #ifdef FIXSIMPLEVALUE
37 #define MAXDNOM 10000LL /**< maximal denominator for simple rational fixed values */
38 #endif
39 
40 
41 /*
42  * Callback methods of presolver
43  */
44 
45 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
46 static
47 SCIP_DECL_PRESOLCOPY(presolCopyRoundbound)
48 { /*lint --e{715}*/
49  assert(scip != NULL);
50  assert(presol != NULL);
51  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
52 
53  /* call inclusion method of presolver */
54  SCIP_CALL( SCIPincludePresolRoundbound(scip) );
55 
56  return SCIP_OKAY;
57 }
58 
59 
60 /** presolving execution method */
61 static
62 SCIP_DECL_PRESOLEXEC(presolExecRoundbound)
63 { /*lint --e{715}*/
64  SCIP_VAR** vars;
65  int nvars;
66  int v;
67 
68  assert(result != NULL);
69 
70  *result = SCIP_DIDNOTFIND;
71 
72  /* get the problem variables */
73  vars = SCIPgetVars(scip);
74  nvars = SCIPgetNVars(scip);
75 
76  /* scan the variables for roundbound bound reductions
77  * (loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array)
78  */
79  for( v = nvars-1; v >= 0; --v )
80  {
81  SCIP_Real lb;
82  SCIP_Real ub;
83 
84  /* get variable's bounds */
85  lb = SCIPvarGetLbGlobal(vars[v]);
86  ub = SCIPvarGetUbGlobal(vars[v]);
87 
88  /* is variable integral? */
89  if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS )
90  {
91  SCIP_Real newlb;
92  SCIP_Real newub;
93 
94  /* round fractional bounds on integer variables */
95  newlb = SCIPfeasCeil(scip, lb);
96  newub = SCIPfeasFloor(scip, ub);
97 
98  /* check bounds on variable for infeasibility */
99  if( newlb > newub + 0.5 )
100  {
101  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
102  "problem infeasible: integral variable <%s> has bounds [%.17f,%.17f] rounded to [%.17f,%.17f]\n",
103  SCIPvarGetName(vars[v]), lb, ub, newlb, newub);
104  *result = SCIP_CUTOFF;
105  return SCIP_OKAY;
106  }
107 
108  /* round fractional bounds */
109  if( !SCIPisFeasEQ(scip, lb, newlb) )
110  {
111  SCIPdebugMessage("rounding lower bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
112  SCIPvarGetName(vars[v]), lb, ub, newlb, ub);
113  SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlb) );
114  (*nchgbds)++;
115  }
116  if( !SCIPisFeasEQ(scip, ub, newub) )
117  {
118  SCIPdebugMessage("rounding upper bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
119  SCIPvarGetName(vars[v]), newlb, ub, newlb, newub);
120  SCIP_CALL( SCIPchgVarUb(scip, vars[v], newub) );
121  (*nchgbds)++;
122  }
123 
124  }
125  else
126  {
127  /* check bounds on continuous variable for infeasibility */
128  if( SCIPisFeasGT(scip, lb, ub) )
129  {
130  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
131  "problem infeasible: continuous variable <%s> has bounds [%.17f,%.17f]\n",
132  SCIPvarGetName(vars[v]), lb, ub);
133  *result = SCIP_CUTOFF;
134  return SCIP_OKAY;
135  }
136  }
137  }
138 
139  return SCIP_OKAY;
140 }
141 
142 
143 /*
144  * presolver specific interface methods
145  */
146 
147 /** creates the roundbound presolver and includes it in SCIP */
149  SCIP* scip /**< SCIP data structure */
150  )
151 {
152  SCIP_PRESOLDATA* presoldata;
153  SCIP_PRESOL* presolptr;
154 
155  /* create roundbound presolver data */
156  presoldata = NULL;
157 
158  /* include presolver */
159  SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING,
160  presolExecRoundbound,
161  presoldata) );
162 
163  assert(presolptr != NULL);
164 
165  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyRoundbound) );
166 
167  return SCIP_OKAY;
168 }
#define PRESOL_TIMING
static SCIP_DECL_PRESOLCOPY(presolCopyRoundbound)
#define PRESOL_DESC
roundbound presolver: round fractional bounds on integer variables
static SCIP_DECL_PRESOLEXEC(presolExecRoundbound)
#define PRESOL_PRIORITY
#define PRESOL_MAXROUNDS
#define PRESOL_NAME
SCIP_RETCODE SCIPincludePresolRoundbound(SCIP *scip)