  # SCIP

Solving Constraint Integer Programs

sepa_eccuts.h File Reference

## Detailed Description

edge concave cut separator

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)