Scippy

SCIP

Solving Constraint Integer Programs

sepa_eccuts.h File Reference

Detailed Description

edge concave cut separator

Author
Benjamin Müller

We call $ f $ an edge-concave function on a polyhedron $P$ iff it is concave in all edge directions of $P$. For the special case $ P = [\ell,u]$ this is equivalent to $f$ being concave componentwise.

Since the convex envelope of an edge-concave function is a polytope, the value of the convex envelope for a $ x \in [\ell,u] $ can be obtained by solving the following LP:

\[ \min \, \sum_i \lambda_i f(v_i) \]

\[ s.t. \; \sum_i \lambda_i v_i = x \]

\[ \sum_i \lambda_i = 1 \]

where $ \{ v_i \} $ are the vertices of the domain $ [\ell,u] $. Let $ (\alpha, \alpha_0) $ be the dual solution of this LP. It can be shown that $ \alpha' x + \alpha_0 $ is a facet of the convex envelope of $ f $ if $ x $ is in the interior of $ [\ell,u] $.

We use this as follows: We transform the problem to the unit box $ [0,1]^n $ by using an linear affine transformation $ T(x) = Ax + b $ and perturb $ T(x) $ if it is not an interior point. This has the advantage that we do not have to update the matrix of the LP for different edge-concave functions.

For a given quadratic constraint $ g(x) := x'Qx + b'x + c \le 0 $ we decompose $ g $ into several edge-concave aggregations and a remaining part, e.g.,

\[ g(x) = \sum_{i = 1}^k f_i(x) + r(x) \]

where each $ f_i $ is edge-concave. To separate a given solution $ x $, we compute a facet of the convex envelope $ \tilde f $ for each edge-concave function $ f_i $ and an underestimator $ \tilde r $ for $ r $. The resulting cut looks like:

\[ \tilde f_i(x) + \tilde r(x) \le 0 \]

We solve auxiliary MIP problems to identify good edge-concave aggregations. From the literature it is known that the convex envelope of an bilinear edge-concave function $ f_i $ differs from McCormick iff in the graph representation of $ f_i $ there exist a cycle with an odd number of positive weighted edges. We look for a subgraph of the graph representation of the quadratic function $ g(x) $ with the previous property using a model based on binary flow arc variables.

Definition in file sepa_eccuts.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPincludeSepaEccuts (SCIP *scip)
 

Function Documentation