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