Scippy

SCIP

Solving Constraint Integer Programs

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 2002-2022 Zuse Institute Berlin */
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
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
114  SCIP* scip /**< SCIP data structure */
115  );
116 
117 #ifdef __cplusplus
118 }
119 #endif
120 
121 #endif
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for return codes for SCIP methods
type definitions for LP management
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPgenVBoundAdd(SCIP *scip, SCIP_PROP *genvboundprop, SCIP_VAR **vars, SCIP_VAR *var, SCIP_Real *coefs, int ncoefs, SCIP_Real coefprimalbound, SCIP_Real constant, SCIP_BOUNDTYPE boundtype)
type definitions for problem variables
type definitions for propagators
#define SCIP_Real
Definition: def.h:186
SCIP_RETCODE SCIPincludePropGenvbounds(SCIP *scip)
common defines and data types used in all packages of SCIP