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