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   prop_dualfix.c
26   	 * @ingroup DEFPLUGINS_PROP
27   	 * @brief  fixing roundable variables to best bound
28   	 * @author Tobias Achterberg
29   	 * @author Stefan Heinz
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#include "scip/prop_dualfix.h"
35   	#include "scip/pub_message.h"
36   	#include "scip/pub_prop.h"
37   	#include "scip/pub_var.h"
38   	#include "scip/scip_general.h"
39   	#include "scip/scip_message.h"
40   	#include "scip/scip_numerics.h"
41   	#include "scip/scip_prob.h"
42   	#include "scip/scip_probing.h"
43   	#include "scip/scip_prop.h"
44   	#include "scip/scip_tree.h"
45   	#include "scip/scip_var.h"
46   	#include <string.h>
47   	
48   	#define PROP_NAME                  "dualfix"
49   	#define PROP_DESC                  "roundable variables dual fixing"
50   	#define PROP_TIMING                 SCIP_PROPTIMING_BEFORELP
51   	#define PROP_PRIORITY               +8000000 /**< propagation priority */
52   	#define PROP_FREQ                          0 /**< propagation frequency */
53   	#define PROP_DELAY                     FALSE /**< should propagation method be delayed, if other propagators found
54   	                                              *   reductions? */
55   	#define PROP_PRESOL_PRIORITY        +8000000 /**< priority of the propagator (>= 0: before, < 0: after constraint handlers) */
56   	#define PROP_PRESOL_MAXROUNDS             -1 /**< maximal number of propving rounds the propver participates in (-1: no limit) */
57   	#define PROP_PRESOLTIMING           SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */
58   	
59   	
60   	/**@name Local methods
61   	 *
62   	 * @{
63   	 */
64   	
65   	/** perform dual presolving */
66   	static
67   	SCIP_RETCODE performDualfix(
68   	   SCIP*                 scip,               /**< SCIP data structure */
69   	   int*                  nfixedvars,         /**< pointer to store number of fixed variables */
70   	   SCIP_Bool*            unbounded,          /**< pointer to store if an unboundness was detected */
71   	   SCIP_Bool*            cutoff              /**< pointer to store if a cutoff was detected */
72   	   )
73   	{
74   	   SCIP_VAR** vars;
75   	   int nvars;
76   	   int v;
77   	
78   	   /* get active problem variables */
79   	   vars = SCIPgetVars(scip);
80   	   nvars = SCIPgetNVars(scip);
81   	
82   	   /* look for fixable variables
83   	    * loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array
84   	    */
85   	   for( v = nvars - 1; v >= 0; --v )
86   	   {
87   	      SCIP_VAR* var;
88   	      SCIP_Real bound;
89   	      SCIP_Real obj;
90   	      SCIP_Bool infeasible;
91   	      SCIP_Bool fixed;
92   	
93   	      var = vars[v];
94   	      assert(var != NULL);
95   	
96   	      /* don't perform dual presolving operations on deleted variables */
97   	      if( SCIPvarIsDeleted(var) )
98   	         continue;
99   	
100  	      /* ignore already fixed variables */
101  	      if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
102  	         continue;
103  	
104  	      obj = SCIPvarGetObj(var);
105  	
106  	      /* if the objective coefficient of the variable is 0 and it may be rounded both
107  	       * up and down, then fix it to the closest feasible value to 0 */
108  	      if( SCIPisZero(scip, obj) && SCIPvarMayRoundDown(var) && SCIPvarMayRoundUp(var) )
109  	      {
110  	         SCIP_Real roundbound;
111  	
112  	         bound = SCIPvarGetLbGlobal(var);
113  	         if( SCIPisLT(scip, bound, 0.0) )
114  	         {
115  	            if( SCIPisLE(scip, 0.0, SCIPvarGetUbGlobal(var)) )
116  	               bound = 0.0;
117  	            else
118  	            {
119  	               /* try to take an integer value, only for polishing */
120  	               roundbound = SCIPfloor(scip, SCIPvarGetUbGlobal(var));
121  	
122  	               if( roundbound < bound )
123  	                  bound = SCIPvarGetUbGlobal(var);
124  	               else
125  	                  bound = roundbound;
126  	            }
127  	         }
128  	         else
129  	         {
130  	            /* try to take an integer value, only for polishing */
131  	            roundbound = SCIPceil(scip, bound);
132  	
133  	            if( roundbound < SCIPvarGetUbGlobal(var) )
134  	               bound = roundbound;
135  	         }
136  	         SCIPdebugMsg(scip, "fixing variable <%s> with objective 0 to %g\n", SCIPvarGetName(var), bound);
137  	      }
138  	      else
139  	      {
140  	         /* if it is always possible to round variable in direction of objective value, fix it to its proper bound */
141  	         if( SCIPvarMayRoundDown(var) && !SCIPisNegative(scip, obj) )
142  	         {
143  	            bound = SCIPvarGetLbGlobal(var);
144  	            if ( SCIPisInfinity(scip, -bound) )
145  	            {
146  	               /* variable can be fixed to -infinity */
147  	               if ( SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING )
148  	               {
149  	                  /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this
150  	                   * consistently. We thus have to ignore this (should better be handled in presolving). */
151  	                  continue;
152  	               }
153  	               if ( SCIPisZero(scip, obj) && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 1 )
154  	               {
155  	                  /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is
156  	                   * clever enough to set/aggregate the variable to something more useful than -infinity and do nothing
157  	                   * here. */
158  	                  continue;
159  	               }
160  	            }
161  	            SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d uplocks to lower bound %g\n",
162  	               SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL), bound);
163  	         }
164  	         else if( SCIPvarMayRoundUp(var) && !SCIPisPositive(scip, obj) )
165  	         {
166  	            bound = SCIPvarGetUbGlobal(var);
167  	            if ( SCIPisInfinity(scip, bound) )
168  	            {
169  	               /* variable can be fixed to infinity */
170  	               if ( SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING )
171  	               {
172  	                  /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this
173  	                   * consistently. We thus have to ignore this (should better be handled in presolving). */
174  	                  continue;
175  	               }
176  	               if ( SCIPisZero(scip, obj) && SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 1 )
177  	               {
178  	                  /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is
179  	                   * clever enough to set/aggregate the variable to something more useful than +infinity and do nothing
180  	                   * here */
181  	                  continue;
182  	               }
183  	            }
184  	            SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d downlocks to upper bound %g\n",
185  	               SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL), bound);
186  	         }
187  	         else
188  	            continue;
189  	      }
190  	
191  	      if( SCIPisInfinity(scip, REALABS(bound)) && !SCIPisZero(scip, obj) )
192  	      {
193  	         SCIPdebugMsg(scip, " -> unbounded fixing\n");
194  	         SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
195  	            "problem infeasible or unbounded: variable <%s> with objective %.15g can be made infinitely %s\n",
196  	            SCIPvarGetName(var), SCIPvarGetObj(var), bound < 0.0 ? "small" : "large");
197  	         *unbounded = TRUE;
198  	         return SCIP_OKAY;
199  	      }
200  	
201  	      /* apply the fixing */
202  	      SCIPdebugMsg(scip, "apply fixing of variable %s to %g\n", SCIPvarGetName(var), bound);
203  	      SCIP_CALL( SCIPfixVar(scip, var, bound, &infeasible, &fixed) );
204  	
205  	      if( infeasible )
206  	      {
207  	         SCIPdebugMsg(scip, " -> infeasible fixing\n");
208  	         *cutoff = TRUE;
209  	         return SCIP_OKAY;
210  	      }
211  	
212  	      /* SCIPfixVar only changes bounds if not already feaseq.
213  	       * Only if in presolve and not probing, variables will always be fixed.
214  	       */
215  	      assert(fixed || (SCIPisFeasEQ(scip, bound, SCIPvarGetLbLocal(var))
216  	         && SCIPisFeasEQ(scip, bound, SCIPvarGetUbLocal(var))));
217  	      (*nfixedvars)++;
218  	   }
219  	
220  	   return SCIP_OKAY;
221  	}
222  	
223  	/**@} */
224  	
225  	/**@name Callback methods
226  	 *
227  	 * @{
228  	 */
229  	
230  	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
231  	static
232  	SCIP_DECL_PROPCOPY(propCopyDualfix)
233  	{  /*lint --e{715}*/
234  	   assert(scip != NULL);
235  	   assert(prop != NULL);
236  	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
237  	
238  	   /* call inclusion method of propagator */
239  	   SCIP_CALL( SCIPincludePropDualfix(scip) );
240  	
241  	   return SCIP_OKAY;
242  	}
243  	
244  	/** presolving method of propagator */
245  	static
246  	SCIP_DECL_PROPPRESOL(propPresolDualfix)
247  	{  /*lint --e{715}*/
248  	   SCIP_Bool cutoff;
249  	   SCIP_Bool unbounded;
250  	   int oldnfixedvars;
251  	
252  	   assert(prop != NULL);
253  	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
254  	   assert(result != NULL);
255  	
256  	   *result = SCIP_DIDNOTRUN;
257  	
258  	   if( !SCIPallowStrongDualReds(scip) )
259  	      return SCIP_OKAY;
260  	
261  	   cutoff = FALSE;
262  	   unbounded = FALSE;
263  	   oldnfixedvars = *nfixedvars;
264  	
265  	   SCIP_CALL( performDualfix(scip, nfixedvars, &unbounded, &cutoff) );
266  	
267  	   /* evaluate propagation result */
268  	   if( cutoff )
269  	      *result = SCIP_CUTOFF;
270  	   else if( unbounded )
271  	      *result = SCIP_UNBOUNDED;
272  	   else if( *nfixedvars > oldnfixedvars )
273  	      *result = SCIP_SUCCESS;
274  	   else
275  	      *result = SCIP_DIDNOTFIND;
276  	
277  	   return SCIP_OKAY;
278  	}
279  	
280  	/** execution method of propagator */
281  	static
282  	SCIP_DECL_PROPEXEC(propExecDualfix)
283  	{  /*lint --e{715}*/
284  	   int nfixedvars;
285  	   SCIP_Bool cutoff;
286  	   SCIP_Bool unbounded;
287  	
288  	   assert(prop != NULL);
289  	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
290  	   assert(result != NULL);
291  	
292  	   *result = SCIP_DIDNOTRUN;
293  	
294  	   /** @warning Don't run in probing or in repropagation since this can lead to wrong conclusion
295  	    *
296  	    *  do not run if propagation w.r.t. current objective is not allowed
297  	    */
298  	   if( SCIPinProbing(scip) || SCIPinRepropagation(scip) || !SCIPallowStrongDualReds(scip) )
299  	      return SCIP_OKAY;
300  	
301  	   cutoff = FALSE;
302  	   unbounded = FALSE;
303  	   nfixedvars = 0;
304  	
305  	   SCIP_CALL( performDualfix(scip, &nfixedvars, &unbounded, &cutoff) );
306  	
307  	   /* evaluate propagation result */
308  	   if( cutoff )
309  	      *result = SCIP_CUTOFF;
310  	   else if( unbounded )
311  	      *result = SCIP_UNBOUNDED;
312  	   else if( nfixedvars > 0 )
313  	      *result = SCIP_REDUCEDDOM;
314  	   else
315  	      *result = SCIP_DIDNOTFIND;
316  	
317  	   return SCIP_OKAY;
318  	}
319  	
320  	
321  	/**@} */
322  	
323  	
324  	/** creates the dual fixing propagator and includes it in SCIP */
325  	SCIP_RETCODE SCIPincludePropDualfix(
326  	   SCIP*                 scip                /**< SCIP data structure */
327  	   )
328  	{
329  	   SCIP_PROP* prop;
330  	
331  	   /* include propagator */
332  	   SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, propExecDualfix, NULL) );
333  	   assert(prop != NULL);
334  	
335  	   SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyDualfix) );
336  	   SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolDualfix, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
337  	
338  	   return SCIP_OKAY;
339  	}
340