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