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