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