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_genvbounds.h
26   	 * @ingroup PROPAGATORS
27   	 * @brief   generalized variable bounds propagator
28   	 * @author  Stefan Weltge
29   	 * @author  Ambros Gleixner
30   	 *
31   	 *  A generalized variable bound is a linear inequality of the form
32   	 *  \f[
33   	 *     c \, x_i \geq \sum (a_j \, x_j) + d \cdot \mbox{primal\_bound} + \mbox{const},
34   	 *  \f]
35   	 *  where \f$c\f$ is either 1 or -1 and \f$primal\_bound\f$ is an upper bound on the optimal objective
36   	 *  value, which may improve during the solving process. In SCIP, generalized variable bounds are
37   	 *  used for providing bounds on the LHS's variable \f$x_i\f$. If the above inequality is valid, the
38   	 *  following bounds, depending on \f$x_i\f$'s coefficient, are also valid:
39   	 *  \f[
40   	 *     c = 1   \qquad\Rightarrow\qquad   x_i \geq  \mbox{minactivity}(\sum a_j \, x_j)
41   	 *                                       + d \cdot \mbox{primal\_bound} + \mbox{const}
42   	 *  \f]
43   	 *  \f[
44   	 *     c = -1  \qquad\Rightarrow\qquad   x_i \leq - \mbox{minactivity}(\sum a_j \, x_j)
45   	 *                                       - d \cdot \mbox{primal\_bound} - \mbox{const}.
46   	 *  \f]
47   	 *
48   	 *  Note that for feasible problems, \f$d \leq 0\f$ must hold. If \f$d < 0\f$ a decrease of the
49   	 *  primal bound causes an improvement of the provided bound. Similarly, if \f$a_j > 0\f$ (\f$< 0\f$), a
50   	 *  tightened lower (upper) bound of a variable \f$x_j\f$ also yields a better bound for \f$x_i\f$.
51   	 *
52   	 *  The genvbounds propagator sorts its stored generalized variable bounds topologically in the
53   	 *  following order: A generalized variable bound A (\f$c\, x_i \geq \ldots\f$) preceeds a
54   	 *  generalized variable bound B if the left-hand side variable of A appears in the right-hand side
55   	 *  of B with sign of its coefficient equal to c; i.e., if A is propagated and tightens the
56   	 *  corresponding bound of x_i, then the minactivity on the right-hand side of B increases. We
57   	 *  assume that this order is acyclic for the generalized variable bounds added. Under this
58   	 *  condition, propagating the generalized variable bounds in a topological order ensures that all
59   	 *  propagations are found in one round.
60   	 *
61   	 *  Both global and local propagation is applied: If the primal bound improves, generalized variable bounds with a
62   	 *  nonzero coefficient d are enforced in order to tighten global bounds using the global variable bounds for computing
63   	 *  the minactivity. Independently, the genvbounds propagator catches events SCIP_EVENTTYPE_LBTIGHTENED and
64   	 *  SCIP_EVENTTYPE_UBTIGHTENED, i.e., locally tightened bounds of variables that occur in the right-hand sides of
65   	 *  generalized variable bounds, in order to perform an efficient local propagation when called.
66   	 */
67   	
68   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
69   	
70   	#ifndef __SCIP_PROP_GENVBOUNDS_H__
71   	#define __SCIP_PROP_GENVBOUNDS_H__
72   	
73   	#include "scip/def.h"
74   	#include "scip/type_lp.h"
75   	#include "scip/type_prop.h"
76   	#include "scip/type_retcode.h"
77   	#include "scip/type_scip.h"
78   	#include "scip/type_var.h"
79   	
80   	#ifdef __cplusplus
81   	extern "C" {
82   	#endif
83   	
84   	/**@addtogroup PROPAGATORS
85   	  *
86   	  * @{
87   	  */
88   	
89   	/** adds a generalized variable bound to the genvbounds propagator; if there is already a genvbound for the bound
90   	 *  "boundtype" of variable "var", it will be replaced
91   	 */
92   	SCIP_EXPORT
93   	SCIP_RETCODE SCIPgenVBoundAdd(
94   	   SCIP*                 scip,               /**< SCIP data structure */
95   	   SCIP_PROP*            genvboundprop,      /**< genvbound propagator */
96   	   SCIP_VAR**            vars,               /**< array of RHSs variables */
97   	   SCIP_VAR*             var,                /**< LHSs variable */
98   	   SCIP_Real*            coefs,              /**< array of coefficients for the RHSs variables */
99   	   int                   ncoefs,             /**< size of coefs array */
100  	   SCIP_Real             coefprimalbound,    /**< nonpositive value of the primal bounds multiplier */
101  	   SCIP_Real             constant,           /**< constant term */
102  	   SCIP_BOUNDTYPE        boundtype           /**< type of bound provided by the genvbound */
103  	   );
104  	
105  	/** @} */
106  	
107  	
108  	/** creates the genvbounds propagator and includes it in SCIP
109  	 *
110  	 * @ingroup PropagatorIncludes
111  	 */
112  	SCIP_EXPORT
113  	SCIP_RETCODE SCIPincludePropGenvbounds(
114  	   SCIP*                 scip                /**< SCIP data structure */
115  	   );
116  	
117  	#ifdef __cplusplus
118  	}
119  	#endif
120  	
121  	#endif
122