Scippy

SCIP

Solving Constraint Integer Programs

presol_inttobinary.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_inttobinary.c
17  * @brief presolver that converts integer variables with domain [a,a+1] to binaries
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "scip/presol_inttobinary.h"
27 
28 
29 #define PRESOL_NAME "inttobinary"
30 #define PRESOL_DESC "converts integer variables with domain [a,a+1] to binaries"
31 #define PRESOL_PRIORITY +7000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
32 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
33 #define PRESOL_DELAY FALSE /**< should presolver be delayed, if other presolvers found reductions? */
34 
35 
36 /*
37  * Callback methods of presolver
38  */
39 
40 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
41 static
42 SCIP_DECL_PRESOLCOPY(presolCopyInttobinary)
43 { /*lint --e{715}*/
44  assert(scip != NULL);
45  assert(presol != NULL);
46  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
47 
48  /* call inclusion method of presolver */
49  SCIP_CALL( SCIPincludePresolInttobinary(scip) );
50 
51  return SCIP_OKAY;
52 }
53 
54 
55 /** presolving execution method */
56 static
57 SCIP_DECL_PRESOLEXEC(presolExecInttobinary)
58 { /*lint --e{715}*/
59  SCIP_VAR** scipvars;
60  SCIP_VAR** vars;
61  int nbinvars;
62  int nintvars;
63  int v;
64 
65  assert(result != NULL);
66 
67  *result = SCIP_DIDNOTRUN;
68 
69  if( SCIPdoNotAggr(scip) )
70  return SCIP_OKAY;
71 
72  /* get the problem variables */
73  scipvars = SCIPgetVars(scip);
74  nbinvars = SCIPgetNBinVars(scip);
75  nintvars = SCIPgetNIntVars(scip);
76  if( nintvars == 0 )
77  return SCIP_OKAY;
78 
79  *result = SCIP_DIDNOTFIND;
80 
81  /* copy the integer variables into an own array, since adding binary variables affects the left-most slots in the
82  * array and thereby interferes with our search loop
83  */
84  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nintvars) );
85 
86  /* scan the integer variables for possible conversion into binaries;
87  * we have to collect the variables first in an own
88  */
89  for( v = 0; v < nintvars; ++v )
90  {
91  SCIP_Real lb;
92  SCIP_Real ub;
93 
94  assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER);
95 
96  /* get variable's bounds */
97  lb = SCIPvarGetLbGlobal(vars[v]);
98  ub = SCIPvarGetUbGlobal(vars[v]);
99 
100  /* check if bounds are exactly one apart */
101  if( SCIPisEQ(scip, lb, ub - 1.0) )
102  {
103  SCIP_VAR* binvar;
104  char binvarname[SCIP_MAXSTRLEN];
105  SCIP_Bool infeasible;
106  SCIP_Bool redundant;
107  SCIP_Bool aggregated;
108 
109  SCIPdebugMessage("converting <%s>[%g,%g] into binary variable\n", SCIPvarGetName(vars[v]), lb, ub);
110 
111  /* create binary variable */
112  (void) SCIPsnprintf(binvarname, SCIP_MAXSTRLEN, "%s_bin", SCIPvarGetName(vars[v]));
113  SCIP_CALL( SCIPcreateVar(scip, &binvar, binvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
114  SCIPvarIsInitial(vars[v]), SCIPvarIsRemovable(vars[v]), NULL, NULL, NULL, NULL, NULL) );
115  SCIP_CALL( SCIPaddVar(scip, binvar) );
116 
117  /* aggregate integer and binary variable */
118  SCIP_CALL( SCIPaggregateVars(scip, vars[v], binvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
119 
120  /* release binary variable */
121  SCIP_CALL( SCIPreleaseVar(scip, &binvar) );
122 
123  /* it can be the case that this aggregation detects an infeasibility; for example, during the copy of the
124  * variable bounds from the integer variable to the binary variable, infeasibility can be detected; this can
125  * happen because an upper bound or a lower bound of such a variable bound variable was "just" changed and the
126  * varbound constraint handler, who would detect that infeasibility (since it was creating it from a varbound
127  * constraint), was called before that bound change was detected due to the presolving priorities;
128  */
129  if( infeasible )
130  {
131  *result = SCIP_CUTOFF;
132  break;
133  }
134 
135  assert(redundant);
136  assert(aggregated);
137  (*nchgvartypes)++;
138  ++(*naggrvars);
139  *result = SCIP_SUCCESS;
140  }
141  }
142 
143  /* free temporary memory */
144  SCIPfreeBufferArray(scip, &vars);
145 
146  return SCIP_OKAY;
147 }
148 
149 
150 /*
151  * presolver specific interface methods
152  */
153 
154 /** creates the inttobinary presolver and includes it in SCIP */
155 SCIP_RETCODE SCIPincludePresolInttobinary(
156  SCIP* scip /**< SCIP data structure */
157  )
158 {
159  SCIP_PRESOLDATA* presoldata;
160  SCIP_PRESOL* presolptr;
161 
162  /* create inttobinary presolver data */
163  presoldata = NULL;
164 
165  /* include presolver */
166  SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_DELAY,
167  presolExecInttobinary,
168  presoldata) );
169 
170  assert(presolptr != NULL);
171 
172  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyInttobinary) );
173 
174  return SCIP_OKAY;
175 }
176