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-2018 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 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 "blockmemshell/memory.h"
29 #include "scip/cons_knapsack.h"
31 #include "scip/pub_message.h"
32 #include "scip/pub_misc.h"
33 #include "scip/pub_presol.h"
34 #include "scip/pub_var.h"
35 #include "scip/scip_cons.h"
36 #include "scip/scip_mem.h"
37 #include "scip/scip_message.h"
38 #include "scip/scip_numerics.h"
39 #include "scip/scip_param.h"
40 #include "scip/scip_presol.h"
41 #include "scip/scip_prob.h"
42 #include "scip/scip_var.h"
43 #include <string.h>
44 
45 #define PRESOL_NAME "convertinttobin"
46 #define PRESOL_DESC "converts integer variables to binaries"
47 #define PRESOL_PRIORITY +6000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
48 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no
49  * limit) */
50 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
51 
52 #define DEFAULT_MAXDOMAINSIZE SCIP_LONGINT_MAX /**< absolute value of maximum domain size which will be converted */
53 #define DEFAULT_ONLYPOWERSOFTWO FALSE /**< should only integer variables with a domain size of 2^p - 1 be
54  * converted(, there we don't need an knapsack-constraint) */
55 #define DEFAULT_SAMELOCKSINBOTHDIRECTIONS FALSE /**< should only integer variables with uplocks equals downlocks be converted */
56 
57 /** presolver data */
58 struct SCIP_PresolData
59 {
60  SCIP_Longint maxdomainsize; /**< absolute value of maximum domain size */
61  SCIP_Bool onlypoweroftwo; /**< should only integer variables with a domain size of 2^p - 1 be converted */
62  SCIP_Bool samelocksinbothdirections; /**< should only integer variables with uplocks equals downlocks be converted */
63 };
64 
65 /*
66  * Callback methods of presolver
67  */
68 
69 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
70 static
71 SCIP_DECL_PRESOLCOPY(presolCopyConvertinttobin)
72 { /*lint --e{715}*/
73  assert(scip != NULL);
74  assert(presol != NULL);
75  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
76 
77  /* call inclusion method of presolver */
79 
80  return SCIP_OKAY;
81 }
82 
83 /** destructor of presolver to free user data (called when SCIP is exiting) */
84 static
85 SCIP_DECL_PRESOLFREE(presolFreeConvertinttobin)
86 { /*lint --e{715}*/
87  SCIP_PRESOLDATA* presoldata;
88 
89  /* free presolver data */
90  presoldata = SCIPpresolGetData(presol);
91  assert(presoldata != NULL);
92 
93  SCIPfreeBlockMemory(scip, &presoldata);
94  SCIPpresolSetData(presol, NULL);
95 
96  return SCIP_OKAY;
97 }
98 
99 /** presolving execution method */
100 static
101 SCIP_DECL_PRESOLEXEC(presolExecConvertinttobin)
102 { /*lint --e{715}*/
103  SCIP_VAR** scipvars;
104  SCIP_VAR** vars;
105  SCIP_PRESOLDATA* presoldata;
106  int nbinvars;
107  int nintvars;
108  int v;
109 
110  assert(scip != NULL);
111  assert(presol != NULL);
112  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
113  assert(result != NULL);
114 
115  *result = SCIP_DIDNOTRUN;
116 
117  /* get the problem variables */
118  scipvars = SCIPgetVars(scip);
119  nbinvars = SCIPgetNBinVars(scip);
120  nintvars = SCIPgetNIntVars(scip);
121  if( nintvars == 0 )
122  return SCIP_OKAY;
123 
124  /* get presolver data */
125  presoldata = SCIPpresolGetData(presol);
126  assert(presoldata != NULL);
127 
128  *result = SCIP_DIDNOTFIND;
129 
130  /* copy the integer variables into an own array, since adding binary variables affects the left-most slots in the
131  * array and thereby interferes with our search loop
132  */
133  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nintvars) );
134 
135  /* scan the integer variables for possible conversion into binaries;
136  * we have to collect the variables first in an own
137  */
138  for( v = 0; v < nintvars; ++v )
139  {
140  SCIP_VAR** newbinvars;
141  SCIP_Real* newbinvarcoeffs;
142  SCIP_Longint* weights;
143  SCIP_CONS* newcons;
144  SCIP_Real lb;
145  SCIP_Real ub;
146  SCIP_Longint domainsize;
147  char newbinvarname[SCIP_MAXSTRLEN];
148  char newconsname[SCIP_MAXSTRLEN];
149  int nnewbinvars;
150  int v2;
151  SCIP_Longint scalar;
152  SCIP_Bool infeasible;
153  SCIP_Bool aggregated;
154  SCIP_Bool noconsknapsack;
155 
156  assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER);
157 
158  /* skip variables which cannot be multi-aggregated */
159  if( SCIPdoNotMultaggrVar(scip, vars[v]) )
160  continue;
161 
162  /* check for correct locks */
163  if( presoldata->samelocksinbothdirections
165  continue;
166 
167  /* get variable's bounds */
168  lb = SCIPvarGetLbGlobal(vars[v]);
169  ub = SCIPvarGetUbGlobal(vars[v]);
170  assert( SCIPisIntegral(scip, lb) );
171  assert( SCIPisIntegral(scip, ub) );
172 
173  if( SCIPisInfinity(scip, ub - lb) )
174  domainsize = SCIP_LONGINT_MAX;
175  else
176  domainsize = (SCIP_Longint) SCIPceil(scip, ub - lb);
177 
178  assert(domainsize >= 0);
179 
180  /* check for allowed domainsize */
181  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) || domainsize > presoldata->maxdomainsize )
182  continue;
183 
184  /* check for domainsize is not 2^p - 1 if necessary */
185  if( presoldata->onlypoweroftwo )
186  {
187  /* stop if domainsize is not 2^p - 1*/
188  SCIP_Longint tmp;
189 
190  assert(domainsize < SCIP_LONGINT_MAX);
191  tmp = domainsize + 1;
192 
193  while( tmp % 2 == 0 )
194  tmp /= 2;
195  if( tmp != 1 )
196  continue;
197  }
198 
199  noconsknapsack = FALSE;
200 
201  nnewbinvars = (int)SCIPfloor(scip, (log((SCIP_Real) domainsize)/log(2.0))) + 1;
202 
203  SCIPdebugMsg(scip, "integer variable <%s> [%g,%g], domainsize %" SCIP_LONGINT_FORMAT "\n, <uplocks = %d, downlocks = %d will be 'binarized' by %d binary variables\n ",
204  SCIPvarGetName(vars[v]), lb, ub, domainsize, SCIPvarGetNLocksUpType(vars[v], SCIP_LOCKTYPE_MODEL),
205  SCIPvarGetNLocksDownType(vars[v], SCIP_LOCKTYPE_MODEL), nnewbinvars);
206 
207  assert(nnewbinvars > 0);
208 
209  scalar = (SCIP_Longint)pow(2.0, nnewbinvars); /*lint !e747*/
210  /* because of rounding errors */
211  if( scalar == domainsize )
212  {
213  scalar *= 2;
214  nnewbinvars++;
215  }
216  else if( scalar == domainsize + 1 )
217  noconsknapsack = TRUE;
218 
219  assert(scalar > domainsize);
220 
221  SCIP_CALL( SCIPallocBufferArray(scip, &newbinvars, nnewbinvars) );
222  SCIP_CALL( SCIPallocBufferArray(scip, &newbinvarcoeffs, nnewbinvars) );
223  SCIP_CALL( SCIPallocBufferArray(scip, &weights, nnewbinvars) );
224 
225  for( v2 = nnewbinvars - 1; v2 >= 0; --v2 )
226  {
227  SCIPdebugMsg(scip, "creating for <%s>[%g,%g] %d. binary variable\n", SCIPvarGetName(vars[v]), lb, ub, v2);
228 
229  /* create binary variable */
230  (void) SCIPsnprintf(newbinvarname, SCIP_MAXSTRLEN, "%s_bin_%d", SCIPvarGetName(vars[v]), v2);
231  SCIP_CALL( SCIPcreateVar(scip, &newbinvars[v2], newbinvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
232  SCIPvarIsInitial(vars[v]), SCIPvarIsRemovable(vars[v]), NULL, NULL, NULL, NULL, NULL) );
233  SCIP_CALL( SCIPaddVar(scip, newbinvars[v2]) );
234 
235  scalar /= 2;
236  assert(scalar > 0);
237 
238  newbinvarcoeffs[v2] = (SCIP_Real)scalar;
239  weights[v2] = scalar;
240  }
241 
242  /* aggregate integer and binary variable */
243  SCIP_CALL( SCIPmultiaggregateVar(scip, vars[v], nnewbinvars, newbinvars, (SCIP_Real*)newbinvarcoeffs, lb, &infeasible, &aggregated) );
244  assert(!infeasible);
245  assert(aggregated);
246 
247  (void) SCIPsnprintf(newconsname, SCIP_MAXSTRLEN, "%s_bin_knapsack", SCIPvarGetName(vars[v]));
248 
249  if( !noconsknapsack )
250  {
251  int nodd;
252  nodd = 0;
253  while( domainsize % 2 == 1 )
254  {
255  nodd++;
256  domainsize = (domainsize - 1) / 2;
257  }
258  if( nodd > 0 )
259  {
260  SCIP_Longint divisor;
261 
262  divisor = (SCIP_Longint)pow(2.0, nodd); /*lint !e747*/
263  assert(divisor >= 2);
264 
265  for( v2 = nodd; v2 < nnewbinvars; ++v2 )
266  {
267  weights[v2] /= divisor;
268  }
269  }
270 
271  SCIP_CALL( SCIPcreateConsKnapsack(scip, &newcons, newconsname, nnewbinvars - nodd, &newbinvars[nodd],
272  &weights[nodd], domainsize,
274  SCIP_CALL( SCIPaddCons(scip, newcons) );
275  SCIPdebugPrintCons(scip, newcons, NULL);
276  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
277  }
278 
279  for( v2 = nnewbinvars - 1; v2 >= 0; --v2 )
280  {
281  /* release binary variable */
282  SCIP_CALL( SCIPreleaseVar(scip, &newbinvars[v2]) );
283  (*nchgvartypes)++;
284  }
285 
286  SCIPfreeBufferArray(scip, &newbinvars);
287  SCIPfreeBufferArray(scip, &newbinvarcoeffs);
288  SCIPfreeBufferArray(scip, &weights);
289 
290  if( aggregated ) /*lint !e774*/
291  *result = SCIP_SUCCESS;
292  }
293 
294  /* free temporary memory */
295  SCIPfreeBufferArray(scip, &vars);
296 
297  return SCIP_OKAY;
298 }
299 
300 
301 /*
302  * presolver specific interface methods
303  */
304 
305 /** creates the convertinttobin presolver and includes it in SCIP */
307  SCIP* scip /**< SCIP data structure */
308  )
309 {
310  SCIP_PRESOLDATA* presoldata;
311  SCIP_PRESOL* presolptr;
312 
313  /* create convertinttobin presolver data */
314  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
315 
316  presoldata->maxdomainsize = DEFAULT_MAXDOMAINSIZE;
317  presoldata->onlypoweroftwo = DEFAULT_ONLYPOWERSOFTWO;
318 
319  /* include presolver */
321  presolExecConvertinttobin,
322  presoldata) );
323  assert(presolptr != NULL);
324 
325  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyConvertinttobin) );
326  SCIP_CALL( SCIPsetPresolFree(scip, presolptr, presolFreeConvertinttobin) );
327 
328  /* add convertinttobin presolver parameters */
330  "presolving/" PRESOL_NAME "/maxdomainsize",
331  "absolute value of maximum domain size for converting an integer variable to binaries variables",
332  &presoldata->maxdomainsize, TRUE, DEFAULT_MAXDOMAINSIZE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
333 
334  /* add convertinttobin presolver parameters */
336  "presolving/" PRESOL_NAME "/onlypoweroftwo",
337  "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)",
338  &presoldata->onlypoweroftwo, TRUE, DEFAULT_ONLYPOWERSOFTWO, NULL, NULL) );
339 
340  /* add convertinttobin presolver parameters */
342  "presolving/" PRESOL_NAME "/samelocksinbothdirections",
343  "should only integer variables with uplocks equals downlocks be converted",
344  &presoldata->samelocksinbothdirections, TRUE, DEFAULT_SAMELOCKSINBOTHDIRECTIONS, NULL, NULL) );
345 
346  return SCIP_OKAY;
347 }
presolver that converts integer variables with domain [a,a+1] to binaries
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:174
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2134
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
#define NULL
Definition: def.h:239
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:225
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3176
#define DEFAULT_MAXDOMAINSIZE
public methods for memory management
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
#define SCIP_MAXSTRLEN
Definition: def.h:260
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3233
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:16930
SCIPInterval pow(const SCIPInterval &x, const SCIPInterval &y)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
#define PRESOL_TIMING
#define FALSE
Definition: def.h:65
static SCIP_DECL_PRESOLCOPY(presolCopyConvertinttobin)
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:183
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:502
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:138
#define SCIP_LONGINT_MAX
Definition: def.h:136
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:16940
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:88
public methods for numerical tolerances
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17353
SCIP_RETCODE SCIPmultiaggregateVar(SCIP *scip, SCIP_VAR *var, int naggvars, SCIP_VAR **aggvars, SCIP_Real *scalars, SCIP_Real constant, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
Definition: scip_var.c:8411
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
SCIP_Bool SCIPdoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8461
#define DEFAULT_ONLYPOWERSOFTWO
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:512
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
#define PRESOL_DESC
#define DEFAULT_SAMELOCKSINBOTHDIRECTIONS
SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define SCIP_CALL(x)
Definition: def.h:351
#define PRESOL_NAME
public methods for constraint handler plugins and constraints
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
public data structures and miscellaneous methods
#define PRESOL_PRIORITY
#define SCIP_Bool
Definition: def.h:62
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:589
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:104
SCIPInterval log(const SCIPInterval &x)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2089
static SCIP_DECL_PRESOLFREE(presolFreeConvertinttobin)
#define SCIP_LONGINT_FORMAT
Definition: def.h:142
public methods for presolvers
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1724
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:209
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
#define PRESOL_MAXROUNDS
#define SCIP_Real
Definition: def.h:150
public methods for message handling
static SCIP_DECL_PRESOLEXEC(presolExecConvertinttobin)
#define SCIP_Longint
Definition: def.h:135
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16894
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
public methods for global and local (sub)problems
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
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:129
SCIP_RETCODE SCIPincludePresolConvertinttobin(SCIP *scip)
memory allocation routines