 # SCIP

Solving Constraint Integer Programs

 Overview Files Plugin Types Interfaces Examples How To prop_genvbounds.h Go to the documentation of this file. 1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15  16 /**@file prop_genvbounds.h 17  * @ingroup PROPAGATORS 18  * @brief generalized variable bounds propagator 19  * @author Stefan Weltge 20  * @author Ambros Gleixner 21  * 22  * A generalized variable bound is a linear inequality of the form 23  * \f[ 24  * c \, x_i \geq \sum (a_j \, x_j) + d \cdot \mbox{primal\_bound} + \mbox{const}, 25  * \f] 26  * where \f$c\f$ is either 1 or -1 and \f$primal\_bound\f$ is an upper bound on the optimal objective 27  * value, which may improve during the solving process. In SCIP, generalized variable bounds are 28  * used for providing bounds on the LHS's variable \f$x_i\f$. If the above inequality is valid, the 29  * following bounds, depending on \f$x_i\f$'s coefficient, are also valid: 30  * \f[ 31  * c = 1 \qquad\Rightarrow\qquad x_i \geq \mbox{minactivity}(\sum a_j \, x_j) 32  * + d \cdot \mbox{primal\_bound} + \mbox{const} 33  * \f] 34  * \f[ 35  * c = -1 \qquad\Rightarrow\qquad x_i \leq - \mbox{minactivity}(\sum a_j \, x_j) 36  * - d \cdot \mbox{primal\_bound} - \mbox{const}. 37  * \f] 38  * 39  * Note that for feasible problems, \f$d \leq 0\f$ must hold. If \f$d < 0\f$ a decrease of the 40  * primal bound causes an improvement of the provided bound. Similarly, if \f$a_j > 0\f$ (\f$< 0\f$), a 41  * tightened lower (upper) bound of a variable \f$x_j\f$ also yields a better bound for \f$x_i\f$. 42  * 43  * The genvbounds propagator sorts its stored generalized variable bounds topologically in the 44  * following order: A generalized variable bound A (\f$c\, x_i \geq \ldots\f$) preceeds a 45  * generalized variable bound B if the left-hand side variable of A appears in the right-hand side 46  * of B with sign of its coefficient equal to c; i.e., if A is propagated and tightens the 47  * corresponding bound of x_i, then the minactivity on the right-hand side of B increases. We 48  * assume that this order is acyclic for the generalized variable bounds added. Under this 49  * condition, propagating the generalized variable bounds in a topological order ensures that all 50  * propagations are found in one round. 51  * 52  * Both global and local propagation is applied: If the primal bound improves, generalized variable bounds with a 53  * nonzero coefficient d are enforced in order to tighten global bounds using the global variable bounds for computing 54  * the minactivity. Independently, the genvbounds propagator catches events SCIP_EVENTTYPE_LBTIGHTENED and 55  * SCIP_EVENTTYPE_UBTIGHTENED, i.e., locally tightened bounds of variables that occur in the right-hand sides of 56  * generalized variable bounds, in order to perform an efficient local propagation when called. 57  */ 58  59 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 60  61 #ifndef __SCIP_PROP_GENVBOUNDS_H__ 62 #define __SCIP_PROP_GENVBOUNDS_H__ 63  64  65 #include "scip/scip.h" 66  67 #ifdef __cplusplus 68 extern "C" { 69 #endif 70  71 /** adds a generalized variable bound to the genvbounds propagator; if there is already a genvbound for the bound 72  * "boundtype" of variable "var", it will be replaced 73  */ 74 extern 76  SCIP* scip, /**< SCIP data structure */ 77  SCIP_PROP* genvboundprop, /**< genvbound propagator */ 78  SCIP_VAR** vars, /**< array of RHSs variables */ 79  SCIP_VAR* var, /**< LHSs variable */ 80  SCIP_Real* coefs, /**< array of coefficients for the RHSs variables */ 81  int ncoefs, /**< size of coefs array */ 82  SCIP_Real coefprimalbound, /**< nonpositive value of the primal bounds multiplier */ 83  SCIP_Real constant, /**< constant term */ 84  SCIP_BOUNDTYPE boundtype /**< type of bound provided by the genvbound */ 85  ); 86  87 /** creates the genvbounds propagator and includes it in SCIP */ 88 extern 90  SCIP* scip /**< SCIP data structure */ 91  ); 92  93 #ifdef __cplusplus 94 } 95 #endif 96  97 #endif 98  Generated on Wed Apr 2 2014 for SCIP Doxygen Documentation by doxygen (1.8.2) © 2020 by Zuse Institute Berlin (ZIB), Imprint designed with Bootstrap