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

SCIP_RETCODE SCIPincludeSepaEccuts ( SCIP * scip )

creates the edge-concave separator and includes it in SCIP

Parameters

scip	SCIP data structure

SCIP

Detailed Description

Functions

Function Documentation