sepa_eccuts.h
Go to the documentation of this file.
21 * We call \f$ f \f$ an edge-concave function on a polyhedron \f$P\f$ iff it is concave in all edge directions of 22 * \f$P\f$. For the special case \f$ P = [\ell,u]\f$ this is equivalent to \f$f\f$ being concave componentwise. 24 * Since the convex envelope of an edge-concave function is a polytope, the value of the convex envelope for a 37 * where \f$ \{ v_i \} \f$ are the vertices of the domain \f$ [\ell,u] \f$. Let \f$ (\alpha, \alpha_0) \f$ be the dual 38 * solution of this LP. It can be shown that \f$ \alpha' x + \alpha_0 \f$ is a facet of the convex envelope of \f$ f \f$ 41 * We use this as follows: We transform the problem to the unit box \f$ [0,1]^n \f$ by using an linear affine 43 * This has the advantage that we do not have to update the matrix of the LP for different edge-concave functions. 45 * For a given quadratic constraint \f$ g(x) := x'Qx + b'x + c \le 0 \f$ we decompose \f$ g \f$ into several 52 * where each \f$ f_i \f$ is edge-concave. To separate a given solution \f$ x \f$, we compute a facet of the convex 53 * envelope \f$ \tilde f \f$ for each edge-concave function \f$ f_i \f$ and an underestimator \f$ \tilde r \f$ 60 * We solve auxiliary MIP problems to identify good edge-concave aggregations. From the literature it is known that the 61 * convex envelope of an bilinear edge-concave function \f$ f_i \f$ differs from McCormick iff in the graph 62 * representation of \f$ f_i \f$ there exist a cycle with an odd number of positive weighted edges. We look for a 63 * subgraph of the graph representation of the quadratic function \f$ g(x) \f$ with the previous property using a model 67 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
SCIP_RETCODE SCIPincludeSepaEccuts(SCIP *scip) Definition: objbranchrule.h:33 SCIP callable library. |