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:
\begin{align} \min \, & \sum_i \lambda_i f(v_i) \\ s.t. \, & \sum_i \lambda_i v_i = x \\ & \sum_i \lambda_i = 1 \end{align}
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 a 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 a 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.
This separator is currently disabled by default. It requires additional tuning to be enabled by default. However, it may be useful to enable it on instances with nonconvex quadratic constraints, in particular boxQPs.
Definition in file sepa_eccuts.h.
Go to the source code of this file.
Functions | |
| SCIP_RETCODE | SCIPincludeSepaEccuts (SCIP *scip) |