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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presol_boundshift.c
17  * @ingroup DEFPLUGINS_PRESOL
18  * @brief presolver that converts variables with domain [a,b] to variables with domain [0,b-a]
19  * @author Stefan Heinz
20  * @author Michael Winkler
21  */
22 
23 /**@todo test this presolving step to decide whether to turn it in default mode on or off */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #include "blockmemshell/memory.h"
28 #include "scip/presol_boundshift.h"
29 #include "scip/pub_message.h"
30 #include "scip/pub_misc.h"
31 #include "scip/pub_presol.h"
32 #include "scip/pub_var.h"
33 #include "scip/scip_mem.h"
34 #include "scip/scip_message.h"
35 #include "scip/scip_numerics.h"
36 #include "scip/scip_param.h"
37 #include "scip/scip_presol.h"
38 #include "scip/scip_prob.h"
39 #include "scip/scip_var.h"
40 #include <string.h>
41 
42 #define PRESOL_NAME "boundshift"
43 #define PRESOL_DESC "converts variables with domain [a,b] to variables with domain [0,b-a]"
44 #define PRESOL_PRIORITY 7900000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
45 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
46 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
47 
48 #define MAXABSBOUND 1000.0 /**< maximum absolute variable bounds for aggregation */
49 
50 /*
51  * Default parameter settings
52  */
53 
54 #define DEFAULT_MAXSHIFT SCIP_LONGINT_MAX /**< absolute value of maximum shift */
55 #define DEFAULT_FLIPPING TRUE /**< is flipping allowed? */
56 #define DEFAULT_INTEGER TRUE /**< are only integer ranges shifted */
57 
58 /*
59  * Data structures
60  */
61 
62 /** presolver data */
63 struct SCIP_PresolData
64 {
65  SCIP_Longint maxshift; /**< absolute value of maximum shift */
66  SCIP_Bool flipping; /**< is flipping allowed? */
67  SCIP_Bool integer; /**< shift only integer values? */
68 };
69 
70 
71 /*
72  * Local methods
73  */
74 
75 /** initializes the presolver data */
76 static
78  SCIP_PRESOLDATA* presoldata /**< presolver data */
79  )
80 {
81  assert(presoldata != NULL);
82 
83  presoldata->maxshift = DEFAULT_MAXSHIFT;
84  presoldata->flipping = DEFAULT_FLIPPING;
85  presoldata->integer = DEFAULT_INTEGER;
86 }
87 
88 /*
89  * Callback methods of presolver
90  */
91 
92 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
93 static
94 SCIP_DECL_PRESOLCOPY(presolCopyBoundshift)
95 { /*lint --e{715}*/
96  assert(scip != NULL);
97  assert(presol != NULL);
98  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
99 
100  /* call inclusion method of presolver */
102 
103  return SCIP_OKAY;
104 }
105 
106 
107 /** destructor of presolver to free user data (called when SCIP is exiting) */
108 /**! [SnippetPresolFreeBoundshift] */
109 static
110 SCIP_DECL_PRESOLFREE(presolFreeBoundshift)
111 { /*lint --e{715}*/
112  SCIP_PRESOLDATA* presoldata;
113 
114  /* free presolver data */
115  presoldata = SCIPpresolGetData(presol);
116  assert(presoldata != NULL);
117 
118  SCIPfreeBlockMemory(scip, &presoldata);
119  SCIPpresolSetData(presol, NULL);
120 
121  return SCIP_OKAY;
122 }
123 /**! [SnippetPresolFreeBoundshift] */
124 
125 
126 /** presolving execution method */
127 static
128 SCIP_DECL_PRESOLEXEC(presolExecBoundshift)
129 { /*lint --e{715}*/
130  SCIP_PRESOLDATA* presoldata;
131  SCIP_VAR** scipvars;
132  SCIP_VAR** vars;
133  int nbinvars;
134  int nvars;
135  int v;
136 
137  assert(scip != NULL);
138  assert(presol != NULL);
139  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
140  assert(result != NULL);
141 
142  *result = SCIP_DIDNOTRUN;
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  if( SCIPdoNotAggr(scip) )
157  return SCIP_OKAY;
158 
159  *result = SCIP_DIDNOTFIND;
160 
161  /* copy the integer variables into an own array, since adding new integer variables affects the left-most slots in
162  * the array and thereby interferes with our search loop
163  */
164  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nvars) );
165 
166  /* scan the integer, implicit, and continuous variables for possible conversion */
167  for( v = nvars - 1; v >= 0; --v )
168  {
169  SCIP_VAR* var = vars[v];
170  SCIP_Real lb;
171  SCIP_Real ub;
172 
173  assert(SCIPvarGetType(var) != SCIP_VARTYPE_BINARY);
174 
175  /* get current variable's bounds */
176  lb = SCIPvarGetLbGlobal(var);
177  ub = SCIPvarGetUbGlobal(var);
178 
179  /* it can happen that the variable bounds of integer variables have not been propagated yet or contain
180  * some small noise; this will result in an aggregation that might trigger assertions when updating bounds of
181  * aggregated variables (see #1817)
182  */
183  if( SCIPvarIsIntegral(var) )
184  {
185  assert(SCIPisIntegral(scip, lb));
186  assert(SCIPisIntegral(scip, ub));
187 
188  lb = SCIPadjustedVarLb(scip, var, lb);
189  ub = SCIPadjustedVarUb(scip, var, ub);
190  }
191 
192  assert( SCIPisLE(scip, lb, ub) );
193  if( SCIPisEQ(scip, lb, ub) )
194  continue;
195  if( presoldata->integer && !SCIPisIntegral(scip, ub - lb) )
196  continue;
197 
198  /* check if bounds are shiftable */
199  if( !SCIPisEQ(scip, lb, 0.0) && /* lower bound != 0.0 */
200  SCIPisLT(scip, ub, SCIPinfinity(scip)) && /* upper bound != infinity */
201  SCIPisGT(scip, lb, -SCIPinfinity(scip)) && /* lower bound != -infinity */
202  SCIPisLT(scip, ub - lb, (SCIP_Real) presoldata->maxshift) && /* less than max shifting */
203  SCIPisLE(scip, REALABS(lb), MAXABSBOUND) && /* ensures a small constant in aggregation */
204  SCIPisLE(scip, REALABS(ub), MAXABSBOUND) ) /* ensures a small constant in aggregation */
205  {
206  SCIP_VAR* newvar;
207  char newvarname[SCIP_MAXSTRLEN];
208  SCIP_Bool infeasible;
209  SCIP_Bool redundant;
210  SCIP_Bool aggregated;
211 
212  SCIPdebugMsg(scip, "convert range <%s>[%g,%g] to [%g,%g]\n", SCIPvarGetName(var), lb, ub, 0.0, (ub - lb) );
213 
214  /* create new variable */
215  (void) SCIPsnprintf(newvarname, SCIP_MAXSTRLEN, "%s_shift", SCIPvarGetName(var));
216  SCIP_CALL( SCIPcreateVar(scip, &newvar, newvarname, 0.0, (ub - lb), 0.0, SCIPvarGetType(var),
218  SCIP_CALL( SCIPaddVar(scip, newvar) );
219 
220  /* aggregate old variable with new variable */
221  if( presoldata->flipping )
222  {
223  if( REALABS(ub) < REALABS(lb) )
224  {
225  SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, 1.0, ub, &infeasible, &redundant, &aggregated) );
226  }
227  else
228  {
229  SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
230  }
231  }
232  else
233  {
234  SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
235  }
236 
237  assert(!infeasible);
238  assert(redundant);
239  assert(aggregated);
240  SCIPdebugMsg(scip, "var <%s> with bounds [%f,%f] has obj %f\n",
241  SCIPvarGetName(newvar),SCIPvarGetLbGlobal(newvar),SCIPvarGetUbGlobal(newvar),SCIPvarGetObj(newvar));
242 
243  /* release variable */
244  SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
245 
246  /* take care of statistic */
247  (*naggrvars)++;
248  *result = SCIP_SUCCESS;
249  }
250  }
251 
252  /* free temporary memory */
253  SCIPfreeBufferArray(scip, &vars);
254 
255  return SCIP_OKAY;
256 }
257 
258 
259 /*
260  * presolver specific interface methods
261  */
262 
263 /** creates the boundshift presolver and includes it in SCIP */
265  SCIP* scip /**< SCIP data structure */
266  )
267 {
268  SCIP_PRESOLDATA* presoldata;
269  SCIP_PRESOL* presolptr;
270 
271  /* create boundshift presolver data */
272  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
273  initPresoldata(presoldata);
274 
275  /* include presolver */
277  presolExecBoundshift,
278  presoldata) );
279 
280  assert(presolptr != NULL);
281 
282  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyBoundshift) );
283  SCIP_CALL( SCIPsetPresolFree(scip, presolptr, presolFreeBoundshift) );
284 
285  /* add probing presolver parameters */
287  "presolving/boundshift/maxshift",
288  "absolute value of maximum shift",
289  &presoldata->maxshift, TRUE, DEFAULT_MAXSHIFT, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
291  "presolving/boundshift/flipping",
292  "is flipping allowed (multiplying with -1)?",
293  &presoldata->flipping, TRUE, DEFAULT_FLIPPING, NULL, NULL) );
295  "presolving/boundshift/integer",
296  "shift only integer ranges?",
297  &presoldata->integer, TRUE, DEFAULT_INTEGER, NULL, NULL) );
298 
299  return SCIP_OKAY;
300 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:42
#define PRESOL_NAME
#define PRESOL_MAXROUNDS
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
public methods for SCIP parameter handling
public methods for memory management
#define SCIP_MAXSTRLEN
Definition: def.h:273
#define DEFAULT_FLIPPING
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
public methods for presolving plugins
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
#define PRESOL_PRIORITY
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17182
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_DECL_PRESOLEXEC(presolExecBoundshift)
public methods for problem variables
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4646
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:48
static void initPresoldata(SCIP_PRESOLDATA *presoldata)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
#define SCIP_LONGINT_MAX
Definition: def.h:149
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:69
static SCIP_DECL_PRESOLCOPY(presolCopyBoundshift)
public methods for numerical tolerances
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define PRESOL_TIMING
static SCIP_DECL_PRESOLFREE(presolFreeBoundshift)
SCIP_EXPORT SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:17218
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17208
#define DEFAULT_INTEGER
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:503
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:187
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPincludePresolBoundshift(SCIP *scip)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:130
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:513
#define PRESOL_DESC
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:590
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:105
#define DEFAULT_MAXSHIFT
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:146
public methods for presolvers
#define MAXABSBOUND
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
public methods for message output
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10590
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1252
#define SCIP_Real
Definition: def.h:163
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:95
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_Longint
Definition: def.h:148
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2031
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:102
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:8380
SCIP_EXPORT SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:17228
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8544
public methods for global and local (sub)problems
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4614
presolver that converts integer variables with domain [a,b] to integer variables with domain [0...
memory allocation routines