Scippy

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 /* */
6 /* Copyright (C) 2002-2016 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 sepa_eccuts.h
17  * @ingroup SEPARATORS
18  * @brief edge concave cut separator
19  * @author Benjamin Müller
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[
28  * \min \, \sum_i \lambda_i f(v_i)
29  * \f]
30  * \f[
31  s.t. \; \sum_i \lambda_i v_i = x
32  * \f]
33  * \f[
34  * \sum_i \lambda_i = 1
35  * \f]
36  *
37  * where \f$ \{ v_i \} \f$ are the vertices of the domain \f$ [\ell,u] \f$. Let \f$ (\alpha, \alpha_0) \f$ be the dual
38  * 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$
39  * if \f$ x \f$ is in the interior of \f$ [\ell,u] \f$.
40  *
41  * We use this as follows: We transform the problem to the unit box \f$ [0,1]^n \f$ by using an linear affine
42  * transformation \f$ T(x) = Ax + b \f$ and perturb \f$ T(x) \f$ if it is not an interior point.
43  * This has the advantage that we do not have to update the matrix of the LP for different edge-concave functions.
44  *
45  * For a given quadratic constraint \f$ g(x) := x'Qx + b'x + c \le 0 \f$ we decompose \f$ g \f$ into several
46  * edge-concave aggregations and a remaining part, e.g.,
47  *
48  * \f[
49  * g(x) = \sum_{i = 1}^k f_i(x) + r(x)
50  * \f]
51  *
52  * where each \f$ f_i \f$ is edge-concave. To separate a given solution \f$ x \f$, we compute a facet of the convex
53  * envelope \f$ \tilde f \f$ for each edge-concave function \f$ f_i \f$ and an underestimator \f$ \tilde r \f$
54  * for \f$ r \f$. The resulting cut looks like:
55  *
56  * \f[
57  * \tilde f_i(x) + \tilde r(x) \le 0
58  * \f]
59  *
60  * We solve auxiliary MIP problems to identify good edge-concave aggregations. From the literature it is known that the
61  * convex envelope of an bilinear edge-concave function \f$ f_i \f$ differs from McCormick iff in the graph
62  * representation of \f$ f_i \f$ there exist a cycle with an odd number of positive weighted edges. We look for a
63  * subgraph of the graph representation of the quadratic function \f$ g(x) \f$ with the previous property using a model
64  * based on binary flow arc variables.
65  */
66 
67 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
68 
69 #ifndef __SCIP_SEPA_ECCUTS_H__
70 #define __SCIP_SEPA_ECCUTS_H__
71 
72 
73 #include "scip/scip.h"
74 
75 #ifdef __cplusplus
76 extern "C" {
77 #endif
78 
79 /** creates the edge-concave separator and includes it in SCIP */
80 extern
82  SCIP* scip /**< SCIP data structure */
83  );
84 
85 #ifdef __cplusplus
86 }
87 #endif
88 
89 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPincludeSepaEccuts(SCIP *scip)
Definition: sepa_eccuts.c:2790
SCIP callable library.