Scippy

SCIP

Solving Constraint Integer Programs

presol_implics.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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file presol_implics.c
26 * @ingroup DEFPLUGINS_PRESOL
27 * @brief implics presolver
28 * @author Tobias Achterberg
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
34#include "scip/presol_implics.h"
35#include "scip/pub_message.h"
36#include "scip/pub_presol.h"
37#include "scip/pub_var.h"
38#include "scip/scip_mem.h"
39#include "scip/scip_message.h"
40#include "scip/scip_numerics.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 "implics"
47#define PRESOL_DESC "implication graph aggregator"
48#define PRESOL_PRIORITY -10000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
49#define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
50#define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */
51
52
53/*
54 * Callback methods of presolver
55 */
56
57/** copy method for constraint handler plugins (called when SCIP copies plugins) */
58static
59SCIP_DECL_PRESOLCOPY(presolCopyImplics)
60{ /*lint --e{715}*/
61 assert(scip != NULL);
62 assert(presol != NULL);
63 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
64
65 /* call inclusion method of presolver */
67
68 return SCIP_OKAY;
69}
70
71
72/** execution method of presolver */
73static
74SCIP_DECL_PRESOLEXEC(presolExecImplics)
75{ /*lint --e{715}*/
76 SCIP_VAR** vars;
77 SCIP_VAR** bdchgvars;
78 SCIP_BOUNDTYPE* bdchgtypes;
79 SCIP_Real* bdchgvals;
80 SCIP_VAR** aggrvars;
81 SCIP_VAR** aggraggvars;
82 SCIP_Real* aggrcoefs;
83 SCIP_Real* aggrconsts;
84 int nbdchgs;
85 int naggregations;
86 int nbinvars;
87 int v;
88
89 assert(result != NULL);
90
91 *result = SCIP_DIDNOTFIND;
92
93 /* initialize fixing and aggregation storages */
94 bdchgvars = NULL;
95 bdchgtypes = NULL;
96 bdchgvals = NULL;
97 nbdchgs = 0;
98 aggrvars = NULL;
99 aggraggvars = NULL;
100 aggrcoefs = NULL;
101 aggrconsts = NULL;
102 naggregations = 0;
103
104 /* get active binary problem variables */
105 vars = SCIPgetVars(scip);
106 nbinvars = SCIPgetNBinVars(scip);
107
108 /* look for variable implications in x == 0 and x == 1 with the same implied variable:
109 * x = 0 -> y = lb, and x = 1 -> y = lb: fix y to lb
110 * x = 0 -> y = lb, and x = 1 -> y = ub: aggregate y == lb + (ub-lb)x
111 * x = 0 -> y = ub, and x = 1 -> y = lb: aggregate y == ub - (ub-lb)x
112 * x = 0 -> y = ub, and x = 1 -> y = ub: fix y to ub
113 * the fixings and aggregations are stored in a buffer and applied afterwards, because fixing and aggregation
114 * would modify the vars array and the implication arrays
115 */
116 for( v = 0; v < nbinvars; ++v )
117 {
118 SCIP_VAR** implvars[2];
119 SCIP_BOUNDTYPE* impltypes[2];
120 SCIP_Real* implbounds[2];
121 int nimpls[2];
122 int varfixing;
123 int i0;
124 int i1;
125
126 /* don't perform presolving operations on deleted variables */
127 if( SCIPvarIsDeleted(vars[v]) )
128 continue;
129
130 /* get implications for given variable */
131 for( varfixing = 0; varfixing < 2; ++varfixing )
132 {
133 implvars[varfixing] = SCIPvarGetImplVars(vars[v], (SCIP_Bool)varfixing);
134 impltypes[varfixing] = SCIPvarGetImplTypes(vars[v], (SCIP_Bool)varfixing);
135 implbounds[varfixing] = SCIPvarGetImplBounds(vars[v], (SCIP_Bool)varfixing);
136 nimpls[varfixing] = SCIPvarGetNImpls(vars[v], (SCIP_Bool)varfixing);
137 }
138
139 /* scan implication arrays for equal variables */
140 i0 = 0;
141 i1 = 0;
142 while( i0 < nimpls[0] && i1 < nimpls[1] )
143 {
144 int index0;
145 int index1;
146
147 /* scan the binary or non-binary part of the implication arrays */
148 index0 = SCIPvarGetIndex(implvars[0][i0]);
149 index1 = SCIPvarGetIndex(implvars[1][i1]);
150 while( index0 < index1 )
151 {
152 i0++;
153 if( i0 == nimpls[0] )
154 {
155 index0 = -1;
156 break;
157 }
158 index0 = SCIPvarGetIndex(implvars[0][i0]); /*lint !e838*/
159 }
160 while( index1 < index0 )
161 {
162 i1++;
163 if( i1 == nimpls[1] )
164 {
165 index1 = -1;
166 break;
167 }
168 index1 = SCIPvarGetIndex(implvars[1][i1]); /*lint !e838*/
169 }
170 /**@todo for all implicit binary variables y, check the cliques of x == !varfixing if y is contained */
171
172 if( index0 == index1 )
173 {
174 assert(index0 >= 0);
175 assert(i0 < nimpls[0]);
176 assert(i1 < nimpls[1]);
177 assert(implvars[0][i0] == implvars[1][i1]);
178
179 /* multiaggregated variables cannot be aggregated or their bounds tightened */
180 if( SCIPvarGetStatus(implvars[0][i0]) != SCIP_VARSTATUS_MULTAGGR )
181 {
182 if( impltypes[0][i0] == impltypes[1][i1] )
183 {
184 /* found implication x = 0 -> y >= b / y <= b and x = 1 -> y >= c / y <= c
185 * => change bound y >= min(b,c) / y <= max(b,c)
186 */
187 SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgvars, nbdchgs+1) );
188 SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgtypes, nbdchgs+1) );
189 SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgvals, nbdchgs+1) );
190 bdchgvars[nbdchgs] = implvars[0][i0];
191 bdchgtypes[nbdchgs] = impltypes[0][i0];
192 if( impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER )
193 bdchgvals[nbdchgs] = MIN(implbounds[0][i0], implbounds[1][i1]);
194 else
195 bdchgvals[nbdchgs] = MAX(implbounds[0][i0], implbounds[1][i1]);
196
197 SCIPdebugMsg(scip, " -> <%s> = 0 -> <%s> %s %g, and <%s> = 1 -> <%s> %s %g: tighten <%s> %s %g\n",
198 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]),
199 impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbounds[0][i0],
200 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]),
201 impltypes[1][i1] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbounds[1][i1],
202 SCIPvarGetName(bdchgvars[nbdchgs]), bdchgtypes[nbdchgs] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
203 bdchgvals[nbdchgs]);
204
205 nbdchgs++;
206 }
207 else
208 {
209 SCIP_Real implvarlb;
210 SCIP_Real implvarub;
211
212 implvarlb = SCIPvarGetLbGlobal(implvars[0][i0]);
213 implvarub = SCIPvarGetUbGlobal(implvars[0][i0]);
214
215 if( impltypes[0][i0] == SCIP_BOUNDTYPE_UPPER
216 && SCIPisEQ(scip, implbounds[0][i0], implvarlb)
217 && SCIPisEQ(scip, implbounds[1][i1], implvarub) )
218 {
219 /* found implication x = 0 -> y = lb and x = 1 -> y = ub => aggregate y = lb + (ub-lb) * x */
220 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrvars, naggregations+1) );
221 SCIP_CALL( SCIPreallocBufferArray(scip, &aggraggvars, naggregations+1) );
222 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrcoefs, naggregations+1) );
223 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrconsts, naggregations+1) );
224 aggrvars[naggregations] = implvars[0][i0];
225 aggraggvars[naggregations] = vars[v];
226 aggrcoefs[naggregations] = implvarub - implvarlb;
227 aggrconsts[naggregations] = implvarlb;
228
229 SCIPdebugMsg(scip, " -> <%s> = 0 -> <%s> = %g, and <%s> = 1 -> <%s> = %g: aggregate <%s> = %g %+g<%s>\n",
230 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]), implbounds[0][i0],
231 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]), implbounds[1][i1],
232 SCIPvarGetName(aggrvars[naggregations]), aggrconsts[naggregations], aggrcoefs[naggregations],
233 SCIPvarGetName(aggraggvars[naggregations]));
234
235 naggregations++;
236 }
237 else if( impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER
238 && SCIPisEQ(scip, implbounds[0][i0], implvarub)
239 && SCIPisEQ(scip, implbounds[1][i1], implvarlb) )
240 {
241 /* found implication x = 0 -> y = ub and x = 1 -> y = lb => aggregate y = ub - (ub-lb) * x */
242 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrvars, naggregations+1) );
243 SCIP_CALL( SCIPreallocBufferArray(scip, &aggraggvars, naggregations+1) );
244 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrcoefs, naggregations+1) );
245 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrconsts, naggregations+1) );
246 aggrvars[naggregations] = implvars[0][i0];
247 aggraggvars[naggregations] = vars[v];
248 aggrcoefs[naggregations] = implvarlb - implvarub;
249 aggrconsts[naggregations] = implvarub;
250
251 SCIPdebugMsg(scip, " -> <%s> = 0 -> <%s> = %g, and <%s> = 1 -> <%s> = %g: aggregate <%s> = %g %+g<%s>\n",
252 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]), implbounds[0][i0],
253 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]), implbounds[1][i1],
254 SCIPvarGetName(aggrvars[naggregations]), aggrconsts[naggregations], aggrcoefs[naggregations],
255 SCIPvarGetName(aggraggvars[naggregations]));
256
257 naggregations++;
258 }
259 }
260 }
261
262 /* process the next implications */
263 i0++;
264 i1++;
265 }
266 }
267 }
268
269 /**@todo check cliques of x == 0 and x == 1 for equal entries y == b -> fix y == !b */
270
271 /* perform the bound changes
272 *
273 * Note, that we cannot assume y to be active (see var.c: varRemoveImplicsVbs()), but it should not cause any
274 * troubles as this case seems to be handled correctly in SCIPtightenVarLb/Ub(), unless the variable is
275 * multiaggregated, but this has been excluded above.
276 */
277 for( v = 0; v < nbdchgs && *result != SCIP_CUTOFF; ++v )
278 {
279 SCIP_Bool infeasible;
280 SCIP_Bool tightened;
281
282 assert(bdchgtypes != NULL);
283 assert(bdchgvars != NULL);
284 assert(bdchgvals != NULL);
285
286 if( bdchgtypes[v] == SCIP_BOUNDTYPE_LOWER )
287 {
288 SCIP_CALL( SCIPtightenVarLb(scip, bdchgvars[v], bdchgvals[v], FALSE, &infeasible, &tightened) );
289 }
290 else
291 {
292 SCIP_CALL( SCIPtightenVarUb(scip, bdchgvars[v], bdchgvals[v], FALSE, &infeasible, &tightened) );
293 }
294
295 if( infeasible )
296 {
297 SCIPdebugMsg(scip, " -> infeasible bound change <%s> %s %g\n", SCIPvarGetName(bdchgvars[v]),
298 bdchgtypes[v] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bdchgvals[v]);
299 *result = SCIP_CUTOFF;
300 }
301 else if( tightened )
302 {
303 (*nchgbds)++;
304 *result = SCIP_SUCCESS;
305 }
306 }
307
308 /* perform the aggregations
309 *
310 * Note, that we cannot assume y to be active (see var.c: varRemoveImplicsVbs()), but it should not cause any
311 * troubles as this case seems to be handled correctly in SCIPaggregateVars(), unless the variable is
312 * multiaggregated, but this has been excluded above.
313 */
314 for( v = 0; v < naggregations && *result != SCIP_CUTOFF; ++v )
315 {
316 SCIP_Bool infeasible;
317 SCIP_Bool redundant;
318 SCIP_Bool aggregated;
319
320 assert(aggrvars != NULL);
321 assert(aggraggvars != NULL);
322 assert(aggrcoefs != NULL);
323 assert(aggrconsts != NULL);
324
325 /* aggregation y = const + coef * x => y - coef * x = const */
326 SCIP_CALL( SCIPaggregateVars(scip, aggrvars[v], aggraggvars[v], 1.0, -aggrcoefs[v], aggrconsts[v],
327 &infeasible, &redundant, &aggregated) );
328 if( infeasible )
329 {
330 SCIPdebugMsg(scip, " -> infeasible aggregation <%s> = %g %+g<%s>\n",
331 SCIPvarGetName(aggrvars[v]), aggrconsts[v], aggrcoefs[v], SCIPvarGetName(aggraggvars[v]));
332 *result = SCIP_CUTOFF;
333 }
334 else if( aggregated )
335 {
336 (*naggrvars)++;
337 *result = SCIP_SUCCESS;
338 }
339 }
340
341 /* free the storage buffers */
342 SCIPfreeBufferArrayNull(scip, &aggrconsts);
343 SCIPfreeBufferArrayNull(scip, &aggrcoefs);
344 SCIPfreeBufferArrayNull(scip, &aggraggvars);
345 SCIPfreeBufferArrayNull(scip, &aggrvars);
346 SCIPfreeBufferArrayNull(scip, &bdchgvals);
347 SCIPfreeBufferArrayNull(scip, &bdchgtypes);
348 SCIPfreeBufferArrayNull(scip, &bdchgvars);
349
350 return SCIP_OKAY;
351}
352
353
354/*
355 * presolver specific interface methods
356 */
357
358/** creates the implics presolver and includes it in SCIP */
360 SCIP* scip /**< SCIP data structure */
361 )
362{
363 SCIP_PRESOL* presolptr;
364
365 /* include presolver */
367
368 assert(presolptr != NULL);
369
370 SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyImplics) );
371
372 return SCIP_OKAY;
373}
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludePresolImplics(SCIP *scip)
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
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:105
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
Definition: var.c:17640
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18356
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
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_var.c:8401
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18373
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17758
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18402
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18388
memory allocation routines
static SCIP_DECL_PRESOLEXEC(presolExecImplics)
#define PRESOL_NAME
static SCIP_DECL_PRESOLCOPY(presolCopyImplics)
#define PRESOL_PRIORITY
#define PRESOL_MAXROUNDS
#define PRESOL_TIMING
#define PRESOL_DESC
implication graph presolver which checks for aggregations
public methods for message output
public methods for presolvers
public methods for problem variables
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for SCIP variables
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54