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_convertinttobin.c
26   	 * @ingroup DEFPLUGINS_PRESOL
27   	 * @brief  presolver that converts integer variables to binaries
28   	 * @author Michael Winkler
29   	 *
30   	 *  Converts integer variables at the beginning of Presolving into their binary representation. If necessary adds a
31   	 *  bounding knapsack constraint.
32   	 *
33   	 */
34   	
35   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36   	
37   	#include "blockmemshell/memory.h"
38   	#include "scip/cons_knapsack.h"
39   	#include "scip/debug.h"
40   	#include "scip/presol_convertinttobin.h"
41   	#include "scip/pub_message.h"
42   	#include "scip/pub_misc.h"
43   	#include "scip/pub_presol.h"
44   	#include "scip/pub_var.h"
45   	#include "scip/scip_cons.h"
46   	#include "scip/scip_mem.h"
47   	#include "scip/scip_message.h"
48   	#include "scip/scip_numerics.h"
49   	#include "scip/scip_param.h"
50   	#include "scip/scip_presol.h"
51   	#include "scip/scip_prob.h"
52   	#include "scip/scip_var.h"
53   	#include <string.h>
54   	
55   	#define PRESOL_NAME            "convertinttobin"
56   	#define PRESOL_DESC            "converts integer variables to binaries"
57   	#define PRESOL_PRIORITY        +6000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
58   	#define PRESOL_MAXROUNDS              0 /**< maximal number of presolving rounds the presolver participates in (-1: no
59   						 *   limit) */
60   	#define PRESOL_TIMING           SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
61   	
62   	#define DEFAULT_MAXDOMAINSIZE  SCIP_LONGINT_MAX   /**< absolute value of maximum domain size which will be converted */
63   	#define DEFAULT_ONLYPOWERSOFTWO           FALSE   /**< should only integer variables with a domain size of 2^p - 1 be
64   	                                                   *   converted(, there we don't need an knapsack-constraint) */
65   	#define DEFAULT_SAMELOCKSINBOTHDIRECTIONS FALSE   /**< should only integer variables with uplocks equals downlocks be converted */
66   	
67   	/** presolver data */
68   	struct SCIP_PresolData
69   	{
70   	   SCIP_Longint          maxdomainsize;      /**< absolute value of maximum domain size */
71   	   SCIP_Bool             onlypoweroftwo;     /**< should only integer variables with a domain size of 2^p - 1 be converted */
72   	   SCIP_Bool             samelocksinbothdirections; /**< should only integer variables with uplocks equals downlocks be converted */
73   	};
74   	
75   	/*
76   	 * Callback methods of presolver
77   	 */
78   	
79   	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
80   	static
81   	SCIP_DECL_PRESOLCOPY(presolCopyConvertinttobin)
82   	{  /*lint --e{715}*/
83   	   assert(scip != NULL);
84   	   assert(presol != NULL);
85   	   assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
86   	
87   	   /* call inclusion method of presolver */
88   	   SCIP_CALL( SCIPincludePresolConvertinttobin(scip) );
89   	
90   	   return SCIP_OKAY;
91   	}
92   	
93   	/** destructor of presolver to free user data (called when SCIP is exiting) */
94   	static
95   	SCIP_DECL_PRESOLFREE(presolFreeConvertinttobin)
96   	{  /*lint --e{715}*/
97   	   SCIP_PRESOLDATA* presoldata;
98   	
99   	   /* free presolver data */
100  	   presoldata = SCIPpresolGetData(presol);
101  	   assert(presoldata != NULL);
102  	
103  	   SCIPfreeBlockMemory(scip, &presoldata);
104  	   SCIPpresolSetData(presol, NULL);
105  	
106  	   return SCIP_OKAY;
107  	}
108  	
109  	/** presolving execution method */
110  	static
111  	SCIP_DECL_PRESOLEXEC(presolExecConvertinttobin)
112  	{  /*lint --e{715}*/
113  	   SCIP_VAR** scipvars;
114  	   SCIP_VAR** vars;
115  	   SCIP_PRESOLDATA* presoldata;
116  	   int nbinvars;
117  	   int nintvars;
118  	   int v;
119  	
120  	   assert(scip != NULL);
121  	   assert(presol != NULL);
122  	   assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
123  	   assert(result != NULL);
124  	
125  	   *result = SCIP_DIDNOTRUN;
126  	
127  	   /* get the problem variables */
128  	   scipvars = SCIPgetVars(scip);
129  	   nbinvars = SCIPgetNBinVars(scip);
130  	   nintvars = SCIPgetNIntVars(scip);
131  	   if( nintvars == 0 )
132  	      return SCIP_OKAY;
133  	
134  	   /* get presolver data */
135  	   presoldata = SCIPpresolGetData(presol);
136  	   assert(presoldata != NULL);
137  	
138  	   *result = SCIP_DIDNOTFIND;
139  	
140  	   /* copy the integer variables into an own array, since adding binary variables affects the left-most slots in the
141  	    * array and thereby interferes with our search loop
142  	    */
143  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nintvars) );
144  	
145  	   /* scan the integer variables for possible conversion into binaries;
146  	    * we have to collect the variables first in an own
147  	    */
148  	   for( v = 0; v < nintvars; ++v )
149  	   {
150  	      SCIP_VAR** newbinvars;
151  	      SCIP_Real* newbinvarcoeffs;
152  	      SCIP_Longint* weights;
153  	      SCIP_CONS* newcons;
154  	      SCIP_Real lb;
155  	      SCIP_Real ub;
156  	      SCIP_Longint domainsize;
157  	      char newbinvarname[SCIP_MAXSTRLEN];
158  	      char newconsname[SCIP_MAXSTRLEN];
159  	      int nnewbinvars;
160  	      int v2;
161  	      SCIP_Longint scalar;
162  	      SCIP_Bool infeasible;
163  	      SCIP_Bool aggregated;
164  	      SCIP_Bool noconsknapsack;
165  	
166  	      assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER);
167  	
168  	      /* skip variables which cannot be multi-aggregated */
169  	      if( SCIPdoNotMultaggrVar(scip, vars[v]) )
170  		 continue;
171  	
172  	      /* check for correct locks */
173  	      if( presoldata->samelocksinbothdirections
174  	         && SCIPvarGetNLocksUpType(vars[v], SCIP_LOCKTYPE_MODEL) != SCIPvarGetNLocksDownType(vars[v], SCIP_LOCKTYPE_MODEL) )
175  	         continue;
176  	
177  	      /* get variable's bounds */
178  	      lb = SCIPvarGetLbGlobal(vars[v]);
179  	      ub = SCIPvarGetUbGlobal(vars[v]);
180  	      assert( SCIPisIntegral(scip, lb) );
181  	      assert( SCIPisIntegral(scip, ub) );
182  	
183  	      if( SCIPisInfinity(scip, ub - lb) )
184  	         domainsize = SCIP_LONGINT_MAX;
185  	      else
186  	         domainsize = (SCIP_Longint) SCIPceil(scip, ub - lb);
187  	
188  	      assert(domainsize >= 0);
189  	
190  	      /* check for allowed domainsize */
191  	      if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) || domainsize > presoldata->maxdomainsize )
192  	         continue;
193  	
194  	      /* check for domainsize is not 2^p - 1 if necessary */
195  	      if( presoldata->onlypoweroftwo )
196  	      {
197  	         /* stop if domainsize is not 2^p - 1*/
198  	         SCIP_Longint tmp;
199  	
200  	         assert(domainsize < SCIP_LONGINT_MAX);
201  	         tmp = domainsize + 1;
202  	
203  	         while( tmp % 2 == 0 )
204  	            tmp /= 2;
205  	         if( tmp != 1 )
206  	            continue;
207  	      }
208  	
209  	      noconsknapsack = FALSE;
210  	
211  	      nnewbinvars = (int)SCIPfloor(scip, (log((SCIP_Real) domainsize)/log(2.0))) + 1;
212  	
213  	      SCIPdebugMsg(scip, "integer variable <%s> [%g,%g], domainsize %" SCIP_LONGINT_FORMAT "\n, <uplocks = %d, downlocks = %d will be 'binarized' by %d binary variables\n ",
214  	         SCIPvarGetName(vars[v]), lb, ub, domainsize, SCIPvarGetNLocksUpType(vars[v], SCIP_LOCKTYPE_MODEL),
215  	         SCIPvarGetNLocksDownType(vars[v], SCIP_LOCKTYPE_MODEL), nnewbinvars);
216  	
217  	      assert(nnewbinvars > 0);
218  	
219  	      scalar = (SCIP_Longint)pow(2.0, nnewbinvars); /*lint !e747*/
220  	      /* because of rounding errors */
221  	      if( scalar == domainsize )
222  	      {
223  	         scalar *= 2;
224  	         nnewbinvars++;
225  	      }
226  	      else if( scalar == domainsize + 1 )
227  	         noconsknapsack = TRUE;
228  	
229  	      assert(scalar > domainsize);
230  	
231  	      SCIP_CALL( SCIPallocBufferArray(scip, &newbinvars, nnewbinvars) );
232  	      SCIP_CALL( SCIPallocBufferArray(scip, &newbinvarcoeffs, nnewbinvars) );
233  	      SCIP_CALL( SCIPallocBufferArray(scip, &weights, nnewbinvars) );
234  	
235  	      for( v2 = nnewbinvars - 1; v2 >= 0; --v2 )
236  	      {
237  	         SCIPdebugMsg(scip, "creating for <%s>[%g,%g] %d. binary variable\n", SCIPvarGetName(vars[v]), lb, ub, v2);
238  	
239  	         /* create binary variable */
240  	         (void) SCIPsnprintf(newbinvarname, SCIP_MAXSTRLEN, "%s_bin_%d", SCIPvarGetName(vars[v]), v2);
241  	         SCIP_CALL( SCIPcreateVar(scip, &newbinvars[v2], newbinvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
242  	               SCIPvarIsInitial(vars[v]), SCIPvarIsRemovable(vars[v]), NULL, NULL, NULL, NULL, NULL) );
243  	         SCIP_CALL( SCIPaddVar(scip, newbinvars[v2]) );
244  	
245  	         scalar /= 2;
246  	         assert(scalar > 0);
247  	
248  	         newbinvarcoeffs[v2] = (SCIP_Real)scalar;
249  	         weights[v2] = scalar;
250  	      }
251  	
252  	#ifdef WITH_DEBUG_SOLUTION
253  	      /* set the debug solution values */
254  	      if( SCIPdebugIsMainscip(scip) )
255  	      {
256  	         SCIP_Real varval;
257  	
258  	         SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &varval) );
259  	         assert(SCIPisIntegral(scip, varval));
260  	
261  	         if( SCIPisPositive(scip, varval) )
262  	         {
263  	            SCIP_Real resvarval = varval;
264  	
265  	            for( v2 = nnewbinvars - 1; v2 >= 0; --v2 )
266  	            {
267  	               assert(SCIPisPositive(scip, resvarval));
268  	               assert(SCIPisIntegral(scip, resvarval));
269  	
270  	               if( SCIPisLE(scip, newbinvarcoeffs[v2], resvarval) )
271  	               {
272  	                  SCIP_CALL( SCIPdebugAddSolVal(scip, newbinvars[v2], 1.0) );
273  	                  resvarval -= newbinvarcoeffs[v2];
274  	               }
275  	
276  	               if( SCIPisZero(scip, resvarval) )
277  	                  break;
278  	            }
279  	         }
280  	      }
281  	#endif
282  	
283  	      /* aggregate integer and binary variable */
284  	      SCIP_CALL( SCIPmultiaggregateVar(scip, vars[v], nnewbinvars, newbinvars, (SCIP_Real*)newbinvarcoeffs, lb, &infeasible, &aggregated) );
285  	      assert(!infeasible);
286  	      assert(aggregated);
287  	
288  	      (void) SCIPsnprintf(newconsname, SCIP_MAXSTRLEN, "%s_bin_knapsack", SCIPvarGetName(vars[v]));
289  	
290  	      if( !noconsknapsack )
291  	      {
292  	         int nodd;
293  	         nodd = 0;
294  	         while( domainsize % 2 == 1 )
295  	         {
296  	            nodd++;
297  	            domainsize = (domainsize - 1) / 2;
298  	         }
299  	         if( nodd > 0 )
300  	         {
301  	            SCIP_Longint divisor;
302  	
303  	            divisor = (SCIP_Longint)pow(2.0, nodd); /*lint !e747*/
304  	            assert(divisor >= 2);
305  	
306  	            for( v2 = nodd; v2 < nnewbinvars; ++v2 )
307  	            {
308  	               weights[v2] /= divisor;
309  	            }
310  	         }
311  	
312  	         SCIP_CALL( SCIPcreateConsKnapsack(scip, &newcons, newconsname, nnewbinvars - nodd, &newbinvars[nodd],
313  	               &weights[nodd], domainsize,
314  	               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
315  	         SCIP_CALL( SCIPaddCons(scip, newcons) );
316  	         SCIPdebugPrintCons(scip, newcons, NULL);
317  	         SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
318  	      }
319  	
320  	      for( v2 = nnewbinvars - 1; v2 >= 0; --v2 )
321  	      {
322  	         /* release binary variable */
323  	         SCIP_CALL( SCIPreleaseVar(scip, &newbinvars[v2]) );
324  	         (*nchgvartypes)++;
325  	      }
326  	
327  	      SCIPfreeBufferArray(scip, &newbinvars);
328  	      SCIPfreeBufferArray(scip, &newbinvarcoeffs);
329  	      SCIPfreeBufferArray(scip, &weights);
330  	
331  	      if( aggregated ) /*lint !e774*/
332  	         *result = SCIP_SUCCESS;
333  	   }
334  	
335  	   /* free temporary memory */
336  	   SCIPfreeBufferArray(scip, &vars);
337  	
338  	   return SCIP_OKAY;
339  	}
340  	
341  	
342  	/*
343  	 * presolver specific interface methods
344  	 */
345  	
346  	/** creates the convertinttobin presolver and includes it in SCIP */
347  	SCIP_RETCODE SCIPincludePresolConvertinttobin(
348  	   SCIP*                 scip                /**< SCIP data structure */
349  	   )
350  	{
351  	   SCIP_PRESOLDATA* presoldata;
352  	   SCIP_PRESOL* presolptr;
353  	
354  	   /* create convertinttobin presolver data */
355  	   SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
356  	
357  	   presoldata->maxdomainsize = DEFAULT_MAXDOMAINSIZE;
358  	   presoldata->onlypoweroftwo = DEFAULT_ONLYPOWERSOFTWO;
359  	
360  	   /* include presolver */
361  	   SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING,
362  	         presolExecConvertinttobin,
363  	         presoldata) );
364  	   assert(presolptr != NULL);
365  	
366  	   SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyConvertinttobin) );
367  	   SCIP_CALL( SCIPsetPresolFree(scip, presolptr, presolFreeConvertinttobin) );
368  	
369  	   /* add convertinttobin presolver parameters */
370  	   SCIP_CALL( SCIPaddLongintParam(scip,
371  	         "presolving/" PRESOL_NAME "/maxdomainsize",
372  	         "absolute value of maximum domain size for converting an integer variable to binaries variables",
373  	         &presoldata->maxdomainsize, TRUE, DEFAULT_MAXDOMAINSIZE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
374  	
375  	   /* add convertinttobin presolver parameters */
376  	   SCIP_CALL( SCIPaddBoolParam(scip,
377  	         "presolving/" PRESOL_NAME "/onlypoweroftwo",
378  	         "should only integer variables with a domain size of 2^p - 1 be converted(, there we don't need an knapsack-constraint for restricting the sum of the binaries)",
379  	         &presoldata->onlypoweroftwo, TRUE, DEFAULT_ONLYPOWERSOFTWO, NULL, NULL) );
380  	
381  	   /* add convertinttobin presolver parameters */
382  	   SCIP_CALL( SCIPaddBoolParam(scip,
383  	         "presolving/" PRESOL_NAME "/samelocksinbothdirections",
384  	         "should only integer variables with uplocks equals downlocks be converted",
385  	         &presoldata->samelocksinbothdirections, TRUE, DEFAULT_SAMELOCKSINBOTHDIRECTIONS, NULL, NULL) );
386  	
387  	   return SCIP_OKAY;
388  	}
389