1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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 */
66   	   SCIP_CALL( SCIPincludePresolImplics(scip) );
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 */
359  	SCIP_RETCODE SCIPincludePresolImplics(
360  	   SCIP*                 scip                /**< SCIP data structure */
361  	   )
362  	{
363  	   SCIP_PRESOL* presolptr;
364  	
365  	   /* include presolver */
366  	   SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, presolExecImplics, NULL) );
367  	
368  	   assert(presolptr != NULL);
369  	
370  	   SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyImplics) );
371  	
372  	   return SCIP_OKAY;
373  	}
374