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-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_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 
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_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
34 
35 /*
36  * Callback methods of presolver
37  */
38 
39 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
40 static
41 SCIP_DECL_PRESOLCOPY(presolCopyInttobinary)
42 { /*lint --e{715}*/
43  assert(scip != NULL);
44  assert(presol != NULL);
45  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
46 
47  /* call inclusion method of presolver */
49 
50  return SCIP_OKAY;
51 }
52 
53 
54 /** presolving execution method */
55 static
56 SCIP_DECL_PRESOLEXEC(presolExecInttobinary)
57 { /*lint --e{715}*/
58  SCIP_VAR** scipvars;
59  SCIP_VAR** vars;
60  int nbinvars;
61  int nintvars;
62  int v;
63 
64  assert(result != NULL);
65 
66  *result = SCIP_DIDNOTRUN;
67 
68  if( SCIPdoNotAggr(scip) )
69  return SCIP_OKAY;
70 
71  /* get the problem variables */
72  scipvars = SCIPgetVars(scip);
73  nbinvars = SCIPgetNBinVars(scip);
74  nintvars = SCIPgetNIntVars(scip);
75  if( nintvars == 0 )
76  return SCIP_OKAY;
77 
78  *result = SCIP_DIDNOTFIND;
79 
80  /* copy the integer variables into an own array, since adding binary variables affects the left-most slots in the
81  * array and thereby interferes with our search loop
82  */
83  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nintvars) );
84 
85  /* scan the integer variables for possible conversion into binaries;
86  * we have to collect the variables first in an own
87  */
88  for( v = 0; v < nintvars; ++v )
89  {
90  SCIP_Real lb;
91  SCIP_Real ub;
92 
93  assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER);
94 
95  /* get variable's bounds */
96  lb = SCIPvarGetLbGlobal(vars[v]);
97  ub = SCIPvarGetUbGlobal(vars[v]);
98 
99  /* check if bounds are exactly one apart */
100  if( SCIPisEQ(scip, lb, ub - 1.0) )
101  {
102  SCIP_VAR* binvar;
103  char binvarname[SCIP_MAXSTRLEN];
104  SCIP_Bool infeasible;
105  SCIP_Bool redundant;
106  SCIP_Bool aggregated;
107 
108  SCIPdebugMsg(scip, "converting <%s>[%g,%g] into binary variable\n", SCIPvarGetName(vars[v]), lb, ub);
109 
110  /* create binary variable */
111  (void) SCIPsnprintf(binvarname, SCIP_MAXSTRLEN, "%s_bin", SCIPvarGetName(vars[v]));
112  SCIP_CALL( SCIPcreateVar(scip, &binvar, binvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
113  SCIPvarIsInitial(vars[v]), SCIPvarIsRemovable(vars[v]), NULL, NULL, NULL, NULL, NULL) );
114  SCIP_CALL( SCIPaddVar(scip, binvar) );
115 
116  /* aggregate integer and binary variable */
117  SCIP_CALL( SCIPaggregateVars(scip, vars[v], binvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
118 
119  /* release binary variable */
120  SCIP_CALL( SCIPreleaseVar(scip, &binvar) );
121 
122  /* it can be the case that this aggregation detects an infeasibility; for example, during the copy of the
123  * variable bounds from the integer variable to the binary variable, infeasibility can be detected; this can
124  * happen because an upper bound or a lower bound of such a variable bound variable was "just" changed and the
125  * varbound constraint handler, who would detect that infeasibility (since it was creating it from a varbound
126  * constraint), was called before that bound change was detected due to the presolving priorities;
127  */
128  if( infeasible )
129  {
130  *result = SCIP_CUTOFF;
131  break;
132  }
133 
134  assert(redundant);
135  assert(aggregated);
136  (*nchgvartypes)++;
137  ++(*naggrvars);
138  *result = SCIP_SUCCESS;
139  }
140  }
141 
142  /* free temporary memory */
143  SCIPfreeBufferArray(scip, &vars);
144 
145  return SCIP_OKAY;
146 }
147 
148 
149 /*
150  * presolver specific interface methods
151  */
152 
153 /** creates the inttobinary presolver and includes it in SCIP */
155  SCIP* scip /**< SCIP data structure */
156  )
157 {
158  SCIP_PRESOLDATA* presoldata;
159  SCIP_PRESOL* presolptr;
160 
161  /* create inttobinary presolver data */
162  presoldata = NULL;
163 
164  /* include presolver */
166  presolExecInttobinary,
167  presoldata) );
168 
169  assert(presolptr != NULL);
170 
171  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyInttobinary) );
172 
173  return SCIP_OKAY;
174 }
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:6917
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11896
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
#define SCIP_MAXSTRLEN
Definition: def.h:259
#define PRESOL_DESC
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:16863
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18760
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:22628
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:16873
#define SCIPdebugMsg
Definition: scip.h:455
static SCIP_DECL_PRESOLEXEC(presolExecInttobinary)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
#define SCIP_CALL(x)
Definition: def.h:350
#define PRESOL_TIMING
#define SCIP_Bool
Definition: def.h:61
#define PRESOL_NAME
#define PRESOL_PRIORITY
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
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:17613
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11851
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:11486
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6952
#define PRESOL_MAXROUNDS
static SCIP_DECL_PRESOLCOPY(presolCopyInttobinary)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
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:25678
#define SCIP_Real
Definition: def.h:149
SCIP_RETCODE SCIPincludePresolInttobinary(SCIP *scip)
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip.c:25842
presolver that converts integer variables with domain [a,a+1] to binaries
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827