# SCIP

Solving Constraint Integer Programs

sepa_eccuts.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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file sepa_eccuts.h
17  * @ingroup SEPARATORS
18  * @brief edge concave cut separator
19  * @author Benjamin Mueller
20  *
21  * We call \f$f \f$ an edge-concave function on a polyhedron \f$P\f$ iff it is concave in all edge directions of
22  * \f$P\f$. For the special case \f$P = [\ell,u]\f$ this is equivalent to \f$f\f$ being concave componentwise.
23  *
24  * Since the convex envelope of an edge-concave function is a polytope, the value of the convex envelope for a
25  * \f$x \in [\ell,u] \f$ can be obtained by solving the following LP:
26  *
27  * \f{align}{
28  * \min \, & \sum_i \lambda_i f(v_i) \\
29  * s.t. \, & \sum_i \lambda_i v_i = x \\
30  * & \sum_i \lambda_i = 1
31  * \f}
32  * where \f$\{ v_i \} \f$ are the vertices of the domain \f$[\ell,u] \f$. Let \f$(\alpha, \alpha_0) \f$ be the dual
33  * solution of this LP. It can be shown that \f$\alpha' x + \alpha_0 \f$ is a facet of the convex envelope of \f$f \f$
34  * if \f$x \f$ is in the interior of \f$[\ell,u] \f$.
35  *
36  * We use this as follows: We transform the problem to the unit box \f$[0,1]^n \f$ by using a linear affine
37  * transformation \f$T(x) = Ax + b \f$ and perturb \f$T(x) \f$ if it is not an interior point.
38  * This has the advantage that we do not have to update the matrix of the LP for different edge-concave functions.
39  *
40  * For a given quadratic constraint \f$g(x) := x'Qx + b'x + c \le 0 \f$ we decompose \f$g \f$ into several
41  * edge-concave aggregations and a remaining part, e.g.,
42  *
43  * \f[
44  * g(x) = \sum_{i = 1}^k f_i(x) + r(x)
45  * \f]
46  *
47  * where each \f$f_i \f$ is edge-concave. To separate a given solution \f$x \f$, we compute a facet of the convex
48  * envelope \f$\tilde f \f$ for each edge-concave function \f$f_i \f$ and an underestimator \f$\tilde r \f$
49  * for \f$r \f$. The resulting cut looks like:
50  *
51  * \f[
52  * \tilde f_i(x) + \tilde r(x) \le 0
53  * \f]
54  *
55  * We solve auxiliary MIP problems to identify good edge-concave aggregations. From the literature it is known that the
56  * convex envelope of a bilinear edge-concave function \f$f_i \f$ differs from McCormick iff in the graph
57  * representation of \f$f_i \f$ there exist a cycle with an odd number of positive weighted edges. We look for a
58  * subgraph of the graph representation of the quadratic function \f$g(x) \f$ with the previous property using a model
59  * based on binary flow arc variables.
60  *
61  * This separator is currently disabled by default. It requires additional
62  * tuning to be enabled by default. However, it may be useful to enable
63  * it on instances with nonconvex quadratic constraints, in particular boxQPs.
64  */
65
66 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
67
68 #ifndef __SCIP_SEPA_ECCUTS_H__
69 #define __SCIP_SEPA_ECCUTS_H__
70
71
72 #include "scip/def.h"
73 #include "scip/type_retcode.h"
74 #include "scip/type_scip.h"
75
76 #ifdef __cplusplus
77 extern "C" {
78 #endif
79
80 /** creates the edge-concave separator and includes it in SCIP
81  *
82  * @ingroup SeparatorIncludes
83  */
84 SCIP_EXPORT
86  SCIP* scip /**< SCIP data structure */
87  );
88
89 #ifdef __cplusplus
90 }
91 #endif
92
93 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPincludeSepaEccuts(SCIP *scip)
Definition: sepa_eccuts.c:3127
common defines and data types used in all packages of SCIP