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_redcost.c
26   	 * @ingroup DEFPLUGINS_PROP
27   	 * @brief  propagator using the LP reduced cost and the cutoff bound
28   	 * @author Tobias Achterberg
29   	 * @author Stefan Heinz
30   	 * @author Matthias Miltenberger
31   	 * @author Michael Winkler
32   	 *
33   	 * This propagator uses the reduced cost of an optimal solved LP relaxation to propagate the variables against the
34   	 * cutoff bound.
35   	 */
36   	
37   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38   	
39   	#include "lpi/type_lpi.h"
40   	#include "scip/prop_redcost.h"
41   	#include "scip/pub_lp.h"
42   	#include "scip/pub_message.h"
43   	#include "scip/pub_prop.h"
44   	#include "scip/pub_tree.h"
45   	#include "scip/pub_var.h"
46   	#include "scip/scip_branch.h"
47   	#include "scip/scip_general.h"
48   	#include "scip/scip_lp.h"
49   	#include "scip/scip_mem.h"
50   	#include "scip/scip_message.h"
51   	#include "scip/scip_numerics.h"
52   	#include "scip/scip_param.h"
53   	#include "scip/scip_pricer.h"
54   	#include "scip/scip_prob.h"
55   	#include "scip/scip_prop.h"
56   	#include "scip/scip_solvingstats.h"
57   	#include "scip/scip_tree.h"
58   	#include "scip/scip_var.h"
59   	#include <string.h>
60   	
61   	/**@name Propagator properties
62   	 *
63   	 * @{
64   	 */
65   	
66   	#define PROP_NAME              "redcost"
67   	#define PROP_DESC              "reduced cost strengthening propagator"
68   	#define PROP_TIMING             SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
69   	#define PROP_PRIORITY          +1000000 /**< propagator priority */
70   	#define PROP_FREQ                     1 /**< propagator frequency */
71   	#define PROP_DELAY                FALSE /**< should propagation method be delayed, if other propagators found reductions? */
72   	
73   	/**@} */
74   	
75   	
76   	/**@name Default parameter values
77   	 *
78   	 * @{
79   	 */
80   	
81   	#define DEFAULT_CONTINUOUS        FALSE /**< should reduced cost fixing be also applied to continuous variables? */
82   	#define DEFAULT_USEIMPLICS        FALSE /**< should implications be used to strength the reduced cost for binary variables? */
83   	#define DEFAULT_FORCE             FALSE /**< should the propagator be forced even if active pricer are present? Note that
84   	                                         *   the reductions are always valid, but installing an upper bound on priced
85   	                                         *   variables may lead to problems in pricing (existing variables at their upper
86   	                                         *   bound may be priced again since they may have negative reduced costs) */
87   	
88   	/**@} */
89   	
90   	
91   	/*
92   	 * Data structures
93   	 */
94   	
95   	
96   	/** propagator data */
97   	struct SCIP_PropData
98   	{
99   	   SCIP_Bool             continuous;         /**< should reduced cost fixing be also applied to continuous variables? */
100  	   SCIP_Real             maxredcost;         /**< maximum reduced cost of a single binary variable */
101  	   SCIP_Bool             usefullimplics;     /**< are the implied reduced cost useful */
102  	   SCIP_Bool             useimplics;         /**< should implications be used to strength the reduced cost for binary variables? */
103  	   SCIP_Bool             force;              /**< should the propagator be forced even if active pricer are present? */
104  	};
105  	
106  	
107  	/**@name Local methods
108  	 *
109  	 * @{
110  	 */
111  	
112  	/** propagate the given binary variable/column using the root reduced cost stored in the SCIP internal data structures
113  	 *  and check if the implications can be useful. Depending on that implications are used or not used during the search to
114  	 *  strength the reduced costs.
115  	 */
116  	static
117  	SCIP_RETCODE propagateRootRedcostBinvar(
118  	   SCIP*                 scip,               /**< SCIP data structure */
119  	   SCIP_PROPDATA*        propdata,           /**< propagator data structure */
120  	   SCIP_VAR*             var,                /**< variable to use for propagation */
121  	   SCIP_COL*             col,                /**< LP column of the variable */
122  	   SCIP_Real             cutoffbound,        /**< the current cutoff bound */
123  	   int*                  nchgbds             /**< pointer to count the number of bound changes */
124  	   )
125  	{
126  	   SCIP_Real rootredcost;
127  	   SCIP_Real rootsol;
128  	   SCIP_Real rootlpobjval;
129  	
130  	   assert(scip != NULL);
131  	   assert(SCIPgetDepth(scip) == 0);
132  	
133  	   /* skip binary variable if it is locally fixed */
134  	   if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
135  	      return SCIP_OKAY;
136  	
137  	   rootredcost = SCIPvarGetBestRootRedcost(var);
138  	   rootsol = SCIPvarGetBestRootSol(var);
139  	   rootlpobjval = SCIPvarGetBestRootLPObjval(var);
140  	
141  	   if( SCIPisDualfeasZero(scip, rootredcost) )
142  	      return SCIP_OKAY;
143  	
144  	   assert(rootlpobjval != SCIP_INVALID); /*lint !e777*/
145  	
146  	   if( rootsol > 0.5 )
147  	   {
148  	      /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
149  	       * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
150  	       * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
151  	       * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
152  	       */
153  	      assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, rootredcost));
154  	
155  	      /* update maximum reduced cost of a single binary variable */
156  	      propdata->maxredcost = MAX(propdata->maxredcost, -rootredcost);
157  	
158  	      if( rootlpobjval - rootredcost > cutoffbound )
159  	      {
160  	         SCIPdebugMsg(scip, "globally fix binary variable <%s> to 1.0\n", SCIPvarGetName(var));
161  	
162  	         SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
163  	         (*nchgbds)++;
164  	         return SCIP_OKAY;
165  	      }
166  	   }
167  	   else
168  	   {
169  	      /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
170  	       * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
171  	       * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
172  	       * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
173  	       */
174  	      assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, rootredcost));
175  	
176  	      /* update maximum reduced cost of a single binary variable */
177  	      propdata->maxredcost = MAX(propdata->maxredcost, rootredcost);
178  	
179  	      if( rootlpobjval + rootredcost > cutoffbound )
180  	      {
181  	         SCIPdebugMsg(scip, "globally fix binary variable <%s> to 0.0\n", SCIPvarGetName(var));
182  	
183  	         SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
184  	         (*nchgbds)++;
185  	         return SCIP_OKAY;
186  	      }
187  	   }
188  	
189  	   /* evaluate if the implications are useful; the implications are seen to be useful if they provide an increase for
190  	    * the root reduced costs
191  	    */
192  	   if( !propdata->usefullimplics )
193  	   {
194  	      SCIP_Real lbredcost;
195  	      SCIP_Real ubredcost;
196  	
197  	      lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE);
198  	      assert(!SCIPisDualfeasPositive(scip, lbredcost));
199  	
200  	      ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE);
201  	      assert(!SCIPisDualfeasNegative(scip, ubredcost));
202  	
203  	      switch( SCIPcolGetBasisStatus(col) )
204  	      {
205  	      case SCIP_BASESTAT_LOWER:
206  	         ubredcost -= SCIPgetVarRedcost(scip, var);
207  	
208  	         /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
209  	          * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
210  	          * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
211  	          * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
212  	          */
213  	         assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, ubredcost));
214  	         break;
215  	
216  	      case SCIP_BASESTAT_UPPER:
217  	         lbredcost -= SCIPgetVarRedcost(scip, var);
218  	
219  	         /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
220  	          * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
221  	          * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
222  	          * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
223  	          */
224  	         assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, lbredcost));
225  	         break;
226  	
227  	      case SCIP_BASESTAT_BASIC:
228  	      case SCIP_BASESTAT_ZERO:
229  	      default:
230  	         break;
231  	      }
232  	
233  	      propdata->usefullimplics = (lbredcost < 0.0) || (ubredcost > 0.0);
234  	   }
235  	
236  	   return SCIP_OKAY;
237  	}
238  	
239  	/** propagate the given binary variable/column using the reduced cost */
240  	static
241  	SCIP_RETCODE propagateRedcostBinvar(
242  	   SCIP*                 scip,               /**< SCIP data structure */
243  	   SCIP_PROPDATA*        propdata,           /**< propagator data structure */
244  	   SCIP_VAR*             var,                /**< variable to use for propagation */
245  	   SCIP_COL*             col,                /**< LP column of the variable */
246  	   SCIP_Real             requiredredcost,    /**< required reduset cost to be able to fix a binary variable */
247  	   int*                  nchgbds,            /**< pointer to count the number of bound changes */
248  	   SCIP_Bool*            cutoff              /**< pointer to store if an cutoff was detected */
249  	   )
250  	{
251  	   SCIP_Real lbredcost;
252  	   SCIP_Real ubredcost;
253  	   SCIP_Real redcost;
254  	
255  	   /* skip binary variable if it is locally fixed */
256  	   if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
257  	      return SCIP_OKAY;
258  	
259  	   /* first use the redcost cost to fix the binary variable */
260  	   switch( SCIPcolGetBasisStatus(col) )
261  	   {
262  	   case SCIP_BASESTAT_LOWER:
263  	      redcost = SCIPgetVarRedcost(scip, var);
264  	
265  	      /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
266  	       * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
267  	       * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
268  	       * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
269  	       */
270  	      assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, redcost));
271  	
272  	      if( redcost > requiredredcost )
273  	      {
274  	         SCIPdebugMsg(scip, "variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>)\n",
275  	            SCIPvarGetName(var), requiredredcost, redcost);
276  	
277  	         SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
278  	         (*nchgbds)++;
279  	         return SCIP_OKAY;
280  	      }
281  	      break;
282  	
283  	   case SCIP_BASESTAT_UPPER:
284  	      redcost = SCIPgetVarRedcost(scip, var);
285  	
286  	      /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
287  	       * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
288  	       * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
289  	       * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
290  	       */
291  	      assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, redcost));
292  	
293  	      if( -redcost > requiredredcost )
294  	      {
295  	         SCIPdebugMsg(scip, "variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>)\n",
296  	            SCIPvarGetName(var), requiredredcost, redcost);
297  	
298  	         SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
299  	         (*nchgbds)++;
300  	         return SCIP_OKAY;
301  	      }
302  	      break;
303  	
304  	   case SCIP_BASESTAT_BASIC:
305  	      return SCIP_OKAY;
306  	
307  	   case SCIP_BASESTAT_ZERO:
308  	      /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
309  	       * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
310  	       * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
311  	       * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
312  	       */
313  	      assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasZero(scip, SCIPgetColRedcost(scip, col)));
314  	      return SCIP_OKAY;
315  	
316  	   default:
317  	      SCIPerrorMessage("invalid basis state\n");
318  	      return SCIP_INVALIDDATA;
319  	   }
320  	
321  	   /* second, if the implications should be used and if the implications are seen to be promising use the implied
322  	    * reduced costs to fix the binary variable
323  	    */
324  	   if( propdata->useimplics && propdata->usefullimplics )
325  	   {
326  	      /* collect implied reduced costs if the variable would be fixed to its lower bound */
327  	      lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE);
328  	
329  	      /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
330  	       * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
331  	       * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
332  	       * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
333  	       */
334  	      assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, lbredcost)
335  	            || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
336  	
337  	      /* collect implied reduced costs if the variable would be fixed to its upper bound */
338  	      ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE);
339  	      assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, ubredcost)
340  	            || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
341  	
342  	      if( -lbredcost > requiredredcost && ubredcost > requiredredcost )
343  	      {
344  	         SCIPdebugMsg(scip, "variable <%s>: cutoff (requiredredcost <%g>, lbredcost <%g>, ubredcost <%g>)\n",
345  	            SCIPvarGetName(var), requiredredcost, lbredcost, ubredcost);
346  	
347  	         (*cutoff) = TRUE;
348  	      }
349  	      else if( -lbredcost > requiredredcost )
350  	      {
351  	         SCIPdebugMsg(scip, "variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>, lbredcost <%g>)\n",
352  	            SCIPvarGetName(var), requiredredcost, redcost, lbredcost);
353  	
354  	         SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
355  	         (*nchgbds)++;
356  	      }
357  	      else if( ubredcost > requiredredcost )
358  	      {
359  	         SCIPdebugMsg(scip, "variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>, ubredcost <%g>)\n",
360  	            SCIPvarGetName(var), requiredredcost, redcost, ubredcost);
361  	
362  	         SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
363  	         (*nchgbds)++;
364  	      }
365  	
366  	      /* update maximum reduced cost of a single binary variable */
367  	      propdata->maxredcost = MAX3(propdata->maxredcost, -lbredcost, ubredcost);
368  	   }
369  	
370  	   return SCIP_OKAY;
371  	}
372  	
373  	/** propagate the given none binary variable/column using the reduced cost */
374  	static
375  	SCIP_RETCODE propagateRedcostVar(
376  	   SCIP*                 scip,               /**< SCIP data structure */
377  	   SCIP_VAR*             var,                /**< variable to use for propagation */
378  	   SCIP_COL*             col,                /**< LP column of the variable */
379  	   SCIP_Real             lpobjval,           /**< objective value of the current LP */
380  	   SCIP_Real             cutoffbound,        /**< the current cutoff bound */
381  	   int*                  nchgbds             /**< pointer to count the number of bound changes */
382  	   )
383  	{
384  	   SCIP_Real redcost;
385  	
386  	   switch( SCIPcolGetBasisStatus(col) )
387  	   {
388  	   case SCIP_BASESTAT_LOWER:
389  	      redcost = SCIPgetColRedcost(scip, col);
390  	
391  	      /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
392  	       * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
393  	       * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
394  	       * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
395  	       */
396  	      assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, redcost)
397  	            || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
398  	
399  	      if( SCIPisDualfeasPositive(scip, redcost) )
400  	      {
401  	         SCIP_Real oldlb;
402  	         SCIP_Real oldub;
403  	
404  	         oldlb = SCIPvarGetLbLocal(var);
405  	         oldub = SCIPvarGetUbLocal(var);
406  	         assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col)));
407  	         assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col)));
408  	
409  	         if( SCIPisFeasLT(scip, oldlb, oldub) )
410  	         {
411  	            SCIP_Real newub;
412  	            SCIP_Bool strengthen;
413  	
414  	            /* calculate reduced cost based bound */
415  	            newub = (cutoffbound - lpobjval) / redcost + oldlb;
416  	
417  	            /* check, if new bound is good enough:
418  	             *  - integer variables: take all possible strengthenings
419  	             *  - continuous variables: strengthening must cut part of the variable's dynamic range, and
420  	             *                          at least 20% of the current domain
421  	             */
422  	            if( SCIPvarIsIntegral(var) )
423  	            {
424  	               newub = SCIPadjustedVarUb(scip, var, newub);
425  	               strengthen = (newub < oldub - 0.5);
426  	            }
427  	            else
428  	               strengthen = (newub < SCIPcolGetMaxPrimsol(col) && newub <= 0.2 * oldlb + 0.8 * oldub);
429  	
430  	            if( strengthen )
431  	            {
432  	               /* strengthen upper bound */
433  	               SCIPdebugMsg(scip, "redcost strengthening upper bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
434  	                  SCIPvarGetName(var), oldlb, oldub, oldlb, newub, cutoffbound, lpobjval, redcost);
435  	               SCIP_CALL( SCIPchgVarUb(scip, var, newub) );
436  	               (*nchgbds)++;
437  	            }
438  	         }
439  	      }
440  	      break;
441  	
442  	   case SCIP_BASESTAT_BASIC:
443  	      break;
444  	
445  	   case SCIP_BASESTAT_UPPER:
446  	      redcost = SCIPgetColRedcost(scip, col);
447  	
448  	      /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
449  	       * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
450  	       * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
451  	       * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
452  	       */
453  	      assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, redcost)
454  	            || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
455  	
456  	      if( SCIPisDualfeasNegative(scip, redcost) )
457  	      {
458  	         SCIP_Real oldlb;
459  	         SCIP_Real oldub;
460  	
461  	         oldlb = SCIPvarGetLbLocal(var);
462  	         oldub = SCIPvarGetUbLocal(var);
463  	         assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col)));
464  	         assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col)));
465  	
466  	         if( SCIPisFeasLT(scip, oldlb, oldub) )
467  	         {
468  	            SCIP_Real newlb;
469  	            SCIP_Bool strengthen;
470  	
471  	            /* calculate reduced cost based bound */
472  	            newlb = (cutoffbound - lpobjval) / redcost + oldub;
473  	
474  	            /* check, if new bound is good enough:
475  	             *  - integer variables: take all possible strengthenings
476  	             *  - continuous variables: strengthening must cut part of the variable's dynamic range, and
477  	             *                          at least 20% of the current domain
478  	             */
479  	            if( SCIPvarIsIntegral(var) )
480  	            {
481  	               newlb = SCIPadjustedVarLb(scip, var, newlb);
482  	               strengthen = (newlb > oldlb + 0.5);
483  	            }
484  	            else
485  	               strengthen = (newlb > SCIPcolGetMinPrimsol(col) && newlb >= 0.8 * oldlb + 0.2 * oldub);
486  	
487  	            /* check, if new bound is good enough: at least 20% strengthening for continuous variables */
488  	            if( strengthen )
489  	            {
490  	               /* strengthen lower bound */
491  	               SCIPdebugMsg(scip, "redcost strengthening lower bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
492  	                  SCIPvarGetName(var), oldlb, oldub, newlb, oldub, cutoffbound, lpobjval, redcost);
493  	               SCIP_CALL( SCIPchgVarLb(scip, var, newlb) );
494  	               (*nchgbds)++;
495  	            }
496  	         }
497  	      }
498  	      break;
499  	
500  	   case SCIP_BASESTAT_ZERO:
501  	      /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
502  	       * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
503  	       * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
504  	       * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
505  	       */
506  	      assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasZero(scip, SCIPgetColRedcost(scip, col)));
507  	      break;
508  	
509  	   default:
510  	      SCIPerrorMessage("invalid basis state\n");
511  	      return SCIP_INVALIDDATA;
512  	   }
513  	
514  	   return SCIP_OKAY;
515  	}
516  	
517  	/**@} */
518  	
519  	/**@name Callback methods of propagator
520  	 *
521  	 * @{
522  	 */
523  	
524  	/** copy method for propagator plugins (called when SCIP copies plugins) */
525  	static
526  	SCIP_DECL_PROPCOPY(propCopyRedcost)
527  	{  /*lint --e{715}*/
528  	   assert(scip != NULL);
529  	   assert(prop != NULL);
530  	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
531  	
532  	   /* call inclusion method of constraint handler */
533  	   SCIP_CALL( SCIPincludePropRedcost(scip) );
534  	
535  	   return SCIP_OKAY;
536  	}
537  	
538  	/** destructor of propagator to free user data (called when SCIP is exiting) */
539  	/**! [SnippetPropFreeRedcost] */
540  	static
541  	SCIP_DECL_PROPFREE(propFreeRedcost)
542  	{  /*lint --e{715}*/
543  	   SCIP_PROPDATA* propdata;
544  	
545  	   /* free propagator data */
546  	   propdata = SCIPpropGetData(prop);
547  	   assert(propdata != NULL);
548  	
549  	   SCIPfreeBlockMemory(scip, &propdata);
550  	
551  	   SCIPpropSetData(prop, NULL);
552  	
553  	   return SCIP_OKAY;
554  	}
555  	/**! [SnippetPropFreeRedcost] */
556  	
557  	/** solving process initialization method of propagator (called when branch and bound process is about to begin) */
558  	static
559  	SCIP_DECL_PROPINITSOL(propInitsolRedcost)
560  	{
561  	   SCIP_PROPDATA* propdata;
562  	
563  	   propdata = SCIPpropGetData(prop);
564  	   assert(propdata != NULL);
565  	
566  	   propdata->usefullimplics = FALSE;
567  	   propdata->maxredcost = 0.0;
568  	
569  	   return SCIP_OKAY;
570  	}
571  	
572  	/** reduced cost propagation method for an LP solution */
573  	static
574  	SCIP_DECL_PROPEXEC(propExecRedcost)
575  	{  /*lint --e{715}*/
576  	   SCIP_PROPDATA* propdata;
577  	   SCIP_COL** cols;
578  	   SCIP_Real requiredredcost;
579  	   SCIP_Real cutoffbound;
580  	   SCIP_Real lpobjval;
581  	   SCIP_Bool propbinvars;
582  	   SCIP_Bool cutoff;
583  	   int nchgbds;
584  	   int ncols;
585  	   int c;
586  	
587  	   *result = SCIP_DIDNOTRUN;
588  	
589  	   /* in case we have a zero objective function, we skip the reduced cost propagator */
590  	   if( SCIPgetNObjVars(scip) == 0 )
591  	      return SCIP_OKAY;
592  	
593  	   /* propagator can only be applied during solving stage */
594  	   if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING )
595  	      return SCIP_OKAY;
596  	
597  	   /* we cannot apply reduced cost fixing, if we want to solve exactly */
598  	   /**@todo implement reduced cost fixing with interval arithmetics */
599  	   if( SCIPisExactSolve(scip) )
600  	      return SCIP_OKAY;
601  	
602  	   /* only call propagator, if the current node has an LP */
603  	   if( !SCIPhasCurrentNodeLP(scip) )
604  	      return SCIP_OKAY;
605  	
606  	   /* only call propagator, if an optimal LP solution is at hand */
607  	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
608  	      return SCIP_OKAY;
609  	
610  	   /* only call propagator, if the current LP is a valid relaxation */
611  	   if( !SCIPisLPRelax(scip) )
612  	      return SCIP_OKAY;
613  	
614  	   /* we cannot apply reduced cost strengthening, if no simplex basis is available */
615  	   if( !SCIPisLPSolBasic(scip) )
616  	      return SCIP_OKAY;
617  	
618  	   /* do not run if propagation w.r.t. objective is not allowed */
619  	   if( !SCIPallowWeakDualReds(scip) )
620  	      return SCIP_OKAY;
621  	
622  	   /* get current cutoff bound */
623  	   cutoffbound = SCIPgetCutoffbound(scip);
624  	
625  	   /* reduced cost strengthening can only be applied, if we have a finite cutoff */
626  	   if( SCIPisInfinity(scip, cutoffbound) )
627  	      return SCIP_OKAY;
628  	
629  	   /* get LP columns */
630  	   cols = SCIPgetLPCols(scip);
631  	   ncols = SCIPgetNLPCols(scip);
632  	
633  	   /* do nothing if the LP has no columns (is empty) */
634  	   if( ncols == 0 )
635  	      return SCIP_OKAY;
636  	
637  	   /* get propagator data */
638  	   propdata = SCIPpropGetData(prop);
639  	   assert(propdata != NULL);
640  	
641  	   /* do nothing if active pricer are present and force flag is not TRUE */
642  	   if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
643  	      return SCIP_OKAY;
644  	
645  	   /* check if all integral variables are fixed and the continuous variables should not be propagated */
646  	   if( !propdata->continuous && SCIPgetNPseudoBranchCands(scip) == 0 )
647  	      return SCIP_OKAY;
648  	
649  	   /* get LP objective value */
650  	   lpobjval = SCIPgetLPObjval(scip);
651  	
652  	   /* check if binary variables should be propagated */
653  	   propbinvars = (SCIPgetDepth(scip) == 0) || (cutoffbound - lpobjval < 5 * propdata->maxredcost);
654  	
655  	   /* skip the propagator if the problem has only binary variables and those should not be propagated */
656  	   if( !propbinvars && SCIPgetNVars(scip) == SCIPgetNBinVars(scip) )
657  	      return SCIP_OKAY;
658  	
659  	   *result = SCIP_DIDNOTFIND;
660  	   cutoff = FALSE;
661  	   nchgbds = 0;
662  	
663  	   /* compute the required reduced cost which are needed for a binary variable to be fixed */
664  	   requiredredcost = cutoffbound - lpobjval;
665  	
666  	   SCIPdebugMsg(scip, "lpobjval <%g>, cutoffbound <%g>, max reduced <%g>, propgate binary %u, use implics %u\n",
667  	      lpobjval, cutoffbound, propdata->maxredcost, propbinvars, propdata->usefullimplics);
668  	
669  	   /* check reduced costs for non-basic columns */
670  	   for( c = 0; c < ncols && !cutoff; ++c )
671  	   {
672  	      SCIP_VAR* var;
673  	
674  	      var = SCIPcolGetVar(cols[c]);
675  	
676  	      /* skip continuous variables in case the corresponding parameter is set */
677  	      if( !propdata->continuous && !SCIPvarIsIntegral(var) )
678  	         continue;
679  	
680  	      if( SCIPvarIsBinary(var) )
681  	      {
682  	         if( propbinvars )
683  	         {
684  	            if( SCIPgetDepth(scip) == 0 )
685  	            {
686  	               SCIP_CALL( propagateRootRedcostBinvar(scip, propdata, var, cols[c], cutoffbound, &nchgbds) );
687  	            }
688  	            else
689  	            {
690  	               SCIP_CALL( propagateRedcostBinvar(scip, propdata, var, cols[c], requiredredcost, &nchgbds, &cutoff) );
691  	            }
692  	         }
693  	      }
694  	      else
695  	      {
696  	         SCIP_CALL( propagateRedcostVar(scip, var, cols[c], lpobjval, cutoffbound, &nchgbds) );
697  	      }
698  	   }
699  	
700  	   if( cutoff )
701  	   {
702  	      *result = SCIP_CUTOFF;
703  	
704  	      SCIPdebugMsg(scip, "node %" SCIP_LONGINT_FORMAT ": detected cutoff\n",
705  	         SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
706  	   }
707  	   else if( nchgbds > 0 )
708  	   {
709  	      *result = SCIP_REDUCEDDOM;
710  	
711  	      SCIPdebugMsg(scip, "node %" SCIP_LONGINT_FORMAT ": %d bound changes (max redcost <%g>)\n",
712  	         SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) , nchgbds, propdata->maxredcost);
713  	   }
714  	
715  	   return SCIP_OKAY;
716  	}
717  	
718  	/**@} */
719  	
720  	/** creates the redcost propagator and includes it in SCIP */
721  	SCIP_RETCODE SCIPincludePropRedcost(
722  	   SCIP*                 scip                /**< SCIP data structure */
723  	   )
724  	{
725  	   SCIP_PROPDATA* propdata;
726  	   SCIP_PROP* prop;
727  	
728  	   /* create redcost propagator data */
729  	   SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
730  	
731  	   /* include propagator */
732  	   SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
733  	         propExecRedcost, propdata) );
734  	
735  	   assert(prop != NULL);
736  	
737  	   /* set optional callbacks via setter functions */
738  	   SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyRedcost) );
739  	   SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolRedcost) );
740  	   SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeRedcost) );
741  	
742  	   /* add redcost propagator parameters */
743  	   SCIP_CALL( SCIPaddBoolParam(scip,
744  	         "propagating/" PROP_NAME "/continuous",
745  	         "should reduced cost fixing be also applied to continuous variables?",
746  	         &propdata->continuous, FALSE, DEFAULT_CONTINUOUS, NULL, NULL) );
747  	   SCIP_CALL( SCIPaddBoolParam(scip,
748  	         "propagating/" PROP_NAME "/useimplics",
749  	         "should implications be used to strength the reduced cost for binary variables?",
750  	         &propdata->useimplics, FALSE, DEFAULT_USEIMPLICS, NULL, NULL) );
751  	   SCIP_CALL( SCIPaddBoolParam(scip,
752  	         "propagating/" PROP_NAME "/force",
753  	         "should the propagator be forced even if active pricer are present?",
754  	         &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) );
755  	
756  	   return SCIP_OKAY;
757  	}
758