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 2002-2022 Zuse Institute Berlin */
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 
36 #include "blockmemshell/memory.h"
37 #include "scip/presol_boundshift.h"
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 */
73 struct 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) */
90 static
91 SCIP_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] */
106 static
107 SCIP_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 */
124 static
125 SCIP_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 */
284  SCIPfreeBufferArray(scip, &vars);
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 }
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
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:51
#define PRESOL_NAME
#define PRESOL_MAXROUNDS
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:156
public methods for SCIP parameter handling
public methods for memory management
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17919
#define SCIP_MAXSTRLEN
Definition: def.h:302
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:17461
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1254
#define DEFAULT_FLIPPING
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4651
public methods for presolving plugins
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
#define PRESOL_PRIORITY
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10764
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_RETCODE SCIPincludePresolBoundshift(SCIP *scip)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:512
static SCIP_DECL_PRESOLEXEC(presolExecBoundshift)
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_LONGINT_MAX
Definition: def.h:172
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4619
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:17471
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
public methods for SCIP variables
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
static SCIP_DECL_PRESOLCOPY(presolCopyBoundshift)
public methods for numerical tolerances
#define PRESOL_TIMING
static SCIP_DECL_PRESOLFREE(presolFreeBoundshift)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17929
#define DEFAULT_INTEGER
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:522
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17260
#define NULL
Definition: lpi_spx1.cpp:164
#define REALABS(x)
Definition: def.h:210
#define SCIP_CALL(x)
Definition: def.h:393
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:299
#define PRESOL_DESC
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:93
methods for debugging
#define DEFAULT_MAXSHIFT
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17767
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
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2045
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2000
public methods for presolvers
#define MAXABSBOUND
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1676
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:1955
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:8407
#define SCIP_Real
Definition: def.h:186
public methods for message handling
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8571
#define SCIP_Longint
Definition: def.h:171
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:298
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17425
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for global and local (sub)problems
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17451
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_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17589
presolver that converts integer variables with domain [a,b] to integer variables with domain [0...
memory allocation routines