Scippy

SCIP

Solving Constraint Integer Programs

presol_boundshift.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_boundshift.c
26 * @ingroup DEFPLUGINS_PRESOL
27 * @brief presolver that converts variables with domain [a,b] to variables with domain [0,b-a]
28 * @author Stefan Heinz
29 * @author Michael Winkler
30 */
31
32/**@todo test this presolving step to decide whether to turn it in default mode on or off */
33
34/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
38#include "scip/pub_message.h"
39#include "scip/pub_misc.h"
40#include "scip/pub_presol.h"
41#include "scip/pub_var.h"
42#include "scip/scip_mem.h"
43#include "scip/scip_message.h"
44#include "scip/scip_numerics.h"
45#include "scip/scip_param.h"
46#include "scip/scip_presol.h"
47#include "scip/scip_prob.h"
48#include "scip/scip_var.h"
49#include "scip/debug.h"
50#include <string.h>
51
52#define PRESOL_NAME "boundshift"
53#define PRESOL_DESC "converts variables with domain [a,b] to variables with domain [0,b-a]"
54#define PRESOL_PRIORITY 7900000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
55#define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
56#define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
57
58#define MAXABSBOUND 1000.0 /**< maximum absolute variable bounds for aggregation */
59
60/*
61 * Default parameter settings
62 */
63
64#define DEFAULT_MAXSHIFT SCIP_LONGINT_MAX /**< absolute value of maximum shift */
65#define DEFAULT_FLIPPING TRUE /**< is flipping allowed? */
66#define DEFAULT_INTEGER TRUE /**< are only integer ranges shifted */
67
68/*
69 * Data structures
70 */
71
72/** presolver data */
73struct SCIP_PresolData
74{
75 SCIP_Longint maxshift; /**< absolute value of maximum shift */
76 SCIP_Bool flipping; /**< is flipping allowed? */
77 SCIP_Bool integer; /**< shift only integer values? */
78};
79
80
81/*
82 * Local methods
83 */
84
85/*
86 * Callback methods of presolver
87 */
88
89/** copy method for constraint handler plugins (called when SCIP copies plugins) */
90static
91SCIP_DECL_PRESOLCOPY(presolCopyBoundshift)
92{ /*lint --e{715}*/
93 assert(scip != NULL);
94 assert(presol != NULL);
95 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
96
97 /* call inclusion method of presolver */
99
100 return SCIP_OKAY;
101}
102
103
104/** destructor of presolver to free user data (called when SCIP is exiting) */
105/**! [SnippetPresolFreeBoundshift] */
106static
107SCIP_DECL_PRESOLFREE(presolFreeBoundshift)
108{ /*lint --e{715}*/
109 SCIP_PRESOLDATA* presoldata;
110
111 /* free presolver data */
112 presoldata = SCIPpresolGetData(presol);
113 assert(presoldata != NULL);
114
115 SCIPfreeBlockMemory(scip, &presoldata);
116 SCIPpresolSetData(presol, NULL);
117
118 return SCIP_OKAY;
119}
120/**! [SnippetPresolFreeBoundshift] */
121
122
123/** presolving execution method */
124static
125SCIP_DECL_PRESOLEXEC(presolExecBoundshift)
126{ /*lint --e{715}*/
127 SCIP_PRESOLDATA* presoldata;
128 SCIP_VAR** scipvars;
129 SCIP_VAR** vars;
130 int nbinvars;
131 int nvars;
132 int v;
133
134 assert(scip != NULL);
135 assert(presol != NULL);
136 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
137 assert(result != NULL);
138
139 *result = SCIP_DIDNOTRUN;
140
141 if( SCIPdoNotAggr(scip) )
142 return SCIP_OKAY;
143
144 /* get presolver data */
145 presoldata = SCIPpresolGetData(presol);
146 assert(presoldata != NULL);
147
148 /* get the problem variables */
149 scipvars = SCIPgetVars(scip);
150 nbinvars = SCIPgetNBinVars(scip);
151 nvars = SCIPgetNVars(scip) - nbinvars;
152
153 if( nvars == 0 )
154 return SCIP_OKAY;
155
156 *result = SCIP_DIDNOTFIND;
157
158 /* copy the integer/continuous variables into an own array, since adding new variables affects the left-most slots in
159 * the array and thereby interferes with our search loop
160 */
161 SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nvars) );
162
163 /* scan the integer, implicit, and continuous variables for possible conversion */
164 for( v = nvars - 1; v >= 0; --v )
165 {
166 SCIP_VAR* var = vars[v];
167 SCIP_Real lb;
168 SCIP_Real ub;
169
170 assert(SCIPvarGetType(var) != SCIP_VARTYPE_BINARY);
171
172 /* do not shift non-active (fixed or (multi-)aggregated) variables */
173 if( !SCIPvarIsActive(var) )
174 continue;
175
176 /* get current variable's bounds */
177 lb = SCIPvarGetLbGlobal(var);
178 ub = SCIPvarGetUbGlobal(var);
179
180 /* it can happen that the variable bounds of integer variables have not been propagated yet or contain
181 * some small noise; this will result in an aggregation that might trigger assertions when updating bounds of
182 * aggregated variables (see #1817)
183 */
184 if( SCIPvarIsIntegral(var) )
185 {
186 assert(SCIPisIntegral(scip, lb));
187 assert(SCIPisIntegral(scip, ub));
188
189 lb = SCIPadjustedVarLb(scip, var, lb);
190 ub = SCIPadjustedVarUb(scip, var, ub);
191 }
192
193 assert( SCIPisLE(scip, lb, ub) );
194 if( SCIPisEQ(scip, lb, ub) )
195 continue;
196 if( presoldata->integer && !SCIPisIntegral(scip, ub - lb) )
197 continue;
198
199 /* check if bounds are shiftable */
200 if( !SCIPisEQ(scip, lb, 0.0) && /* lower bound != 0.0 */
201 SCIPisLT(scip, ub, SCIPinfinity(scip)) && /* upper bound != infinity */
202 SCIPisGT(scip, lb, -SCIPinfinity(scip)) && /* lower bound != -infinity */
203 SCIPisLT(scip, ub - lb, (SCIP_Real) presoldata->maxshift) && /* less than max shifting */
204 SCIPisLE(scip, REALABS(lb), MAXABSBOUND) && /* ensures a small constant in aggregation */
205 SCIPisLE(scip, REALABS(ub), MAXABSBOUND) ) /* ensures a small constant in aggregation */
206 {
207 SCIP_VAR* newvar;
208 char newvarname[SCIP_MAXSTRLEN];
209 SCIP_Bool infeasible;
210 SCIP_Bool redundant;
211 SCIP_Bool aggregated;
212
213 SCIPdebugMsg(scip, "convert range <%s>[%g,%g] to [%g,%g]\n", SCIPvarGetName(var), lb, ub, 0.0, (ub - lb) );
214
215 /* create new variable */
216 (void) SCIPsnprintf(newvarname, SCIP_MAXSTRLEN, "%s_shift", SCIPvarGetName(var));
217 SCIP_CALL( SCIPcreateVar(scip, &newvar, newvarname, 0.0, (ub - lb), 0.0, SCIPvarGetType(var),
219 SCIP_CALL( SCIPaddVar(scip, newvar) );
220
221#ifdef WITH_DEBUG_SOLUTION
222 if( SCIPdebugIsMainscip(scip) )
223 {
224 /* calculate and store debug solution value of shift variable */
225 SCIP_Real val;
226
227 SCIP_CALL( SCIPdebugGetSolVal(scip, var, &val) );
228 SCIPdebugMsg(scip, "debug solution value: <%s> = %g", SCIPvarGetName(var), val);
229
230 if( presoldata->flipping )
231 {
232 if( REALABS(ub) < REALABS(lb) )
233 val = ub - val;
234 else
235 val = val - lb;
236 }
237 else
238 {
239 val = val - lb;
240 }
241 SCIPdebugMsgPrint(scip, " -> <%s> = %g\n", SCIPvarGetName(newvar), val);
242
243 SCIP_CALL( SCIPdebugAddSolVal(scip, newvar, val) );
244 }
245#endif
246
247 /* aggregate old variable with new variable */
248 if( presoldata->flipping )
249 {
250 if( REALABS(ub) < REALABS(lb) )
251 {
252 SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, 1.0, ub, &infeasible, &redundant, &aggregated) );
253 }
254 else
255 {
256 SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
257 }
258 }
259 else
260 {
261 SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
262 }
263
264 if( infeasible )
265 *result = SCIP_CUTOFF;
266 else
267 {
268 assert(redundant);
269 assert(aggregated);
270 SCIPdebugMsg(scip, "var <%s> with bounds [%f,%f] has obj %f\n",
271 SCIPvarGetName(newvar), SCIPvarGetLbGlobal(newvar), SCIPvarGetUbGlobal(newvar), SCIPvarGetObj(newvar));
272
273 /* take care of statistics */
274 (*naggrvars)++;
275 *result = SCIP_SUCCESS;
276 }
277
278 /* release variable */
279 SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
280 }
281 }
282
283 /* free temporary memory */
285
286 return SCIP_OKAY;
287}
288
289
290/*
291 * presolver specific interface methods
292 */
293
294/** creates the boundshift presolver and includes it in SCIP */
296 SCIP* scip /**< SCIP data structure */
297 )
298{
299 SCIP_PRESOLDATA* presoldata;
300 SCIP_PRESOL* presolptr;
301
302 /* create boundshift presolver data */
303 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
304
305 /* include presolver */
307 presolExecBoundshift,
308 presoldata) );
309
310 assert(presolptr != NULL);
311
312 SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyBoundshift) );
313 SCIP_CALL( SCIPsetPresolFree(scip, presolptr, presolFreeBoundshift) );
314
315 /* add probing presolver parameters */
317 "presolving/boundshift/maxshift",
318 "absolute value of maximum shift",
319 &presoldata->maxshift, TRUE, DEFAULT_MAXSHIFT, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
320
322 "presolving/boundshift/flipping",
323 "is flipping allowed (multiplying with -1)?",
324 &presoldata->flipping, TRUE, DEFAULT_FLIPPING, NULL, NULL) );
325
327 "presolving/boundshift/integer",
328 "shift only integer ranges?",
329 &presoldata->integer, TRUE, DEFAULT_INTEGER, NULL, NULL) );
330
331 return SCIP_OKAY;
332}
methods for debugging
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:299
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:298
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define REALABS(x)
Definition: def.h:197
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPincludePresolBoundshift(SCIP *scip)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:522
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:512
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:156
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_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:17620
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8565
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8401
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
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_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4645
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4613
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:17630
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:114
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
memory allocation routines
#define PRESOL_NAME
#define DEFAULT_FLIPPING
static SCIP_DECL_PRESOLFREE(presolFreeBoundshift)
#define DEFAULT_INTEGER
static SCIP_DECL_PRESOLEXEC(presolExecBoundshift)
#define PRESOL_PRIORITY
#define DEFAULT_MAXSHIFT
static SCIP_DECL_PRESOLCOPY(presolCopyBoundshift)
#define MAXABSBOUND
#define PRESOL_MAXROUNDS
#define PRESOL_TIMING
#define PRESOL_DESC
presolver that converts integer variables with domain [a,b] to integer variables with domain [0,...
public methods for message output
public data structures and miscellaneous methods
public methods for presolvers
public methods for problem variables
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for SCIP variables
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:51
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62