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-2024 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 
33 #include "blockmemshell/memory.h"
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) */
58 static
59 SCIP_DECL_PRESOLCOPY(presolCopyImplics)
60 { /*lint --e{715}*/
61  assert(scip != NULL);
62  assert(presol != NULL);
63  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
64 
65  /* call inclusion method of presolver */
67 
68  return SCIP_OKAY;
69 }
70 
71 
72 /** execution method of presolver */
73 static
74 SCIP_DECL_PRESOLEXEC(presolExecImplics)
75 { /*lint --e{715}*/
76  SCIP_VAR** vars;
77  SCIP_VAR** bdchgvars;
78  SCIP_BOUNDTYPE* bdchgtypes;
79  SCIP_Real* bdchgvals;
80  SCIP_VAR** aggrvars;
81  SCIP_VAR** aggraggvars;
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 
91  *result = SCIP_DIDNOTFIND;
92 
93  /* initialize fixing and aggregation storages */
94  bdchgvars = NULL;
95  bdchgtypes = NULL;
96  bdchgvals = NULL;
97  nbdchgs = 0;
98  aggrvars = NULL;
99  aggraggvars = NULL;
100  aggrcoefs = NULL;
101  aggrconsts = NULL;
102  naggregations = 0;
103 
104  /* get active binary problem variables */
105  vars = SCIPgetVars(scip);
106  nbinvars = SCIPgetNBinVars(scip);
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];
119  SCIP_BOUNDTYPE* impltypes[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  {
133  implvars[varfixing] = SCIPvarGetImplVars(vars[v], (SCIP_Bool)varfixing);
134  impltypes[varfixing] = SCIPvarGetImplTypes(vars[v], (SCIP_Bool)varfixing);
135  implbounds[varfixing] = SCIPvarGetImplBounds(vars[v], (SCIP_Bool)varfixing);
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 */
148  index0 = SCIPvarGetIndex(implvars[0][i0]);
149  index1 = SCIPvarGetIndex(implvars[1][i1]);
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 */
180  if( SCIPvarGetStatus(implvars[0][i0]) != SCIP_VARSTATUS_MULTAGGR )
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  */
187  SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgvars, nbdchgs+1) );
188  SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgtypes, nbdchgs+1) );
189  SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgvals, nbdchgs+1) );
190  bdchgvars[nbdchgs] = implvars[0][i0];
191  bdchgtypes[nbdchgs] = impltypes[0][i0];
192  if( impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER )
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",
198  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]),
199  impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbounds[0][i0],
200  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]),
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 
212  implvarlb = SCIPvarGetLbGlobal(implvars[0][i0]);
213  implvarub = SCIPvarGetUbGlobal(implvars[0][i0]);
214 
215  if( impltypes[0][i0] == SCIP_BOUNDTYPE_UPPER
216  && SCIPisEQ(scip, implbounds[0][i0], implvarlb)
217  && SCIPisEQ(scip, implbounds[1][i1], implvarub) )
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",
230  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]), implbounds[0][i0],
231  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]), implbounds[1][i1],
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
238  && SCIPisEQ(scip, implbounds[0][i0], implvarub)
239  && SCIPisEQ(scip, implbounds[1][i1], implvarlb) )
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",
252  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]), implbounds[0][i0],
253  SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]), implbounds[1][i1],
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 
282  assert(bdchgtypes != NULL);
283  assert(bdchgvars != NULL);
284  assert(bdchgvals != NULL);
285 
286  if( bdchgtypes[v] == SCIP_BOUNDTYPE_LOWER )
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]);
299  *result = SCIP_CUTOFF;
300  }
301  else if( tightened )
302  {
303  (*nchgbds)++;
304  *result = SCIP_SUCCESS;
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);
321  assert(aggraggvars != NULL);
322  assert(aggrcoefs != NULL);
323  assert(aggrconsts != NULL);
324 
325  /* aggregation y = const + coef * x => y - coef * x = const */
326  SCIP_CALL( SCIPaggregateVars(scip, aggrvars[v], aggraggvars[v], 1.0, -aggrcoefs[v], aggrconsts[v],
327  &infeasible, &redundant, &aggregated) );
328  if( infeasible )
329  {
330  SCIPdebugMsg(scip, " -> infeasible aggregation <%s> = %g %+g<%s>\n",
331  SCIPvarGetName(aggrvars[v]), aggrconsts[v], aggrcoefs[v], SCIPvarGetName(aggraggvars[v]));
332  *result = SCIP_CUTOFF;
333  }
334  else if( aggregated )
335  {
336  (*naggrvars)++;
337  *result = SCIP_SUCCESS;
338  }
339  }
340 
341  /* free the storage buffers */
342  SCIPfreeBufferArrayNull(scip, &aggrconsts);
343  SCIPfreeBufferArrayNull(scip, &aggrcoefs);
344  SCIPfreeBufferArrayNull(scip, &aggraggvars);
345  SCIPfreeBufferArrayNull(scip, &aggrvars);
346  SCIPfreeBufferArrayNull(scip, &bdchgvals);
347  SCIPfreeBufferArrayNull(scip, &bdchgtypes);
348  SCIPfreeBufferArrayNull(scip, &bdchgvars);
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 */
360  SCIP* scip /**< SCIP data structure */
361  )
362 {
363  SCIP_PRESOL* presolptr;
364 
365  /* include presolver */
367 
368  assert(presolptr != NULL);
369 
370  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyImplics) );
371 
372  return SCIP_OKAY;
373 }
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:105
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
#define PRESOL_TIMING
#define NULL
Definition: def.h:267
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5202
#define PRESOL_DESC
#define PRESOL_NAME
public methods for memory management
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
#define FALSE
Definition: def.h:94
public methods for presolving plugins
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
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:5319
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:78
public methods for numerical tolerances
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
#define SCIP_CALL(x)
Definition: def.h:380
#define PRESOL_MAXROUNDS
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18389
#define SCIP_Bool
Definition: def.h:91
implication graph presolver which checks for aggregations
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18357
#define MIN(x, y)
Definition: def.h:243
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18403
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18374
public methods for presolvers
#define MAX(x, y)
Definition: def.h:239
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17539
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:8400
#define SCIP_Real
Definition: def.h:173
public methods for message handling
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17759
static SCIP_DECL_PRESOLCOPY(presolCopyImplics)
public methods for global and local (sub)problems
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
Definition: var.c:17641
static SCIP_DECL_PRESOLEXEC(presolExecImplics)
SCIP_RETCODE SCIPincludePresolImplics(SCIP *scip)
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
memory allocation routines