SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2023 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
60{ /*lint --e{715}*/
61 assert(scip != NULL);
62 assert(presol != NULL);
64
65 /* call inclusion method of presolver */
67
68 return SCIP_OKAY;
69}
70
71
72/** execution method of presolver */
73static
75{ /*lint --e{715}*/
76 SCIP_VAR** vars;
79 SCIP_Real* bdchgvals;
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
92
93 /* initialize fixing and aggregation storages */
97 nbdchgs = 0;
98 aggrvars = NULL;
100 aggrcoefs = NULL;
102 naggregations = 0;
103
104 /* get active binary problem variables */
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];
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 {
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 */
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 */
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 */
190 bdchgvars[nbdchgs] = implvars[0][i0];
191 bdchgtypes[nbdchgs] = impltypes[0][i0];
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",
199 impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbounds[0][i0],
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
214
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",
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
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",
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
285
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]);
300 }
301 else if( tightened )
302 {
303 (*nchgbds)++;
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);
324
325 /* aggregation y = const + coef * x => y - coef * x = const */
327 &infeasible, &redundant, &aggregated) );
328 if( infeasible )
329 {
330 SCIPdebugMsg(scip, " -> infeasible aggregation <%s> = %g %+g<%s>\n",
333 }
334 else if( aggregated )
335 {
336 (*naggrvars)++;
338 }
339 }
340
341 /* free the storage buffers */
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 */
#define FALSE
Definition def.h:96
#define SCIP_CALL(x)
Definition def.h:388
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
#define SCIPdebugMsg
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_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)
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:17462
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition var.c:18178
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
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:17910
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition var.c:18195
int SCIPvarGetIndex(SCIP_VAR *var)
Definition var.c:17580
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition var.c:18224
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:17900
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition var.c:18210
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_VAR ** vars
int nbinvars
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define PRESOL_NAME
#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
#define MAX(x, y)
Definition tclique_def.h:92
@ 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
#define SCIP_DECL_PRESOLCOPY(x)
Definition type_presol.h:60
#define SCIP_DECL_PRESOLEXEC(x)
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_SUCCESS
Definition type_result.h:58
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:54