Toggle navigation
SCIP Optimization Suite
SCIP
SoPlex
ZIMPL
UG
GCG
Documentation
SCIP 9.2.0
SCIP 8.1.0
SCIP 7.0.3
SCIP 6.0.2
SCIP 5.0.1
SCIP 4.0.1
SCIP 3.2.1
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 (C) 2002-2017 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
/**@addtogroup PROPAGATORS
72
*
73
* @{
74
*/
75
76
/** adds a generalized variable bound to the genvbounds propagator; if there is already a genvbound for the bound
77
* "boundtype" of variable "var", it will be replaced
78
*/
79
extern
80
SCIP_RETCODE
SCIPgenVBoundAdd
(
81
SCIP
*
scip
,
/**< SCIP data structure */
82
SCIP_PROP
* genvboundprop,
/**< genvbound propagator */
83
SCIP_VAR
** vars,
/**< array of RHSs variables */
84
SCIP_VAR
* var,
/**< LHSs variable */
85
SCIP_Real
* coefs,
/**< array of coefficients for the RHSs variables */
86
int
ncoefs,
/**< size of coefs array */
87
SCIP_Real
coefprimalbound,
/**< nonpositive value of the primal bounds multiplier */
88
SCIP_Real
constant,
/**< constant term */
89
SCIP_BOUNDTYPE
boundtype
/**< type of bound provided by the genvbound */
90
);
91
92
/* @} */
93
94
95
/** creates the genvbounds propagator and includes it in SCIP
96
*
97
* @ingroup PropagatorIncludes
98
*/
99
extern
100
SCIP_RETCODE
SCIPincludePropGenvbounds
(
101
SCIP
*
scip
/**< SCIP data structure */
102
);
103
104
#ifdef __cplusplus
105
}
106
#endif
107
108
#endif
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition:
type_lp.h:50
Scip
Definition:
struct_scip.h:58
SCIP_Var
Definition:
struct_var.h:197
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition:
type_retcode.h:53
SCIPgenVBoundAdd
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)
Definition:
prop_genvbounds.c:1999
SCIP_Prop
Definition:
struct_prop.h:37
SCIP_Real
#define SCIP_Real
Definition:
def.h:135
SCIPincludePropGenvbounds
SCIP_RETCODE SCIPincludePropGenvbounds(SCIP *scip)
Definition:
prop_genvbounds.c:2708
scip
Definition:
objbranchrule.h:33
scip.h
SCIP callable library.