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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file presol_trivial.c
26  * @ingroup DEFPLUGINS_PRESOL
27  * @brief trivial presolver: round fractional bounds on integer variables, fix variables with equal bounds
28  * @author Tobias Achterberg
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #include "scip/presol_trivial.h"
34 #include "scip/pub_message.h"
35 #include "scip/pub_presol.h"
36 #include "scip/pub_var.h"
37 #include "scip/scip_message.h"
38 #include "scip/scip_numerics.h"
39 #include "scip/scip_presol.h"
40 #include "scip/scip_prob.h"
41 #include "scip/scip_var.h"
42 #include <string.h>
43 
44 #define PRESOL_NAME "trivial"
45 #define PRESOL_DESC "round fractional bounds on integers, fix variables with equal bounds"
46 #define PRESOL_PRIORITY +9000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
47 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
48 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
49 
50 #ifdef FIXSIMPLEVALUE
51 #define MAXDNOM 10000LL /**< maximal denominator for simple rational fixed values */
52 #endif
53 
54 
55 /*
56  * Callback methods of presolver
57  */
58 
59 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
60 static
61 SCIP_DECL_PRESOLCOPY(presolCopyTrivial)
62 { /*lint --e{715}*/
63  assert(scip != NULL);
64  assert(presol != NULL);
65  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
66 
67  /* call inclusion method of presolver */
69 
70  return SCIP_OKAY;
71 }
72 
73 
74 /** presolving execution method */
75 static
76 SCIP_DECL_PRESOLEXEC(presolExecTrivial)
77 { /*lint --e{715}*/
78  SCIP_VAR** vars;
79  int nvars;
80  int v;
81 
82  assert(result != NULL);
83 
84  *result = SCIP_DIDNOTFIND;
85 
86  /* get the problem variables */
87  vars = SCIPgetVars(scip);
88  nvars = SCIPgetNVars(scip);
89 
90  /* scan the variables for trivial bound reductions
91  * (loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array)
92  */
93  for( v = nvars-1; v >= 0; --v )
94  {
95  SCIP_Real lb;
96  SCIP_Real ub;
97  SCIP_Bool infeasible;
98  SCIP_Bool fixed;
99 
100  /* get variable's bounds */
101  lb = SCIPvarGetLbGlobal(vars[v]);
102  ub = SCIPvarGetUbGlobal(vars[v]);
103 
104  /* is variable integral? */
105  if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS )
106  {
107  SCIP_Real newlb;
108  SCIP_Real newub;
109 
110  /* round fractional bounds on integer variables */
111  newlb = SCIPfeasCeil(scip, lb);
112  newub = SCIPfeasFloor(scip, ub);
113 
114  /* check bounds on variable for infeasibility */
115  if( newlb > newub + 0.5 )
116  {
118  "problem infeasible: integral variable <%s> has bounds [%.17f,%.17f] rounded to [%.17f,%.17f]\n",
119  SCIPvarGetName(vars[v]), lb, ub, newlb, newub);
120  *result = SCIP_CUTOFF;
121  return SCIP_OKAY;
122  }
123 
124  /* fix variables with equal bounds */
125  if( newlb > newub - 0.5 )
126  {
127  SCIPdebugMsg(scip, "fixing integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n", SCIPvarGetName(vars[v]), lb, ub, newlb, newub);
128  SCIP_CALL( SCIPfixVar(scip, vars[v], newlb, &infeasible, &fixed) );
129  if( infeasible )
130  {
131  SCIPdebugMsg(scip, " -> infeasible fixing\n");
132  *result = SCIP_CUTOFF;
133  return SCIP_OKAY;
134  }
135  assert(fixed);
136  (*nfixedvars)++;
137  }
138  else
139  {
140  /* round fractional bounds */
141  if( !SCIPisFeasEQ(scip, lb, newlb) )
142  {
143  SCIPdebugMsg(scip, "rounding lower bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
144  SCIPvarGetName(vars[v]), lb, ub, newlb, ub);
145  SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlb) );
146  (*nchgbds)++;
147  }
148  if( !SCIPisFeasEQ(scip, ub, newub) )
149  {
150  SCIPdebugMsg(scip, "rounding upper bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
151  SCIPvarGetName(vars[v]), newlb, ub, newlb, newub);
152  SCIP_CALL( SCIPchgVarUb(scip, vars[v], newub) );
153  (*nchgbds)++;
154  }
155  }
156  }
157  else
158  {
159  /* check bounds on continuous variable for infeasibility */
160  if( SCIPisFeasGT(scip, lb, ub) )
161  {
163  "problem infeasible: continuous variable <%s> has bounds [%.17f,%.17f]\n",
164  SCIPvarGetName(vars[v]), lb, ub);
165  *result = SCIP_CUTOFF;
166  return SCIP_OKAY;
167  }
168 
169  /* fix variables with equal bounds */
170  if( SCIPisEQ(scip, lb, ub) )
171  {
172  SCIP_Real fixval;
173 
174 #ifdef FIXSIMPLEVALUE
175  fixval = SCIPselectSimpleValue(lb - 0.9 * SCIPepsilon(scip), ub + 0.9 * SCIPepsilon(scip), MAXDNOM);
176 #else
177  /* prefer integral values (especially 0) over midpoint */
178  fixval = SCIPround(scip, lb);
179  if( fixval < lb || fixval > ub )
180  fixval = (lb + ub)/2;
181 #endif
182  SCIPdebugMsg(scip, "fixing continuous variable <%s>[%.17f,%.17f] to %.17f\n", SCIPvarGetName(vars[v]), lb, ub, fixval);
183  SCIP_CALL( SCIPfixVar(scip, vars[v], fixval, &infeasible, &fixed) );
184  if( infeasible )
185  {
186  SCIPdebugMsg(scip, " -> infeasible fixing\n");
187  *result = SCIP_CUTOFF;
188  return SCIP_OKAY;
189  }
190  assert(fixed);
191  (*nfixedvars)++;
192  }
193  }
194  }
195 
196  return SCIP_OKAY;
197 }
198 
199 
200 /*
201  * presolver specific interface methods
202  */
203 
204 /** creates the trivial presolver and includes it in SCIP */
206  SCIP* scip /**< SCIP data structure */
207  )
208 {
209  SCIP_PRESOL* presolptr;
210 
211  /* include presolver */
213 
214  assert(presolptr != NULL);
215 
216  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyTrivial) );
217 
218  return SCIP_OKAY;
219 }
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:105
#define NULL
Definition: def.h:267
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
#define PRESOL_TIMING
public methods for presolving plugins
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
public methods for problem variables
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
Definition: misc.c:9824
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4675
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:78
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:18089
#define PRESOL_NAME
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4765
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
#define SCIP_CALL(x)
Definition: def.h:380
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:225
SCIP_RETCODE SCIPincludePresolTrivial(SCIP *scip)
#define SCIP_Bool
Definition: def.h:91
#define PRESOL_DESC
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
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:8275
#define MAXDNOM
Definition: cons_linear.c:182
static SCIP_DECL_PRESOLEXEC(presolExecTrivial)
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
public methods for presolvers
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
#define SCIP_Real
Definition: def.h:173
public methods for message handling
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
#define PRESOL_MAXROUNDS
#define PRESOL_PRIORITY
public methods for global and local (sub)problems
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)