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
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-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 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
*
81
* @ingroup SeparatorIncludes
82
*/
83
extern
84
SCIP_RETCODE
SCIPincludeSepaEccuts
(
85
SCIP
*
scip
/**< SCIP data structure */
86
);
87
88
#ifdef __cplusplus
89
}
90
#endif
91
92
#endif
Scip
Definition:
struct_scip.h:58
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition:
type_retcode.h:53
SCIPincludeSepaEccuts
SCIP_RETCODE SCIPincludeSepaEccuts(SCIP *scip)
Definition:
sepa_eccuts.c:2788
scip
Definition:
objbranchrule.h:33
scip.h
SCIP callable library.