# SCIP

Solving Constraint Integer Programs

sepa_eccuts.h File Reference

## Detailed Description

edge concave cut separator

We call an edge-concave function on a polyhedron iff it is concave in all edge directions of . For the special case this is equivalent to being concave componentwise.

Since the convex envelope of an edge-concave function is a polytope, the value of the convex envelope for a can be obtained by solving the following LP:

where are the vertices of the domain . Let be the dual solution of this LP. It can be shown that is a facet of the convex envelope of if is in the interior of .

We use this as follows: We transform the problem to the unit box by using an linear affine transformation and perturb 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 we decompose into several edge-concave aggregations and a remaining part, e.g.,

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

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 differs from McCormick iff in the graph representation of 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 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