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 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_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */
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 varfixing;
106  int i0;
107  int i1;
108 
109  /* don't perform presolving operations on deleted variables */
110  if( SCIPvarIsDeleted(vars[v]) )
111  continue;
112 
113  /* get implications for given variable */
114  for( varfixing = 0; varfixing < 2; ++varfixing )
115  {
116  implvars[varfixing] = SCIPvarGetImplVars(vars[v], (SCIP_Bool)varfixing);
117  impltypes[varfixing] = SCIPvarGetImplTypes(vars[v], (SCIP_Bool)varfixing);
118  implbounds[varfixing] = SCIPvarGetImplBounds(vars[v], (SCIP_Bool)varfixing);
119  nimpls[varfixing] = SCIPvarGetNImpls(vars[v], (SCIP_Bool)varfixing);
120  }
121 
122  /* scan implication arrays for equal variables */
123  i0 = 0;
124  i1 = 0;
125  while( i0 < nimpls[0] && i1 < nimpls[1] )
126  {
127  int index0;
128  int index1;
129 
130  /* scan the binary or non-binary part of the implication arrays */
131  index0 = SCIPvarGetIndex(implvars[0][i0]);
132  index1 = SCIPvarGetIndex(implvars[1][i1]);
133  while( index0 < index1 )
134  {
135  i0++;
136  if( i0 == nimpls[0] )
137  {
138  index0 = -1;
139  break;
140  }
141  index0 = SCIPvarGetIndex(implvars[0][i0]);
142  }
143  while( index1 < index0 )
144  {
145  i1++;
146  if( i1 == nimpls[1] )
147  {
148  index1 = -1;
149  break;
150  }
151  index1 = SCIPvarGetIndex(implvars[1][i1]);
152  }
153  /**@todo for all implied binary variables y, check the cliques of x == !varfixing if y is contained */
154 
155  if( index0 == index1 )
156  {
157  assert(index0 >= 0);
158  assert(i0 < nimpls[0]);
159  assert(i1 < nimpls[1]);
160  assert(implvars[0][i0] == implvars[1][i1]);
161 
162  if( impltypes[0][i0] == impltypes[1][i1] )
163  {
164  /* found implication x = 0 -> y >= b / y <= b and x = 1 -> y >= c / y <= c
165  * => change bound y >= min(b,c) / y <= max(b,c)
166  */
167  SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgvars, nbdchgs+1) );
168  SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgtypes, nbdchgs+1) );
169  SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgvals, nbdchgs+1) );
170  bdchgvars[nbdchgs] = implvars[0][i0];
171  bdchgtypes[nbdchgs] = impltypes[0][i0];
172  if( impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER )
173  bdchgvals[nbdchgs] = MIN(implbounds[0][i0], implbounds[1][i1]);
174  else
175  bdchgvals[nbdchgs] = MAX(implbounds[0][i0], implbounds[1][i1]);
176 
177  SCIPdebugMsg(scip, " -> <%s> = 0 -> <%s> %s %g, and <%s> = 1 -> <%s> %s %g: tighten <%s> %s %g\n",
178  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]),
179  impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbounds[0][i0],
180  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]),
181  impltypes[1][i1] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbounds[1][i1],
182  SCIPvarGetName(bdchgvars[nbdchgs]), bdchgtypes[nbdchgs] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
183  bdchgvals[nbdchgs]);
184 
185  nbdchgs++;
186  }
187  else
188  {
189  SCIP_Real implvarlb;
190  SCIP_Real implvarub;
191 
192  implvarlb = SCIPvarGetLbGlobal(implvars[0][i0]);
193  implvarub = SCIPvarGetUbGlobal(implvars[0][i0]);
194 
195  if( impltypes[0][i0] == SCIP_BOUNDTYPE_UPPER
196  && SCIPisEQ(scip, implbounds[0][i0], implvarlb)
197  && SCIPisEQ(scip, implbounds[1][i1], implvarub) )
198  {
199  /* found implication x = 0 -> y = lb and x = 1 -> y = ub => aggregate y = lb + (ub-lb) * x */
200  SCIP_CALL( SCIPreallocBufferArray(scip, &aggrvars, naggregations+1) );
201  SCIP_CALL( SCIPreallocBufferArray(scip, &aggraggvars, naggregations+1) );
202  SCIP_CALL( SCIPreallocBufferArray(scip, &aggrcoefs, naggregations+1) );
203  SCIP_CALL( SCIPreallocBufferArray(scip, &aggrconsts, naggregations+1) );
204  aggrvars[naggregations] = implvars[0][i0];
205  aggraggvars[naggregations] = vars[v];
206  aggrcoefs[naggregations] = implvarub - implvarlb;
207  aggrconsts[naggregations] = implvarlb;
208 
209  SCIPdebugMsg(scip, " -> <%s> = 0 -> <%s> = %g, and <%s> = 1 -> <%s> = %g: aggregate <%s> = %g %+g<%s>\n",
210  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]), implbounds[0][i0],
211  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]), implbounds[1][i1],
212  SCIPvarGetName(aggrvars[naggregations]), aggrconsts[naggregations], aggrcoefs[naggregations],
213  SCIPvarGetName(aggraggvars[naggregations]));
214 
215  naggregations++;
216  }
217  else if( impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER
218  && SCIPisEQ(scip, implbounds[0][i0], implvarub)
219  && SCIPisEQ(scip, implbounds[1][i1], implvarlb) )
220  {
221  /* found implication x = 0 -> y = ub and x = 1 -> y = lb => aggregate y = ub - (ub-lb) * x */
222  SCIP_CALL( SCIPreallocBufferArray(scip, &aggrvars, naggregations+1) );
223  SCIP_CALL( SCIPreallocBufferArray(scip, &aggraggvars, naggregations+1) );
224  SCIP_CALL( SCIPreallocBufferArray(scip, &aggrcoefs, naggregations+1) );
225  SCIP_CALL( SCIPreallocBufferArray(scip, &aggrconsts, naggregations+1) );
226  aggrvars[naggregations] = implvars[0][i0];
227  aggraggvars[naggregations] = vars[v];
228  aggrcoefs[naggregations] = implvarlb - implvarub;
229  aggrconsts[naggregations] = implvarub;
230 
231  SCIPdebugMsg(scip, " -> <%s> = 0 -> <%s> = %g, and <%s> = 1 -> <%s> = %g: aggregate <%s> = %g %+g<%s>\n",
232  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]), implbounds[0][i0],
233  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]), implbounds[1][i1],
234  SCIPvarGetName(aggrvars[naggregations]), aggrconsts[naggregations], aggrcoefs[naggregations],
235  SCIPvarGetName(aggraggvars[naggregations]));
236 
237  naggregations++;
238  }
239  }
240 
241  /* process the next implications */
242  i0++;
243  i1++;
244  }
245  }
246  }
247 
248  /**@todo check cliques of x == 0 and x == 1 for equal entries y == b -> fix y == !b */
249 
250  /* perform the bound changes
251  *
252  * note, that we cannot assume y to be active (see var.c: varRemoveImplicsVbs()), but it should not cause any
253  * troubles as this case seems to be handled correctly in SCIPtightenVarLb/Ub().
254  */
255  for( v = 0; v < nbdchgs && *result != SCIP_CUTOFF; ++v )
256  {
257  SCIP_Bool infeasible;
258  SCIP_Bool tightened;
259 
260  assert(bdchgtypes != NULL);
261  assert(bdchgvars != NULL);
262  assert(bdchgvals != NULL);
263 
264  if( bdchgtypes[v] == SCIP_BOUNDTYPE_LOWER )
265  {
266  SCIP_CALL( SCIPtightenVarLb(scip, bdchgvars[v], bdchgvals[v], FALSE, &infeasible, &tightened) );
267  }
268  else
269  {
270  SCIP_CALL( SCIPtightenVarUb(scip, bdchgvars[v], bdchgvals[v], FALSE, &infeasible, &tightened) );
271  }
272 
273  if( infeasible )
274  {
275  SCIPdebugMsg(scip, " -> infeasible bound change <%s> %s %g\n", SCIPvarGetName(bdchgvars[v]),
276  bdchgtypes[v] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bdchgvals[v]);
277  *result = SCIP_CUTOFF;
278  }
279  else if( tightened )
280  {
281  (*nchgbds)++;
282  *result = SCIP_SUCCESS;
283  }
284  }
285 
286  /* perform the aggregations
287  *
288  * note, that we cannot assume y to be active (see var.c: varRemoveImplicsVbs()), but it should not cause any
289  * troubles as this case seems to be handled correctly in SCIPaggregateVars().
290  */
291  for( v = 0; v < naggregations && *result != SCIP_CUTOFF; ++v )
292  {
293  SCIP_Bool infeasible;
294  SCIP_Bool redundant;
295  SCIP_Bool aggregated;
296 
297  assert(aggrvars != NULL);
298  assert(aggraggvars != NULL);
299  assert(aggrcoefs != NULL);
300  assert(aggrconsts != NULL);
301 
302  /* aggregation y = const + coef * x => y - coef * x = const */
303  SCIP_CALL( SCIPaggregateVars(scip, aggrvars[v], aggraggvars[v], 1.0, -aggrcoefs[v], aggrconsts[v],
304  &infeasible, &redundant, &aggregated) );
305  if( infeasible )
306  {
307  SCIPdebugMsg(scip, " -> infeasible aggregation <%s> = %g %+g<%s>\n",
308  SCIPvarGetName(aggrvars[v]), aggrconsts[v], aggrcoefs[v], SCIPvarGetName(aggraggvars[v]));
309  *result = SCIP_CUTOFF;
310  }
311  else if( aggregated )
312  {
313  (*naggrvars)++;
314  *result = SCIP_SUCCESS;
315  }
316  }
317 
318  /* free the storage buffers */
319  SCIPfreeBufferArrayNull(scip, &aggrconsts);
320  SCIPfreeBufferArrayNull(scip, &aggrcoefs);
321  SCIPfreeBufferArrayNull(scip, &aggraggvars);
322  SCIPfreeBufferArrayNull(scip, &aggrvars);
323  SCIPfreeBufferArrayNull(scip, &bdchgvals);
324  SCIPfreeBufferArrayNull(scip, &bdchgtypes);
325  SCIPfreeBufferArrayNull(scip, &bdchgvars);
326 
327  return SCIP_OKAY;
328 }
329 
330 
331 /*
332  * presolver specific interface methods
333  */
334 
335 /** creates the implics presolver and includes it in SCIP */
336 SCIP_RETCODE SCIPincludePresolImplics(
337  SCIP* scip /**< SCIP data structure */
338  )
339 {
340  SCIP_PRESOL* presolptr;
341 
342  /* include presolver */
343  SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, presolExecImplics, NULL) );
344 
345  assert(presolptr != NULL);
346 
347  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyImplics) );
348 
349  return SCIP_OKAY;
350 }
SCIPincludePresolBasic
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.c:6917
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
SCIP_Presol
Definition: struct_presol.h:37
PRESOL_TIMING
#define PRESOL_TIMING
Definition: presol_implics.c:33
SCIPtightenVarLb
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22523
PRESOL_DESC
#define PRESOL_DESC
Definition: presol_implics.c:30
PRESOL_NAME
#define PRESOL_NAME
Definition: presol_implics.c:29
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
SCIP_SUCCESS
Definition: type_result.h:49
SCIP_Var
Definition: struct_var.h:198
FALSE
#define FALSE
Definition: def.h:64
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIPtightenVarUb
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22639
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46963
PRESOL_PRIORITY
#define PRESOL_PRIORITY
Definition: presol_implics.c:31
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip.h:455
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:47
SCIPfreeBufferArrayNull
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:22633
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIP_OKAY
Definition: type_retcode.h:33
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:350
PRESOL_MAXROUNDS
#define PRESOL_MAXROUNDS
Definition: presol_implics.c:32
SCIPvarGetImplTypes
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17586
SCIP_Bool
#define SCIP_Bool
Definition: def.h:61
presol_implics.h
implication graph presolver which checks for aggregations
SCIPvarGetNImpls
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17554
MAX
#define MAX(x, y)
Definition: tclique_def.h:75
SCIPpresolGetName
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
SCIPvarGetImplBounds
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17600
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11857
SCIPvarGetImplVars
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17571
SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:48
SCIPsetPresolCopy
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6952
SCIPgetVars
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11767
SCIPaggregateVars
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.c:25684
SCIP_Real
#define SCIP_Real
Definition: def.h:149
SCIPvarGetIndex
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:16959
SCIP_DECL_PRESOLCOPY
static SCIP_DECL_PRESOLCOPY(presolCopyImplics)
Definition: presol_implics.c:42
SCIPvarIsDeleted
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
Definition: var.c:16883
SCIP_CUTOFF
Definition: type_result.h:39
SCIP_DECL_PRESOLEXEC
static SCIP_DECL_PRESOLEXEC(presolExecImplics)
Definition: presol_implics.c:57
SCIPincludePresolImplics
SCIP_RETCODE SCIPincludePresolImplics(SCIP *scip)
Definition: presol_implics.c:336
SCIPreallocBufferArray
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:22624