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_inttobinary.c
26   	 * @ingroup DEFPLUGINS_PRESOL
27   	 * @brief  presolver that converts integer variables with domain [a,a+1] to binaries
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/debug.h"
35   	#include "scip/presol_inttobinary.h"
36   	#include "scip/pub_message.h"
37   	#include "scip/pub_misc.h"
38   	#include "scip/pub_presol.h"
39   	#include "scip/pub_var.h"
40   	#include "scip/scip_mem.h"
41   	#include "scip/scip_message.h"
42   	#include "scip/scip_numerics.h"
43   	#include "scip/scip_presol.h"
44   	#include "scip/scip_prob.h"
45   	#include "scip/scip_var.h"
46   	#include <string.h>
47   	
48   	#define PRESOL_NAME            "inttobinary"
49   	#define PRESOL_DESC            "converts integer variables with domain [a,a+1] to binaries"
50   	#define PRESOL_PRIORITY        +7000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
51   	#define PRESOL_MAXROUNDS              -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
52   	#define PRESOL_TIMING           SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
53   	
54   	/*
55   	 * Callback methods of presolver
56   	 */
57   	
58   	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
59   	static
60   	SCIP_DECL_PRESOLCOPY(presolCopyInttobinary)
61   	{  /*lint --e{715}*/
62   	   assert(scip != NULL);
63   	   assert(presol != NULL);
64   	   assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
65   	
66   	   /* call inclusion method of presolver */
67   	   SCIP_CALL( SCIPincludePresolInttobinary(scip) );
68   	
69   	   return SCIP_OKAY;
70   	}
71   	
72   	
73   	/** presolving execution method */
74   	static
75   	SCIP_DECL_PRESOLEXEC(presolExecInttobinary)
76   	{  /*lint --e{715}*/
77   	   SCIP_VAR** scipvars;
78   	   SCIP_VAR** vars;
79   	   int nbinvars;
80   	   int nintvars;
81   	   int v;
82   	
83   	   assert(result != NULL);
84   	
85   	   *result = SCIP_DIDNOTRUN;
86   	
87   	   if( SCIPdoNotAggr(scip) )
88   	      return SCIP_OKAY;
89   	
90   	   /* get the problem variables */
91   	   scipvars = SCIPgetVars(scip);
92   	   nbinvars = SCIPgetNBinVars(scip);
93   	   nintvars = SCIPgetNIntVars(scip);
94   	   if( nintvars == 0 )
95   	      return SCIP_OKAY;
96   	
97   	   *result = SCIP_DIDNOTFIND;
98   	
99   	   /* copy the integer variables into an own array, since adding binary variables affects the left-most slots in the
100  	    * array and thereby interferes with our search loop
101  	    */
102  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nintvars) );
103  	
104  	   /* scan the integer variables for possible conversion into binaries */
105  	   for( v = 0; v < nintvars; ++v )
106  	   {
107  	      SCIP_Real lb;
108  	      SCIP_Real ub;
109  	
110  	      assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER);
111  	
112  	      /* get variable's bounds */
113  	      lb = SCIPvarGetLbGlobal(vars[v]);
114  	      ub = SCIPvarGetUbGlobal(vars[v]);
115  	
116  	      /* check if bounds are exactly one apart; if the lower bound is too large, aggregations will be rejected */
117  	      if( SCIPisEQ(scip, lb, ub - 1.0) && !SCIPisHugeValue(scip, REALABS(lb) / SCIPfeastol(scip)) )
118  	      {
119  	         SCIP_VAR* binvar;
120  	         char binvarname[SCIP_MAXSTRLEN];
121  	         SCIP_Bool infeasible;
122  	         SCIP_Bool redundant;
123  	         SCIP_Bool aggregated;
124  	
125  	         SCIPdebugMsg(scip, "converting <%s>[%g,%g] into binary variable\n", SCIPvarGetName(vars[v]), lb, ub);
126  	
127  	         /* create binary variable */
128  	         (void) SCIPsnprintf(binvarname, SCIP_MAXSTRLEN, "%s_bin", SCIPvarGetName(vars[v]));
129  	         SCIP_CALL( SCIPcreateVar(scip, &binvar, binvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
130  	               SCIPvarIsInitial(vars[v]), SCIPvarIsRemovable(vars[v]), NULL, NULL, NULL, NULL, NULL) );
131  	         SCIP_CALL( SCIPaddVar(scip, binvar) );
132  	
133  	                     /* set up debug solution */
134  	#ifdef WITH_DEBUG_SOLUTION
135  	         if( SCIPdebugSolIsEnabled(scip) )
136  	         {
137  	            SCIP_SOL* debugsol;
138  	
139  	            SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) );
140  	
141  	            /* set solution value in the debug solution if it is available */
142  	            if( debugsol != NULL )
143  	            {
144  	               SCIP_Real val;
145  	               SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &val) );
146  	               SCIP_CALL( SCIPdebugAddSolVal(scip, binvar, val - lb) );
147  	            }
148  	         }
149  	#endif
150  	
151  	         /* aggregate integer and binary variable */
152  	         SCIP_CALL( SCIPaggregateVars(scip, vars[v], binvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
153  	
154  	         /* release binary variable */
155  	         SCIP_CALL( SCIPreleaseVar(scip, &binvar) );
156  	
157  	         /* it can be the case that this aggregation detects an infeasibility; for example, during the copy of the
158  	          * variable bounds from the integer variable to the binary variable, infeasibility can be detected; this can
159  	          * happen because an upper bound or a lower bound of such a variable bound variable was "just" changed and the
160  	          * varbound constraint handler, who would detect that infeasibility (since it was creating it from a varbound
161  	          * constraint), was called before that bound change was detected due to the presolving priorities;
162  	          */
163  	         if( infeasible )
164  	         {
165  	            *result = SCIP_CUTOFF;
166  	            break;
167  	         }
168  	         else if( aggregated )
169  	         {
170  	            assert(redundant);
171  	
172  	            (*nchgvartypes)++;
173  	            ++(*naggrvars);
174  	            *result = SCIP_SUCCESS;
175  	         }
176  	      }
177  	   }
178  	
179  	   /* free temporary memory */
180  	   SCIPfreeBufferArray(scip, &vars);
181  	
182  	   return SCIP_OKAY;
183  	}
184  	
185  	
186  	/*
187  	 * presolver specific interface methods
188  	 */
189  	
190  	/** creates the inttobinary presolver and includes it in SCIP */
191  	SCIP_RETCODE SCIPincludePresolInttobinary(
192  	   SCIP*                 scip                /**< SCIP data structure */
193  	   )
194  	{
195  	   SCIP_PRESOLDATA* presoldata;
196  	   SCIP_PRESOL* presolptr;
197  	
198  	   /* create inttobinary presolver data */
199  	   presoldata = NULL;
200  	
201  	   /* include presolver */
202  	   SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING,
203  	         presolExecInttobinary,
204  	         presoldata) );
205  	
206  	   assert(presolptr != NULL);
207  	
208  	   SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyInttobinary) );
209  	
210  	   return SCIP_OKAY;
211  	}
212