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) */
60static
61SCIP_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 */
75static
76SCIP_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? */
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}
#define MAXDNOM
Definition: cons_linear.c:167
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define SCIP_CALL(x)
Definition: def.h:374
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
Definition: misc.c:9824
SCIP_RETCODE SCIPincludePresolTrivial(SCIP *scip)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
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
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4676
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4766
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
#define PRESOL_NAME
static SCIP_DECL_PRESOLCOPY(presolCopyTrivial)
#define PRESOL_PRIORITY
static SCIP_DECL_PRESOLEXEC(presolExecTrivial)
#define PRESOL_MAXROUNDS
#define PRESOL_TIMING
#define PRESOL_DESC
trivial presolver: round fractional bounds on integer variables, fix variables with equal bounds
public methods for message output
public methods for presolvers
public methods for problem variables
public methods for message handling
public methods for numerical tolerances
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for SCIP variables
@ SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:55
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71