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