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