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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presol_boundshift.c
17  * @brief presolver that converts variables with domain [a,b] to variables with domain [0,b-a]
18  * @author Stefan Heinz
19  * @author Michael Winkler
20  */
21 
22 /**@todo test this presolving step to decide whether to turn it in default mode on or off */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include <assert.h>
27 #include <string.h>
28 
29 #include "scip/presol_boundshift.h"
30 
31 
32 #define PRESOL_NAME "boundshift"
33 #define PRESOL_DESC "converts variables with domain [a,b] to variables with domain [0,b-a]"
34 #define PRESOL_PRIORITY 7900000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
35 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
36 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
37 
38 
39 /*
40  * Default parameter settings
41  */
42 
43 #define DEFAULT_MAXSHIFT SCIP_LONGINT_MAX /**< absolute value of maximum shift */
44 #define DEFAULT_FLIPPING TRUE /**< is flipping allowed? */
45 #define DEFAULT_INTEGER TRUE /**< are only integer ranges shifted */
46 
47 /*
48  * Data structures
49  */
50 
51 /** presolver data */
52 struct SCIP_PresolData
53 {
54  SCIP_Longint maxshift; /**< absolute value of maximum shift */
55  SCIP_Bool flipping; /**< is flipping allowed? */
56  SCIP_Bool integer; /**< shift only integer values? */
57 };
58 
59 
60 /*
61  * Local methods
62  */
63 
64 /** initializes the presolver data */
65 static
67  SCIP_PRESOLDATA* presoldata /**< presolver data */
68  )
69 {
70  assert(presoldata != NULL);
71 
72  presoldata->maxshift = DEFAULT_MAXSHIFT;
73  presoldata->flipping = DEFAULT_FLIPPING;
74  presoldata->integer = DEFAULT_INTEGER;
75 }
76 
77 /*
78  * Callback methods of presolver
79  */
80 
81 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
82 static
83 SCIP_DECL_PRESOLCOPY(presolCopyBoundshift)
84 { /*lint --e{715}*/
85  assert(scip != NULL);
86  assert(presol != NULL);
87  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
88 
89  /* call inclusion method of presolver */
91 
92  return SCIP_OKAY;
93 }
94 
95 
96 /** destructor of presolver to free user data (called when SCIP is exiting) */
97 /**! [SnippetPresolFreeBoundshift] */
98 static
99 SCIP_DECL_PRESOLFREE(presolFreeBoundshift)
100 { /*lint --e{715}*/
101  SCIP_PRESOLDATA* presoldata;
102 
103  /* free presolver data */
104  presoldata = SCIPpresolGetData(presol);
105  assert(presoldata != NULL);
106 
107  SCIPfreeBlockMemory(scip, &presoldata);
108  SCIPpresolSetData(presol, NULL);
109 
110  return SCIP_OKAY;
111 }
112 /**! [SnippetPresolFreeBoundshift] */
113 
114 
115 /** presolving execution method */
116 static
117 SCIP_DECL_PRESOLEXEC(presolExecBoundshift)
118 { /*lint --e{715}*/
119  SCIP_PRESOLDATA* presoldata;
120  SCIP_VAR** scipvars;
121  SCIP_VAR** vars;
122  int nbinvars;
123  int nvars;
124  int v;
125 
126  assert(scip != NULL);
127  assert(presol != NULL);
128  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
129  assert(result != NULL);
130 
131  *result = SCIP_DIDNOTRUN;
132 
133  /* get presolver data */
134  presoldata = SCIPpresolGetData(presol);
135  assert(presoldata != NULL);
136 
137  /* get the problem variables */
138  scipvars = SCIPgetVars(scip);
139  nbinvars = SCIPgetNBinVars(scip);
140  nvars = SCIPgetNVars(scip) - nbinvars;
141 
142  if( nvars == 0 )
143  return SCIP_OKAY;
144 
145  if( SCIPdoNotAggr(scip) )
146  return SCIP_OKAY;
147 
148  *result = SCIP_DIDNOTFIND;
149 
150  /* copy the integer variables into an own array, since adding new integer variables affects the left-most slots in
151  * the array and thereby interferes with our search loop
152  */
153  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nvars) );
154 
155  /* scan the integer, implicit, and continuous variables for possible conversion */
156  for( v = nvars - 1; v >= 0; --v )
157  {
158  SCIP_VAR* var = vars[v];
159  SCIP_Real lb;
160  SCIP_Real ub;
161 
162  assert(SCIPvarGetType(var) != SCIP_VARTYPE_BINARY);
163 
164  /* get current variable's bounds */
165  lb = SCIPvarGetLbGlobal(var);
166  ub = SCIPvarGetUbGlobal(var);
167 
168  assert( SCIPisLE(scip, lb, ub) );
169  if( SCIPisEQ(scip, lb, ub) )
170  continue;
171  if( presoldata->integer && !SCIPisIntegral(scip, ub - lb) )
172  continue;
173 
174  /* check if bounds are shiftable */
175  if( !SCIPisEQ(scip, lb, 0.0) && /* lower bound != 0.0 */
176  SCIPisLT(scip, ub, SCIPinfinity(scip)) && /* upper bound != infinity */
177  SCIPisGT(scip, lb, -SCIPinfinity(scip)) && /* lower bound != -infinity */
178 #if 0
179  SCIPisLT(scip, ub - lb, SCIPinfinity(scip)) && /* interval length less than SCIPinfinity(scip) */
180 #endif
181  SCIPisLT(scip, ub - lb, (SCIP_Real) presoldata->maxshift) ) /* less than max shifting */
182  {
183  SCIP_VAR* newvar;
184  char newvarname[SCIP_MAXSTRLEN];
185  SCIP_Bool infeasible;
186  SCIP_Bool redundant;
187  SCIP_Bool aggregated;
188 
189  SCIPdebugMsg(scip, "convert range <%s>[%g,%g] to [%g,%g]\n", SCIPvarGetName(var), lb, ub, 0.0, (ub - lb) );
190 
191  /* create new variable */
192  (void) SCIPsnprintf(newvarname, SCIP_MAXSTRLEN, "%s_shift", SCIPvarGetName(var));
193  SCIP_CALL( SCIPcreateVar(scip, &newvar, newvarname, 0.0, (ub - lb), 0.0, SCIPvarGetType(var),
195  SCIP_CALL( SCIPaddVar(scip, newvar) );
196 
197  /* aggregate old variable with new variable */
198  if( presoldata->flipping )
199  {
200  if( REALABS(ub) < REALABS(lb) )
201  {
202  SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, 1.0, ub, &infeasible, &redundant, &aggregated) );
203  }
204  else
205  {
206  SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
207  }
208  }
209  else
210  {
211  SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
212  }
213 
214  assert(!infeasible);
215  assert(redundant);
216  assert(aggregated);
217  SCIPdebugMsg(scip, "var <%s> with bounds [%f,%f] has obj %f\n",
218  SCIPvarGetName(newvar),SCIPvarGetLbGlobal(newvar),SCIPvarGetUbGlobal(newvar),SCIPvarGetObj(newvar));
219 
220  /* release variable */
221  SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
222 
223  /* take care of statistic */
224  (*naggrvars)++;
225  *result = SCIP_SUCCESS;
226  }
227  }
228 
229  /* free temporary memory */
230  SCIPfreeBufferArray(scip, &vars);
231 
232  return SCIP_OKAY;
233 }
234 
235 
236 /*
237  * presolver specific interface methods
238  */
239 
240 /** creates the boundshift presolver and includes it in SCIP */
242  SCIP* scip /**< SCIP data structure */
243  )
244 {
245  SCIP_PRESOLDATA* presoldata;
246  SCIP_PRESOL* presolptr;
247 
248  /* create boundshift presolver data */
249  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
250  initPresoldata(presoldata);
251 
252  /* include presolver */
254  presolExecBoundshift,
255  presoldata) );
256 
257  assert(presolptr != NULL);
258 
259  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyBoundshift) );
260  SCIP_CALL( SCIPsetPresolFree(scip, presolptr, presolFreeBoundshift) );
261 
262  /* add probing presolver parameters */
264  "presolving/boundshift/maxshift",
265  "absolute value of maximum shift",
266  &presoldata->maxshift, TRUE, DEFAULT_MAXSHIFT, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
268  "presolving/boundshift/flipping",
269  "is flipping allowed (multiplying with -1)?",
270  &presoldata->flipping, TRUE, DEFAULT_FLIPPING, NULL, NULL) );
272  "presolving/boundshift/integer",
273  "shift only integer ranges?",
274  &presoldata->integer, TRUE, DEFAULT_INTEGER, NULL, NULL) );
275 
276  return SCIP_OKAY;
277 }
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.c:6889
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
#define PRESOL_NAME
#define PRESOL_MAXROUNDS
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip.c:6940
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
#define SCIP_MAXSTRLEN
Definition: def.h:225
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:16756
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18461
#define DEFAULT_FLIPPING
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.c:4265
#define PRESOL_PRIORITY
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:46050
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPincludePresolBoundshift(SCIP *scip)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:466
static SCIP_DECL_PRESOLEXEC(presolExecBoundshift)
static void initPresoldata(SCIP_PRESOLDATA *presoldata)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21999
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
#define SCIP_LONGINT_MAX
Definition: def.h:131
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:16766
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
#define SCIPdebugMsg
Definition: scip.h:451
static SCIP_DECL_PRESOLCOPY(presolCopyBoundshift)
#define PRESOL_TIMING
static SCIP_DECL_PRESOLFREE(presolFreeBoundshift)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
#define DEFAULT_INTEGER
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45998
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:476
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:169
#define SCIP_CALL(x)
Definition: def.h:316
#define PRESOL_DESC
#define SCIP_Bool
Definition: def.h:61
#define DEFAULT_MAXSHIFT
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
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.c:17314
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11725
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11680
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46134
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:11360
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6924
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11635
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.c:25344
#define SCIP_Real
Definition: def.h:145
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip.c:25508
#define SCIP_Longint
Definition: def.h:130
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16720
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46011
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.c:4211
presolver that converts integer variables with domain [a,b] to integer variables with domain [0...