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_boundshift.c
26   	 * @ingroup DEFPLUGINS_PRESOL
27   	 * @brief  presolver that converts variables with domain [a,b] to variables with domain [0,b-a]
28   	 * @author Stefan Heinz
29   	 * @author Michael Winkler
30   	 */
31   	
32   	/**@todo test this presolving step to decide whether to turn it in default mode on or off */
33   	
34   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35   	
36   	#include "blockmemshell/memory.h"
37   	#include "scip/presol_boundshift.h"
38   	#include "scip/pub_message.h"
39   	#include "scip/pub_misc.h"
40   	#include "scip/pub_presol.h"
41   	#include "scip/pub_var.h"
42   	#include "scip/scip_mem.h"
43   	#include "scip/scip_message.h"
44   	#include "scip/scip_numerics.h"
45   	#include "scip/scip_param.h"
46   	#include "scip/scip_presol.h"
47   	#include "scip/scip_prob.h"
48   	#include "scip/scip_var.h"
49   	#include "scip/debug.h"
50   	#include <string.h>
51   	
52   	#define PRESOL_NAME            "boundshift"
53   	#define PRESOL_DESC            "converts variables with domain [a,b] to variables with domain [0,b-a]"
54   	#define PRESOL_PRIORITY         7900000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
55   	#define PRESOL_MAXROUNDS              0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
56   	#define PRESOL_TIMING           SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
57   	
58   	#define MAXABSBOUND             1000.0  /**< maximum absolute variable bounds for aggregation */
59   	
60   	/*
61   	 * Default parameter settings
62   	 */
63   	
64   	#define DEFAULT_MAXSHIFT      SCIP_LONGINT_MAX  /**< absolute value of maximum shift */
65   	#define DEFAULT_FLIPPING                  TRUE  /**< is flipping allowed? */
66   	#define DEFAULT_INTEGER                   TRUE  /**< are only integer ranges shifted  */
67   	
68   	/*
69   	 * Data structures
70   	 */
71   	
72   	/** presolver data */
73   	struct SCIP_PresolData
74   	{
75   	   SCIP_Longint          maxshift;           /**< absolute value of maximum shift */
76   	   SCIP_Bool             flipping;           /**< is flipping allowed? */
77   	   SCIP_Bool             integer;            /**< shift only integer values? */
78   	};
79   	
80   	
81   	/*
82   	 * Local methods
83   	 */
84   	
85   	/*
86   	 * Callback methods of presolver
87   	 */
88   	
89   	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
90   	static
91   	SCIP_DECL_PRESOLCOPY(presolCopyBoundshift)
92   	{  /*lint --e{715}*/
93   	   assert(scip != NULL);
94   	   assert(presol != NULL);
95   	   assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
96   	
97   	   /* call inclusion method of presolver */
98   	   SCIP_CALL( SCIPincludePresolBoundshift(scip) );
99   	
100  	   return SCIP_OKAY;
101  	}
102  	
103  	
104  	/** destructor of presolver to free user data (called when SCIP is exiting) */
105  	/**! [SnippetPresolFreeBoundshift] */
106  	static
107  	SCIP_DECL_PRESOLFREE(presolFreeBoundshift)
108  	{  /*lint --e{715}*/   
109  	   SCIP_PRESOLDATA* presoldata;
110  	
111  	   /* free presolver data */
112  	   presoldata = SCIPpresolGetData(presol);
113  	   assert(presoldata != NULL);
114  	
115  	   SCIPfreeBlockMemory(scip, &presoldata);
116  	   SCIPpresolSetData(presol, NULL);
117  	
118  	   return SCIP_OKAY;
119  	}
120  	/**! [SnippetPresolFreeBoundshift] */
121  	
122  	
123  	/** presolving execution method */
124  	static
125  	SCIP_DECL_PRESOLEXEC(presolExecBoundshift)
126  	{  /*lint --e{715}*/
127  	   SCIP_PRESOLDATA* presoldata;
128  	   SCIP_VAR** scipvars;
129  	   SCIP_VAR** vars;
130  	   int nbinvars;
131  	   int nvars;
132  	   int v;
133  	
134  	   assert(scip != NULL);
135  	   assert(presol != NULL);
136  	   assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
137  	   assert(result != NULL);
138  	
139  	   *result = SCIP_DIDNOTRUN;
140  	
141  	   if( SCIPdoNotAggr(scip) )
142  	      return SCIP_OKAY;
143  	
144  	   /* get presolver data */
145  	   presoldata = SCIPpresolGetData(presol);
146  	   assert(presoldata != NULL);
147  	
148  	   /* get the problem variables */
149  	   scipvars = SCIPgetVars(scip);
150  	   nbinvars = SCIPgetNBinVars(scip);
151  	   nvars = SCIPgetNVars(scip) - nbinvars;
152  	
153  	   if( nvars == 0 )
154  	      return SCIP_OKAY;
155  	
156  	   *result = SCIP_DIDNOTFIND;
157  	
158  	   /* copy the integer/continuous variables into an own array, since adding new variables affects the left-most slots in
159  	    * the array and thereby interferes with our search loop
160  	    */
161  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nvars) );
162  	
163  	   /* scan the integer, implicit, and continuous variables for possible conversion */
164  	   for( v = nvars - 1; v >= 0; --v )
165  	   {
166  	      SCIP_VAR* var = vars[v];
167  	      SCIP_Real lb;
168  	      SCIP_Real ub;
169  	
170  	      assert(SCIPvarGetType(var) != SCIP_VARTYPE_BINARY);
171  	
172  	      /* do not shift non-active (fixed or (multi-)aggregated) variables */
173  	      if( !SCIPvarIsActive(var) )
174  	         continue;
175  	
176  	      /* get current variable's bounds */
177  	      lb = SCIPvarGetLbGlobal(var);
178  	      ub = SCIPvarGetUbGlobal(var);
179  	
180  	      /* it can happen that the variable bounds of integer variables have not been propagated yet or contain
181  	       * some small noise; this will result in an aggregation that might trigger assertions when updating bounds of
182  	       * aggregated variables (see #1817)
183  	       */
184  	      if( SCIPvarIsIntegral(var) )
185  	      {
186  	         assert(SCIPisIntegral(scip, lb));
187  	         assert(SCIPisIntegral(scip, ub));
188  	
189  	         lb = SCIPadjustedVarLb(scip, var, lb);
190  	         ub = SCIPadjustedVarUb(scip, var, ub);
191  	      }
192  	
193  	      assert( SCIPisLE(scip, lb, ub) );
194  	      if( SCIPisEQ(scip, lb, ub) )
195  	         continue;
196  	      if( presoldata->integer && !SCIPisIntegral(scip, ub - lb) ) 
197  	         continue;
198  	
199  	      /* check if bounds are shiftable */
200  	      if( !SCIPisEQ(scip, lb, 0.0) &&                           /* lower bound != 0.0 */
201  	         SCIPisLT(scip, ub, SCIPinfinity(scip)) &&              /* upper bound != infinity */
202  	         SCIPisGT(scip, lb, -SCIPinfinity(scip)) &&             /* lower bound != -infinity */
203  	         SCIPisLT(scip, ub - lb, (SCIP_Real) presoldata->maxshift) &&      /* less than max shifting */
204  	         SCIPisLE(scip, REALABS(lb), MAXABSBOUND) &&            /* ensures a small constant in aggregation */
205  	         SCIPisLE(scip, REALABS(ub), MAXABSBOUND) )             /* ensures a small constant in aggregation */
206  	      {
207  	         SCIP_VAR* newvar;
208  	         char newvarname[SCIP_MAXSTRLEN];
209  	         SCIP_Bool infeasible;
210  	         SCIP_Bool redundant;
211  	         SCIP_Bool aggregated;
212  	
213  	         SCIPdebugMsg(scip, "convert range <%s>[%g,%g] to [%g,%g]\n", SCIPvarGetName(var), lb, ub, 0.0, (ub - lb) );
214  	
215  	         /* create new variable */
216  	         (void) SCIPsnprintf(newvarname, SCIP_MAXSTRLEN, "%s_shift", SCIPvarGetName(var));
217  	         SCIP_CALL( SCIPcreateVar(scip, &newvar, newvarname, 0.0, (ub - lb), 0.0, SCIPvarGetType(var),
218  	               SCIPvarIsInitial(var), SCIPvarIsRemovable(var), NULL, NULL, NULL, NULL, NULL) );
219  	         SCIP_CALL( SCIPaddVar(scip, newvar) );
220  	
221  	#ifdef WITH_DEBUG_SOLUTION
222  	         if( SCIPdebugIsMainscip(scip) )
223  	         {
224  	            /* calculate and store debug solution value of shift variable */
225  	            SCIP_Real val;
226  	
227  	            SCIP_CALL( SCIPdebugGetSolVal(scip, var, &val) );
228  	            SCIPdebugMsg(scip, "debug solution value: <%s> = %g", SCIPvarGetName(var), val);
229  	
230  	            if( presoldata->flipping )
231  	            {
232  	               if( REALABS(ub) < REALABS(lb) )
233  	                  val = ub - val;
234  	               else
235  	                  val = val - lb;
236  	            }
237  	            else
238  	            {
239  	               val = val - lb;
240  	            }
241  	            SCIPdebugMsgPrint(scip, " -> <%s> = %g\n", SCIPvarGetName(newvar), val);
242  	
243  	            SCIP_CALL( SCIPdebugAddSolVal(scip, newvar, val) );
244  	         }
245  	#endif
246  	
247  	         /* aggregate old variable with new variable */
248  	         if( presoldata->flipping )
249  	         {
250  	            if( REALABS(ub) < REALABS(lb) )
251  	            {
252  	               SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, 1.0, ub, &infeasible, &redundant, &aggregated) );
253  	            }
254  	            else
255  	            {
256  	               SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
257  	            }
258  	         }
259  	         else
260  	         {
261  	            SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
262  	         }
263  	
264  	         if( infeasible )
265  	            *result = SCIP_CUTOFF;
266  	         else
267  	         {
268  	            assert(redundant);
269  	            assert(aggregated);
270  	            SCIPdebugMsg(scip, "var <%s> with bounds [%f,%f] has obj %f\n",
271  	               SCIPvarGetName(newvar), SCIPvarGetLbGlobal(newvar), SCIPvarGetUbGlobal(newvar), SCIPvarGetObj(newvar));
272  	
273  	            /* take care of statistics */
274  	            (*naggrvars)++;
275  	            *result = SCIP_SUCCESS;
276  	         }
277  	
278  	         /* release variable */
279  	         SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
280  	      }
281  	   }
282  	
283  	   /* free temporary memory */
284  	   SCIPfreeBufferArray(scip, &vars);
285  	
286  	   return SCIP_OKAY;
287  	}
288  	
289  	
290  	/*
291  	 * presolver specific interface methods
292  	 */
293  	
294  	/** creates the boundshift presolver and includes it in SCIP */
295  	SCIP_RETCODE SCIPincludePresolBoundshift(
296  	   SCIP*                 scip                /**< SCIP data structure */
297  	   )
298  	{
299  	   SCIP_PRESOLDATA* presoldata;
300  	   SCIP_PRESOL* presolptr;
301  	
302  	   /* create boundshift presolver data */
303  	   SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
304  	
305  	   /* include presolver */
306  	   SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING,
307  	         presolExecBoundshift,
308  	         presoldata) );
309  	
310  	   assert(presolptr != NULL);
311  	
312  	   SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyBoundshift) );
313  	   SCIP_CALL( SCIPsetPresolFree(scip, presolptr, presolFreeBoundshift) );
314  	
315  	   /* add probing presolver parameters */
316  	   SCIP_CALL( SCIPaddLongintParam(scip,
317  	         "presolving/boundshift/maxshift",
318  	         "absolute value of maximum shift",
319  	         &presoldata->maxshift, TRUE, DEFAULT_MAXSHIFT, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
320  	
321  	   SCIP_CALL( SCIPaddBoolParam(scip,
322  	         "presolving/boundshift/flipping",
323  	         "is flipping allowed (multiplying with -1)?",
324  	         &presoldata->flipping, TRUE, DEFAULT_FLIPPING, NULL, NULL) );
325  	
326  	   SCIP_CALL( SCIPaddBoolParam(scip,
327  	         "presolving/boundshift/integer",
328  	         "shift only integer ranges?",
329  	         &presoldata->integer, TRUE, DEFAULT_INTEGER, NULL, NULL) );
330  	
331  	   return SCIP_OKAY;
332  	}
333