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