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_rootredcost.c
26   	 * @ingroup DEFPLUGINS_PROP
27   	 * @brief  reduced cost strengthening using root node reduced costs and the cutoff bound
28   	 * @author Tobias Achterberg
29   	 * @author Stefan Heinz
30   	 *
31   	 * This propagator uses the root reduced cost to (globally) propagate against the cutoff bound. The propagator checks if
32   	 * the variables with non-zero root reduced cost can exceed the cutoff bound. If this is the case the corresponding
33   	 * bound can be tightened.
34   	 *
35   	 * The propagate is performed during the search any time a new cutoff bound (primal solution) is found.
36   	 *
37   	 * @todo do not sort the variables; just store the cutoff bound which leads to a fixing. If that appears loop over all
38   	 *       variables and fix and store the next cutoff bound which leads to an fixing
39   	 * @todo resolve the root LP in case of repropagation and update root reduced costs use root LP counter to check if new
40   	 *       best root combinations might be available
41   	 */
42   	
43   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44   	
45   	#include "scip/prop_rootredcost.h"
46   	#include "scip/pub_message.h"
47   	#include "scip/pub_misc_sort.h"
48   	#include "scip/pub_prop.h"
49   	#include "scip/pub_var.h"
50   	#include "scip/scip_general.h"
51   	#include "scip/scip_lp.h"
52   	#include "scip/scip_mem.h"
53   	#include "scip/scip_message.h"
54   	#include "scip/scip_numerics.h"
55   	#include "scip/scip_param.h"
56   	#include "scip/scip_pricer.h"
57   	#include "scip/scip_prob.h"
58   	#include "scip/scip_probing.h"
59   	#include "scip/scip_prop.h"
60   	#include "scip/scip_solvingstats.h"
61   	#include "scip/scip_tree.h"
62   	#include "scip/scip_var.h"
63   	#include <string.h>
64   	
65   	/**@name Propagator properties
66   	 *
67   	 * @{
68   	 */
69   	
70   	#define PROP_NAME              "rootredcost"
71   	#define PROP_DESC              "reduced cost strengthening using root node reduced costs and the cutoff bound"
72   	#define PROP_TIMING             SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP
73   	#define PROP_PRIORITY         +10000000 /**< propagator priority */
74   	#define PROP_FREQ                     1 /**< propagator frequency */
75   	#define PROP_DELAY                FALSE /**< should propagation method be delayed, if other propagators found reductions? */
76   	
77   	/**@} */
78   	
79   	/**@name Default parameter values
80   	 *
81   	 * @{
82   	 */
83   	#define DEFAULT_ONLYBINARY        FALSE /**< should only binary variables be propagated? */
84   	#define DEFAULT_FORCE             FALSE /**< should the propagator be forced even if active pricer are present? Note that
85   	                                         *   the reductions are always valid, but installing an upper bound on priced
86   	                                         *   variables may lead to problems in pricing (existing variables at their upper
87   	                                         *   bound may be priced again since they may have negative reduced costs) */
88   	
89   	/**@} */
90   	
91   	
92   	/*
93   	 * Data structures
94   	 */
95   	
96   	/** propagator data */
97   	struct SCIP_PropData
98   	{
99   	   SCIP_VAR**            redcostvars;        /**< variables with non-zero root reduced cost */
100  	   SCIP_Real             lastcutoffbound;    /**< cutoff bound for which the root reduced costs were already processed */
101  	   int                   nredcostvars;       /**< number of variables with non-zero root reduced cost */
102  	   int                   nredcostbinvars;    /**< number of binary variables with non-zero root reduced cost */
103  	   int                   glbfirstnonfixed;   /**< index of first globally non-fixed binary variable */
104  	   SCIP_Bool             initialized;        /**< is the propagator data initialized */
105  	   SCIP_Bool             onlybinary;         /**< should only binary variables be propagated? */
106  	   SCIP_Bool             force;              /**< should the propagator be forced even if active pricer are present? */
107  	};
108  	
109  	
110  	/**@name Local methods
111  	 *
112  	 * @{
113  	 */
114  	
115  	/** reset structure memember of propagator data structure */
116  	static
117  	void propdataReset(
118  	   SCIP_PROPDATA*        propdata            /**< propagator data to reset */
119  	   )
120  	{
121  	   propdata->redcostvars = NULL;
122  	   propdata->lastcutoffbound = SCIP_INVALID;
123  	   propdata->nredcostvars = 0;
124  	   propdata->nredcostbinvars = 0;
125  	   propdata->glbfirstnonfixed = 0;
126  	   propdata->initialized = FALSE;
127  	}
128  	
129  	/** compare variables with non-zero reduced cost w.r.t.
130  	 *  (i)  the cutoff bound which would lead to a fixing
131  	 *  (ii) variable problem index;
132  	 */
133  	static
134  	SCIP_DECL_SORTPTRCOMP(varCompRedcost)
135  	{
136  	   SCIP_VAR* var1 = (SCIP_VAR*)elem1;
137  	   SCIP_VAR* var2 = (SCIP_VAR*)elem2;
138  	   SCIP_Real key1;
139  	   SCIP_Real key2;
140  	
141  	   assert(SCIPvarIsBinary(var1));
142  	   assert(SCIPvarGetBestRootRedcost(var1) != 0.0);
143  	
144  	   assert(SCIPvarIsBinary(var2));
145  	   assert(SCIPvarGetBestRootRedcost(var2) != 0.0);
146  	
147  	   /* collect sorting key for both variables */
148  	   key1 = REALABS(SCIPvarGetBestRootRedcost(var1)) + SCIPvarGetBestRootLPObjval(var1);
149  	   key2 = REALABS(SCIPvarGetBestRootRedcost(var2)) + SCIPvarGetBestRootLPObjval(var2);
150  	
151  	   if( key1 < key2 )
152  	      return -1;
153  	   else if( key1 > key2 )
154  	      return +1;
155  	
156  	   /* second criteria use the problem index
157  	    *
158  	    * @note The problem index is unique. That means the resulting sorting is unique.
159  	    */
160  	   return SCIPvarCompare(var1, var2);
161  	}
162  	
163  	/** create propagator data structure */
164  	static
165  	SCIP_RETCODE propdataCreate(
166  	   SCIP*                 scip,               /**< SCIP data structure */
167  	   SCIP_PROPDATA**       propdata            /**< pointer to store the created propagator data */
168  	   )
169  	{
170  	   SCIP_CALL( SCIPallocBlockMemory(scip, propdata) );
171  	
172  	   propdataReset(*propdata);
173  	
174  	   return SCIP_OKAY;
175  	}
176  	
177  	/** counts the number of variables with non-zero root reduced cost */
178  	static
179  	int countNonZeroRootRedcostVars(
180  	   SCIP*                 scip,               /**< SCIP data structure */
181  	   SCIP_VAR**            vars,               /**< variable array */
182  	   int                   nvars               /**< number of variables */
183  	   )
184  	{
185  	   int count;
186  	   int v;
187  	
188  	   count = 0;
189  	
190  	   /* count number of variables with non-zero root reduced cost */
191  	   for( v = 0; v < nvars; ++v )
192  	   {
193  	      SCIP_Real redcost;
194  	
195  	      assert(vars[v] != NULL);
196  	
197  	      redcost = SCIPvarGetBestRootRedcost(vars[v]);
198  	      if( !SCIPisDualfeasZero(scip, redcost) )
199  	         count++;
200  	   }
201  	
202  	   return count;
203  	}
204  	
205  	/** free propagator data */
206  	static
207  	SCIP_RETCODE propdataExit(
208  	   SCIP*                 scip,               /**< SCIP data structure */
209  	   SCIP_PROPDATA*        propdata            /**< propagator data */
210  	   )
211  	{
212  	   int v;
213  	
214  	   /* release all variables */
215  	   for( v = 0; v < propdata->nredcostvars; ++v )
216  	   {
217  	      SCIP_CALL( SCIPreleaseVar(scip, &propdata->redcostvars[v]) );
218  	   }
219  	
220  	   /* free memory for non-zero reduced cost variables */
221  	   SCIPfreeBlockMemoryArrayNull(scip, &propdata->redcostvars, propdata->nredcostvars);
222  	
223  	   propdataReset(propdata);
224  	
225  	   return SCIP_OKAY;
226  	}
227  	
228  	/** initializate the propagator */
229  	static
230  	SCIP_RETCODE propdataInit(
231  	   SCIP*                 scip,               /**< SCIP data structure */
232  	   SCIP_PROPDATA*        propdata            /**< propagator data */
233  	   )
234  	{
235  	   SCIP_VAR** vars;
236  	   int nvars;
237  	   int nbinvars;
238  	   int nredcostvars;
239  	   int nredcostbinvars;
240  	   int v;
241  	
242  	   assert(scip != NULL);
243  	   assert(propdata != NULL);
244  	
245  	   /* check if the propagator data structure is already initialized */
246  	   if( propdata->initialized )
247  	      return SCIP_OKAY;
248  	
249  	   /* get problem variables */
250  	   vars = SCIPgetVars(scip);
251  	   nvars = SCIPgetNVars(scip);
252  	   nbinvars = SCIPgetNBinVars(scip);
253  	
254  	   /* count binary variables with non-zero root reduced cost */
255  	   nredcostbinvars = countNonZeroRootRedcostVars(scip, vars, nbinvars);
256  	   SCIPdebugMsg(scip, "There are %d (poor) binary variables with non-zero root reduced cost <%s>.\n", nredcostbinvars, SCIPgetProbName(scip));
257  	
258  	   /* count non-binary variables with non-zero root reduced cost */
259  	   nredcostvars = countNonZeroRootRedcostVars(scip, &vars[nbinvars], nvars - nbinvars);
260  	
261  	   nredcostvars += nredcostbinvars;
262  	
263  	   /* collect the variables with non-zero reduced costs */
264  	   if( nredcostvars > 0 )
265  	   {
266  	      int k;
267  	
268  	      k = 0;
269  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->redcostvars, nredcostvars) );
270  	
271  	      SCIPdebugMsg(scip, "Store non-zero root reduced cost variables at address <%p>.\n", (void*)propdata->redcostvars);
272  	
273  	      for( v = 0; v < nvars; ++v )
274  	      {
275  	         SCIP_Real redcost;
276  	         SCIP_VAR* var;
277  	
278  	         var = vars[v];
279  	         redcost = SCIPvarGetBestRootRedcost(var);
280  	
281  	         if( SCIPisDualfeasZero(scip, redcost) )
282  	            continue;
283  	
284  	         assert(k < nredcostvars);
285  	
286  	         /* check if one of the non-binary variables is implicit binary */
287  	         if( k >= nredcostbinvars && SCIPvarIsBinary(var) )
288  	         {
289  	            /* move the first non-binary variable to end of the array */
290  	            propdata->redcostvars[k] = propdata->redcostvars[nredcostbinvars];
291  	
292  	            /* place the binary variable at the end of the binary section */
293  	            propdata->redcostvars[nredcostbinvars] = var;
294  	            nredcostbinvars++;
295  	         }
296  	         else
297  	            propdata->redcostvars[k] = var;
298  	
299  	         /* captures the variable */
300  	         SCIP_CALL( SCIPcaptureVar(scip, var) ) ;
301  	
302  	         k++;
303  	
304  	         /* check if already visited all variable with non-zero redcostective coefficient */
305  	         if( k == nredcostvars )
306  	            break;
307  	      }
308  	
309  	      /* sort binary variables with respect to their cutoff bound which would lead to an fixing; this order can be used
310  	       * to efficiently propagate the binary variables
311  	       */
312  	      SCIPsortDownPtr((void**)propdata->redcostvars, varCompRedcost, nredcostbinvars);
313  	
314  	      assert(k == nredcostvars);
315  	
316  	      SCIPdebugMsg(scip, "variables with non-zero redcostective coefficient: %d binaries, %d non-binaries\n", nredcostbinvars, nredcostvars - nredcostbinvars);
317  	   }
318  	
319  	   propdata->nredcostvars = nredcostvars;
320  	   propdata->nredcostbinvars = nredcostbinvars;
321  	   propdata->glbfirstnonfixed = 0;
322  	   propdata->lastcutoffbound = SCIPinfinity(scip);
323  	   propdata->initialized = TRUE;
324  	
325  	   return SCIP_OKAY;
326  	}
327  	
328  	/** propagates the root reduced cost against the cutoff bound for the given variable */
329  	static
330  	SCIP_RETCODE propagateRootRedcostVar(
331  	   SCIP*                 scip,               /**< SCIP data structure */
332  	   SCIP_VAR*             var,                /**< variable to propagate */
333  	   SCIP_Real             cutoffbound,        /**< cutoff bound to use */
334  	   SCIP_Bool*            infeasible,         /**< pointer to store whether the new domain is empty */
335  	   SCIP_Bool*            tightened           /**< pointer to store if the bound was tightened */
336  	   )
337  	{
338  	   SCIP_Real rootsol;
339  	   SCIP_Real rootredcost;
340  	   SCIP_Real rootlpobjval;
341  	   SCIP_Real newbd;
342  	
343  	   rootredcost = SCIPvarGetBestRootRedcost(var);
344  	   assert(rootredcost != SCIP_INVALID); /*lint !e777*/
345  	
346  	   /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
347  	    * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
348  	    * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
349  	    * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
350  	    */
351  	   assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasZero(scip, rootredcost));
352  	
353  	   rootsol = SCIPvarGetBestRootSol(var);
354  	   rootlpobjval = SCIPvarGetBestRootLPObjval(var);
355  	
356  	   /* calculate reduced cost based bound */
357  	   newbd = rootsol + (cutoffbound - rootlpobjval) / rootredcost;
358  	
359  	   if( SCIPisDualfeasPositive(scip, rootredcost) )
360  	   {
361  	      assert(SCIPisFeasLE(scip, rootsol, SCIPvarGetLbGlobal(var))); /* lb might have been increased in the meantime */
362  	
363  	      /* strengthen upper bound */
364  	      SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
365  	   }
366  	   else
367  	   {
368  	      assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasNegative(scip, rootredcost));
369  	      assert(SCIPisFeasGE(scip, rootsol, SCIPvarGetUbGlobal(var))); /* ub might have been decreased in the meantime */
370  	
371  	      /* strengthen lower bound */
372  	      SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
373  	   }
374  	
375  	   return SCIP_OKAY;
376  	}
377  	
378  	/** propagate binary variables with non-zero root reduced cost */
379  	static
380  	SCIP_RETCODE propagateBinaryBestRootRedcost(
381  	   SCIP*                 scip,               /**< SCIP data structure */
382  	   SCIP_PROPDATA*        propdata,           /**< propagator data structure */
383  	   SCIP_Real             cutoffbound,        /**< cutoff bound to use */
384  	   int*                  nchgbds,            /**< pointer to store the number of bound changes */
385  	   SCIP_Bool*            cutoff              /**< pointer to store if a cutoff was detected */
386  	   )
387  	{
388  	   SCIP_VAR** redcostvars;
389  	   int v;
390  	
391  	   assert(!(*cutoff));
392  	
393  	   /* the binary variables are stored in the beginning of the variable array; these variables are sorted w.r.t. cutoff
394  	    * bound which would lead to a fixing; that give us an abort criteria (see below)
395  	    */
396  	   redcostvars = propdata->redcostvars;
397  	   assert(redcostvars != NULL);
398  	
399  	#ifndef NDEBUG
400  	   /* check that the binary variables are correctly sorted
401  	    *
402  	    * @note In case the assertion fails it indicates that a new LP root solving arose after we initialized the
403  	    *       propagator; The new LP solution destroyed the sorting of the binary variables since the reduced cost of the
404  	    *       variables changed. This could lead to potentially missing a domain reductions. Currently, it is not possible to
405  	    *       check if a new root LP was solved, changing the root reduced costs. This case, however, should not happen in the
406  	    *       current SCIP version.
407  	    */
408  	   for( v = 1; v < propdata->nredcostbinvars; ++v )
409  	      assert(varCompRedcost(redcostvars[v-1], redcostvars[v]) == 1);
410  	
411  	   /* check that the variables before glbfirstnonfixed are globally fixed */
412  	   for( v = 0; v < propdata->glbfirstnonfixed; ++v )
413  	   {
414  	      SCIP_VAR* var;
415  	
416  	      var =  redcostvars[v];
417  	      assert(var != NULL);
418  	
419  	      assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5);
420  	   }
421  	#endif
422  	
423  	   /* propagate binary variables */
424  	   for( v = propdata->glbfirstnonfixed; v < propdata->nredcostbinvars; ++v )
425  	   {
426  	      SCIP_VAR* var;
427  	      SCIP_Bool tightened;
428  	
429  	      var =  redcostvars[v];
430  	      assert(var != NULL);
431  	
432  	      /* check if the variables is already globally fixed; if so continue with the next potential candidate */
433  	      if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
434  	         continue;
435  	
436  	      /* try to tighten the variable bound */
437  	      SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, cutoff, &tightened) );
438  	
439  	      if( tightened )
440  	      {
441  	         /* @note The variable might not be globally fixed right away since this would destroy the local internal data
442  	          *       structure of a search node; the bound change is in that case pending; hence we cannot assert that the
443  	          *       variable is globally fixed
444  	          */
445  	         assert(!(*cutoff));
446  	
447  	         SCIPdebugMsg(scip, "globally fixed binary variable <%s> [%g,%g] bestroot sol <%g>, redcost <%g>, lpobj <%g>\n",
448  	            SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var),
449  	            SCIPvarGetBestRootSol(var), SCIPvarGetBestRootRedcost(var), SCIPvarGetBestRootLPObjval(var) );
450  	
451  	         (*nchgbds)++;
452  	      }
453  	      else
454  	      {
455  	         assert(!tightened);
456  	
457  	         /* The binary variables are sorted in non-increasing manner w.r.t. their cutoff bound which would lead to a
458  	          * global fixing; That is, abs(rootredcost) + rootlpobjval. Depending on the sign of the reduced cost the
459  	          * following two cases can arise for binary variables which are not fixed globally yet:
460  	          *
461  	          * - redcost > 0 --> newub = 0.0 + (cutoffbound - lpobjval) / redcost --> newub = 0 <=> cutoffbound < redcost + lpobjval = sorting key
462  	          * - redcost < 0 --> newlb = 1.0 + (cutoffbound - lpobjval) / redcost --> newlb = 1 <=> cutoffbound < -redcost + lpobjval = sorting key
463  	          *
464  	          * Due to the order of the binary variables it follows if one binary variable cannot be fixed anymore all the
465  	          * remaining once can also not be fixed since these have only an smaller or equal cutoff bound which would lead
466  	          * to global fixing. Hence, we can break that loop.
467  	          *
468  	          * Note that variables with non-zero reduced cost are sitting at one of their bound. That is the lower one if
469  	          * the reduced cost are positive and the upper bound if the reduced cost are negative. For binary variables
470  	          * that is 0 for the lower bound and 1 for the upper bound.
471  	          */
472  	         SCIPdebugMsg(scip, "interrupt propagation for binary variables after %d from %d binary variables\n",
473  	            v, propdata->nredcostbinvars);
474  	
475  	         if( *cutoff )
476  	         {
477  	            SCIPdebugMsg(scip, "detected cutoff: binary variable <%s> [%g,%g], redcost <%g>, rootsol <%g>, rootlpobjval <%g>\n",
478  	               SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var),
479  	               SCIPvarGetBestRootRedcost(var), SCIPvarGetBestRootSol(var), SCIPvarGetBestRootLPObjval(var));
480  	         }
481  	
482  	         break;
483  	      }
484  	   }
485  	   /* store the index of the variable which is not globally fixed */
486  	   propdata->glbfirstnonfixed = v;
487  	
488  	#if 0 /* due to numerics it might be that the abort criteria did not work correctly, because the sorting mechanism may
489  	       * have evaluated variables with a really small difference in their reduced cost values but with really huge
490  	       * lpobjval as the same
491  	       */
492  	#ifndef NDEBUG
493  	   /* check that the abort criteria works; that means none of the remaining binary variables can be fixed */
494  	   for( ; v < propdata->nredcostbinvars && !(*cutoff); ++v )
495  	   {
496  	      SCIP_VAR* var;
497  	      SCIP_Bool tightened;
498  	
499  	      var =  redcostvars[v];
500  	      assert(var != NULL);
501  	
502  	      /* check if the variables is already globally fixed; if so continue with the potential candidate */
503  	      if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
504  	         continue;
505  	
506  	      /* try to tighten the variable bound */
507  	      SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, cutoff, &tightened) );
508  	      assert(!tightened);
509  	      assert(!(*cutoff));
510  	   }
511  	#endif
512  	#endif
513  	
514  	   return SCIP_OKAY;
515  	}
516  	
517  	/**@} */
518  	
519  	
520  	/**@name Callback methods of propagator
521  	 *
522  	 * @{
523  	 */
524  	
525  	/** copy method for propagator plugins (called when SCIP copies plugins) */
526  	static
527  	SCIP_DECL_PROPCOPY(propCopyRootredcost)
528  	{  /*lint --e{715}*/
529  	   assert(scip != NULL);
530  	   assert(prop != NULL);
531  	   assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
532  	
533  	   /* call inclusion method of propagator */
534  	   SCIP_CALL( SCIPincludePropRootredcost(scip) );
535  	
536  	   return SCIP_OKAY;
537  	}
538  	
539  	/** destructor of propagator to free user data (called when SCIP is exiting) */
540  	static
541  	SCIP_DECL_PROPFREE(propFreeRootredcost)
542  	{  /*lint --e{715}*/
543  	   SCIP_PROPDATA* propdata;
544  	
545  	   /* free propagator data */
546  	   propdata = SCIPpropGetData(prop);
547  	   assert(propdata != NULL);
548  	   assert(propdata->redcostvars == NULL);
549  	
550  	   SCIPfreeBlockMemory(scip, &propdata);
551  	   SCIPpropSetData(prop, NULL);
552  	
553  	   return SCIP_OKAY;
554  	}
555  	
556  	/** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
557  	static
558  	SCIP_DECL_PROPEXITSOL(propExitsolRootredcost)
559  	{  /*lint --e{715}*/
560  	   SCIP_PROPDATA* propdata;
561  	
562  	   propdata = SCIPpropGetData(prop);
563  	   assert(propdata != NULL);
564  	
565  	   /* reset propagator data structure */
566  	   SCIP_CALL( propdataExit(scip, propdata) );
567  	
568  	   return SCIP_OKAY;
569  	}
570  	
571  	/** execution method of propagator */
572  	static
573  	SCIP_DECL_PROPEXEC(propExecRootredcost)
574  	{  /*lint --e{715}*/
575  	   SCIP_PROPDATA* propdata;
576  	   SCIP_VAR** redcostvars;
577  	   SCIP_Real cutoffbound;
578  	   SCIP_Real lpobjval;
579  	   SCIP_Bool cutoff;
580  	   int nredcostvars;
581  	   int nchgbds;
582  	   int v;
583  	
584  	   *result = SCIP_DIDNOTRUN;
585  	
586  	   /* in case we have a zero objective fucntion, we skip the root reduced cost propagator */
587  	   if( SCIPgetNObjVars(scip) == 0 )
588  	      return SCIP_OKAY;
589  	
590  	   /* propagator can only be applied during solving stage */
591  	   if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING )
592  	      return SCIP_OKAY;
593  	
594  	   /* the propagator should run in all nodes except the root node; for the root node the redcost propagator does
595  	    * the job already
596  	    */
597  	   if( SCIPgetDepth(scip) < 1 )
598  	      return SCIP_OKAY;
599  	
600  	   /* first check root LP objective value if it exists */
601  	   lpobjval = SCIPgetLPRootObjval(scip);
602  	   if( lpobjval == SCIP_INVALID ) /*lint !e777*/
603  	      return SCIP_OKAY;
604  	
605  	   /* do not run in probing mode since this propagator changes global variable bounds */
606  	   if( SCIPinProbing(scip) )
607  	      return SCIP_OKAY;
608  	
609  	   /* do not run if propagation w.r.t. objective is not allowed */
610  	   if( !SCIPallowWeakDualReds(scip) )
611  	      return SCIP_OKAY;
612  	
613  	   /* get propagator data */
614  	   propdata = SCIPpropGetData(prop);
615  	   assert(propdata != NULL);
616  	
617  	   /* do nothing if active pricer are present and force flag is not TRUE */
618  	   if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
619  	      return SCIP_OKAY;
620  	
621  	   /* get current cutoff bound */
622  	   cutoffbound = SCIPgetCutoffbound(scip);
623  	
624  	   /* reduced cost strengthening can only be applied, if we have a finite upper bound on the LP value */
625  	   if( SCIPisInfinity(scip, cutoffbound) )
626  	      return SCIP_OKAY;
627  	
628  	   /* initialize propagator data structure */
629  	   SCIP_CALL( propdataInit(scip, propdata) );
630  	   assert(cutoffbound <= propdata->lastcutoffbound);
631  	
632  	   if( cutoffbound == propdata->lastcutoffbound ) /*lint !e777*/
633  	      return SCIP_OKAY;
634  	
635  	   /* get variables */
636  	   redcostvars = propdata->redcostvars;
637  	   nredcostvars = propdata->nredcostvars;
638  	
639  	   /* since no variables has non-zero reduced cost do nothing */
640  	   if( nredcostvars == 0 )
641  	      return SCIP_OKAY;
642  	
643  	   /* store cutoff bound to remember later that for that particular cutoff bound the propagation was already
644  	    * preformed
645  	    */
646  	   propdata->lastcutoffbound = cutoffbound;
647  	
648  	   SCIPdebugMsg(scip, "searching for root reduced cost fixings\n");
649  	   SCIPdebugMsg(scip, "-> cutoffbound <%g>\n", cutoffbound);
650  	   SCIPdebugMsg(scip, "-> LP objective value <%g>\n", lpobjval);
651  	
652  	   *result = SCIP_DIDNOTFIND;
653  	   nchgbds = 0;
654  	   cutoff = FALSE;
655  	
656  	   /* propagate the binary variables with non-zero root reduced cost */
657  	   SCIP_CALL( propagateBinaryBestRootRedcost(scip, propdata, cutoffbound, &nchgbds, &cutoff) );
658  	
659  	   if( !propdata->onlybinary )
660  	   {
661  	      /* check reduced costs for non-binary variables that were columns of the root LP */
662  	      for( v = propdata->nredcostbinvars; v < nredcostvars && !cutoff; ++v )
663  	      {
664  	         SCIP_VAR* var;
665  	         SCIP_Bool tightened;
666  	
667  	         var = redcostvars[v];
668  	         assert(var != NULL);
669  	
670  	         /* try to tighten the variable bound */
671  	         SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, &cutoff, &tightened) );
672  	
673  	         if( tightened )
674  	            nchgbds++;
675  	      }
676  	   }
677  	
678  	   /* evaluate propagation results */
679  	   if( cutoff )
680  	   {
681  	      /* we are done with solving since the cutoff is w.r.t. a global bound change; cutoff root node */
682  	      SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
683  	      (*result) = SCIP_CUTOFF;
684  	   }
685  	   else if( nchgbds > 0 )
686  	      (*result) = SCIP_REDUCEDDOM;
687  	
688  	   SCIPdebugMsg(scip, "tightened %d variable domains (%u cutoff)\n", nchgbds, cutoff);
689  	
690  	   return SCIP_OKAY;
691  	}
692  	
693  	/**@} */
694  	
695  	
696  	/** creates the root node reduced cost strengthening propagator and includes it in SCIP */
697  	SCIP_RETCODE SCIPincludePropRootredcost(
698  	   SCIP*                 scip                /**< SCIP data structure */
699  	   )
700  	{
701  	   SCIP_PROPDATA* propdata;
702  	   SCIP_PROP* prop;
703  	
704  	   /* create rootredcost propagator data */
705  	   SCIP_CALL( propdataCreate(scip, &propdata) );
706  	
707  	   /* include propagator */
708  	   SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
709  	         propExecRootredcost, propdata) );
710  	
711  	   assert(prop != NULL);
712  	
713  	   /* set optional callbacks via setter functions */
714  	   SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyRootredcost) );
715  	   SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeRootredcost) );
716  	   SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolRootredcost) );
717  	
718  	   SCIP_CALL( SCIPaddBoolParam(scip,
719  	         "propagating/" PROP_NAME "/onlybinary",
720  	         "should only binary variables be propagated?",
721  	         &propdata->onlybinary, TRUE, DEFAULT_ONLYBINARY, NULL, NULL) );
722  	   SCIP_CALL( SCIPaddBoolParam(scip,
723  	         "propagating/" PROP_NAME "/force",
724  	         "should the propagator be forced even if active pricer are present?",
725  	         &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) );
726  	
727  	   return SCIP_OKAY;
728  	}
729