SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2023 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
92{ /*lint --e{715}*/
93 assert(scip != NULL);
94 assert(presol != NULL);
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
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);
117
118 return SCIP_OKAY;
119}
120/**! [SnippetPresolFreeBoundshift] */
121
122
123/** presolving execution method */
124static
126{ /*lint --e{715}*/
127 SCIP_PRESOLDATA* presoldata;
129 SCIP_VAR** vars;
130 int nbinvars;
131 int nvars;
132 int v;
133
134 assert(scip != NULL);
135 assert(presol != NULL);
137 assert(result != NULL);
138
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 */
152
153 if( nvars == 0 )
154 return SCIP_OKAY;
155
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 */
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
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 */
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 */
185 {
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 {
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 */
220
221#ifdef WITH_DEBUG_SOLUTION
223 {
224 /* calculate and store debug solution value of shift variable */
225 SCIP_Real val;
226
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
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 )
266 else
267 {
268 assert(redundant);
270 SCIPdebugMsg(scip, "var <%s> with bounds [%f,%f] has obj %f\n",
272
273 /* take care of statistics */
274 (*naggrvars)++;
276 }
277
278 /* release variable */
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;
301
302 /* create boundshift presolver data */
303 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
304
305 /* include presolver */
308 presoldata) );
309
311
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 SCIP_MAXSTRLEN
Definition def.h:302
#define TRUE
Definition def.h:95
#define REALABS(x)
Definition def.h:210
#define SCIP_LONGINT_MAX
Definition def.h:172
#define SCIP_CALL(x)
Definition def.h:388
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
#define SCIPdebugMsg
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
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition presol.c:522
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition presol.c:512
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
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)
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:17442
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:17570
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:17748
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
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:17432
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition var.c:17452
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:17900
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
int nbinvars
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define PRESOL_NAME
#define DEFAULT_FLIPPING
#define DEFAULT_INTEGER
#define PRESOL_PRIORITY
#define DEFAULT_MAXSHIFT
#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
#define SCIP_DECL_PRESOLCOPY(x)
Definition type_presol.h:60
struct SCIP_PresolData SCIP_PRESOLDATA
Definition type_presol.h:51
#define SCIP_DECL_PRESOLFREE(x)
Definition type_presol.h:68
#define SCIP_DECL_PRESOLEXEC(x)
@ 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
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62