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/def.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"

Go to the source code of this file.

Functions
SCIP_EXPORT SCIP_RETCODE	SCIPincludeSepaEccuts (SCIP *scip)