Scippy

SCIP

Solving Constraint Integer Programs

presol_convertinttobin.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-2014 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_convertinttobin.c
17  * @ingroup PRESOLVERS
18  * @brief presolver that converts integer variables to binaries
19  * @author Michael Winkler
20  *
21  * Converts integer variables at the beginning of Presolving into their binary representation. If necessary adds a
22  * bounding knapsack constraint.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include <assert.h>
29 #include <string.h>
30 
32 #include "scip/cons_knapsack.h"
33 #include "scip/pub_misc.h"
34 
35 
36 #define PRESOL_NAME "convertinttobin"
37 #define PRESOL_DESC "converts integer variables to binaries"
38 #define PRESOL_PRIORITY +6000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
39 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no
40  * limit) */
41 #define PRESOL_DELAY FALSE /**< should presolver be delayed, if other presolvers found reductions? */
42 
43 #define DEFAULT_MAXDOMAINSIZE SCIP_LONGINT_MAX /**< absolute value of maximum domain size which will be converted */
44 #define DEFAULT_ONLYPOWERSOFTWO FALSE /**< should only integer variables with a domain size of 2^p - 1 be
45  * converted(, there we don't need an knapsack-constraint) */
46 #define DEFAULT_SAMELOCKSINBOTHDIRECTIONS FALSE /**< should only integer variables with uplocks equals downlocks be converted */
47 
48 /** presolver data */
49 struct SCIP_PresolData
50 {
51  SCIP_Longint maxdomainsize; /**< absolute value of maximum domain size */
52  SCIP_Bool onlypoweroftwo; /**< should only integer variables with a domain size of 2^p - 1 be converted */
53  SCIP_Bool samelocksinbothdirections; /**< should only integer variables with uplocks equals downlocks be converted */
54 };
55 
56 /*
57  * Callback methods of presolver
58  */
59 
60 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
61 static
62 SCIP_DECL_PRESOLCOPY(presolCopyConvertinttobin)
63 { /*lint --e{715}*/
64  assert(scip != NULL);
65  assert(presol != NULL);
66  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
67 
68  /* call inclusion method of presolver */
70 
71  return SCIP_OKAY;
72 }
73 
74 /** destructor of presolver to free user data (called when SCIP is exiting) */
75 static
76 SCIP_DECL_PRESOLFREE(presolFreeConvertinttobin)
77 { /*lint --e{715}*/
78  SCIP_PRESOLDATA* presoldata;
79 
80  /* free presolver data */
81  presoldata = SCIPpresolGetData(presol);
82  assert(presoldata != NULL);
83 
84  SCIPfreeMemory(scip, &presoldata);
85  SCIPpresolSetData(presol, NULL);
86 
87  return SCIP_OKAY;
88 }
89 
90 /** presolving execution method */
91 static
92 SCIP_DECL_PRESOLEXEC(presolExecConvertinttobin)
93 { /*lint --e{715}*/
94  SCIP_VAR** scipvars;
95  SCIP_VAR** vars;
96  SCIP_PRESOLDATA* presoldata;
97  int nbinvars;
98  int nintvars;
99  int v;
100 
101  assert(scip != NULL);
102  assert(presol != NULL);
103  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
104  assert(result != NULL);
105 
106  *result = SCIP_DIDNOTRUN;
107 
108  /* get the problem variables */
109  scipvars = SCIPgetVars(scip);
110  nbinvars = SCIPgetNBinVars(scip);
111  nintvars = SCIPgetNIntVars(scip);
112  if( nintvars == 0 )
113  return SCIP_OKAY;
114 
115  /* get presolver data */
116  presoldata = SCIPpresolGetData(presol);
117  assert(presoldata != NULL);
118 
119  *result = SCIP_DIDNOTFIND;
120 
121  /* copy the integer variables into an own array, since adding binary variables affects the left-most slots in the
122  * array and thereby interferes with our search loop
123  */
124  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nintvars) );
125 
126  /* scan the integer variables for possible conversion into binaries;
127  * we have to collect the variables first in an own
128  */
129  for( v = 0; v < nintvars; ++v )
130  {
131  SCIP_VAR** newbinvars;
132  SCIP_Real* newbinvarcoeffs;
133  SCIP_Longint* weights;
134  SCIP_CONS* newcons;
135  SCIP_Real lb;
136  SCIP_Real ub;
137  SCIP_Longint domainsize;
138  char newbinvarname[SCIP_MAXSTRLEN];
139  char newconsname[SCIP_MAXSTRLEN];
140  int nnewbinvars;
141  int v2;
142  SCIP_Longint scalar;
143  SCIP_Bool infeasible;
144  SCIP_Bool aggregated;
145  SCIP_Bool noconsknapsack;
146 
147  assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER);
148 
149  /* skip variables which cannot be multi-aggregated */
150  if( SCIPdoNotMultaggrVar(scip, vars[v]) )
151  continue;
152 
153  /* check for correct locks */
154  if( presoldata->samelocksinbothdirections && SCIPvarGetNLocksUp(vars[v]) != SCIPvarGetNLocksDown(vars[v]) )
155  continue;
156 
157  /* get variable's bounds */
158  lb = SCIPvarGetLbGlobal(vars[v]);
159  ub = SCIPvarGetUbGlobal(vars[v]);
160  assert( SCIPisIntegral(scip, lb) );
161  assert( SCIPisIntegral(scip, ub) );
162 
163  if( SCIPisInfinity(scip, ub - lb) )
164  domainsize = SCIP_LONGINT_MAX;
165  else
166  domainsize = (SCIP_Longint) SCIPceil(scip, ub - lb);
167 
168  assert(domainsize >= 0);
169 
170  /* check for allowed domainsize */
171  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) || domainsize > presoldata->maxdomainsize )
172  continue;
173 
174  /* check for domainsize is not 2^p - 1 if necessary */
175  if( presoldata->onlypoweroftwo )
176  {
177  /* stop if domainsize is not 2^p - 1*/
178  SCIP_Longint tmp;
179 
180  assert(domainsize < SCIP_LONGINT_MAX);
181  tmp = domainsize + 1;
182 
183  while( tmp%2 == 0 )
184  tmp /= 2;
185  if( tmp != 1 )
186  continue;
187  }
188 
189  noconsknapsack = FALSE;
190 
191  nnewbinvars = (int)SCIPfloor(scip, (log((SCIP_Real) domainsize)/log(2.0))) + 1;
192 
193  SCIPdebugMessage("integer variable <%s> [%g,%g], domainsize %"SCIP_LONGINT_FORMAT"\n, <uplocks = %d, downlocks = %d will be 'binarized' by %d binary variables\n ",
194  SCIPvarGetName(vars[v]), lb, ub, domainsize, SCIPvarGetNLocksUp(vars[v]), SCIPvarGetNLocksDown(vars[v]), nnewbinvars);
195 
196  assert(nnewbinvars > 0);
197 
198  scalar = (SCIP_Longint)pow(2.0, nnewbinvars); /*lint !e747*/
199  /* because of rounding errors */
200  if( scalar == domainsize )
201  {
202  scalar *= 2;
203  nnewbinvars++;
204  }
205  else if( scalar == domainsize + 1 )
206  noconsknapsack = TRUE;
207 
208  assert(scalar > domainsize);
209 
210  SCIP_CALL( SCIPallocBufferArray(scip, &newbinvars, nnewbinvars) );
211  SCIP_CALL( SCIPallocBufferArray(scip, &newbinvarcoeffs, nnewbinvars) );
212  SCIP_CALL( SCIPallocBufferArray(scip, &weights, nnewbinvars) );
213 
214  for( v2 = nnewbinvars - 1; v2 >= 0; --v2 )
215  {
216  SCIPdebugMessage("creating for <%s>[%g,%g] %d. binary variable\n", SCIPvarGetName(vars[v]), lb, ub, v2);
217 
218  /* create binary variable */
219  (void) SCIPsnprintf(newbinvarname, SCIP_MAXSTRLEN, "%s_bin_%d", SCIPvarGetName(vars[v]), v2);
220  SCIP_CALL( SCIPcreateVar(scip, &newbinvars[v2], newbinvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
221  SCIPvarIsInitial(vars[v]), SCIPvarIsRemovable(vars[v]), NULL, NULL, NULL, NULL, NULL) );
222  SCIP_CALL( SCIPaddVar(scip, newbinvars[v2]) );
223 
224  scalar /= 2;
225  assert(scalar > 0);
226 
227  newbinvarcoeffs[v2] = (SCIP_Real)scalar;
228  weights[v2] = scalar;
229  }
230 
231  /* aggregate integer and binary variable */
232  SCIP_CALL( SCIPmultiaggregateVar(scip, vars[v], nnewbinvars, newbinvars, (SCIP_Real*)newbinvarcoeffs, lb, &infeasible, &aggregated) );
233  assert(!infeasible);
234  assert(aggregated);
235 
236  (void) SCIPsnprintf(newconsname, SCIP_MAXSTRLEN, "%s_bin_knapsack", SCIPvarGetName(vars[v]));
237 
238  if( !noconsknapsack )
239  {
240  int nodd;
241  nodd = 0;
242  while( domainsize % 2 == 1 )
243  {
244  nodd++;
245  domainsize = (domainsize - 1) / 2;
246  }
247  if( nodd > 0 )
248  {
249  SCIP_Longint divisor;
250 
251  divisor = (SCIP_Longint)pow(2.0, nodd); /*lint !e747*/
252  assert(divisor >= 2);
253 
254  for( v2 = nodd; v2 < nnewbinvars; ++v2 )
255  {
256  weights[v2] /= divisor;
257  }
258  }
259 
260  SCIP_CALL( SCIPcreateConsKnapsack(scip, &newcons, newconsname, nnewbinvars - nodd, &newbinvars[nodd],
261  &weights[nodd], domainsize,
263  SCIP_CALL( SCIPaddCons(scip, newcons) );
264  SCIPdebugPrintCons(scip, newcons, NULL);
265  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
266  }
267 
268  for( v2 = nnewbinvars - 1; v2 >= 0; --v2 )
269  {
270  /* release binary variable */
271  SCIP_CALL( SCIPreleaseVar(scip, &newbinvars[v2]) );
272  (*nchgvartypes)++;
273  }
274 
275  SCIPfreeBufferArray(scip, &newbinvars);
276  SCIPfreeBufferArray(scip, &newbinvarcoeffs);
277  SCIPfreeBufferArray(scip, &weights);
278 
279  if( aggregated ) /*lint !e774*/
280  *result = SCIP_SUCCESS;
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 convertinttobin 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 convertinttobin presolver data */
303  SCIP_CALL( SCIPallocMemory(scip, &presoldata) );
304 
305  presoldata->maxdomainsize = DEFAULT_MAXDOMAINSIZE;
306  presoldata->onlypoweroftwo = DEFAULT_ONLYPOWERSOFTWO;
307 
308  /* include presolver */
310  presolExecConvertinttobin,
311  presoldata) );
312  assert(presolptr != NULL);
313 
314  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyConvertinttobin) );
315  SCIP_CALL( SCIPsetPresolFree(scip, presolptr, presolFreeConvertinttobin) );
316 
317  /* add convertinttobin presolver parameters */
319  "presolving/"PRESOL_NAME"/maxdomainsize",
320  "absolute value of maximum domain size for converting an integer variable to binaries variables",
321  &presoldata->maxdomainsize, TRUE, DEFAULT_MAXDOMAINSIZE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
322 
323  /* add convertinttobin presolver parameters */
325  "presolving/"PRESOL_NAME"/onlypoweroftwo",
326  "should only integer variables with a domain size of 2^p - 1 be converted(, there we don't need an knapsack-constraint for restricting the sum of the binaries)",
327  &presoldata->onlypoweroftwo, TRUE, DEFAULT_ONLYPOWERSOFTWO, NULL, NULL) );
328 
329  /* add convertinttobin presolver parameters */
331  "presolving/"PRESOL_NAME"/samelocksinbothdirections",
332  "should only integer variables with uplocks equals downlocks be converted",
333  &presoldata->samelocksinbothdirections, TRUE, DEFAULT_SAMELOCKSINBOTHDIRECTIONS, NULL, NULL) );
334 
335  return SCIP_OKAY;
336 }
337