All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
sepa_eccuts.h File Reference Detailed Descriptionedge concave cut separator We call an edgeconcave 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 edgeconcave 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 edgeconcave functions. For a given quadratic constraint we decompose into several edgeconcave aggregations and a remaining part, e.g.,
where each is edgeconcave. To separate a given solution , we compute a facet of the convex envelope for each edgeconcave function and an underestimator for . The resulting cut looks like:
We solve auxiliary MIP problems to identify good edgeconcave aggregations. From the literature it is known that the convex envelope of an bilinear edgeconcave 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.
Function Documentation
creates the edgeconcave separator and includes it in SCIP
