# SCIP

Solving Constraint Integer Programs

 sepa_eccuts.h Go to the documentation of this file. 1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2015 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15  16 /**@file sepa_eccuts.h 17  * @ingroup SEPARATORS 18  * @brief edge concave cut separator 19  * @author Benjamin MÃ¼ller 20  * 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. 23  * 24  * Since the convex envelope of an edge-concave function is a polytope, the value of the convex envelope for a 25  * \f$x \in [\ell,u] \f$ can be obtained by solving the following LP: 26  * 27  * \f[ 28  * \min \, \sum_i \lambda_i f(v_i) 29  * \f] 30  * \f[ 31  s.t. \; \sum_i \lambda_i v_i = x 32  * \f] 33  * \f[ 34  * \sum_i \lambda_i = 1 35  * \f] 36  * 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$ 39  * if \f$x \f$ is in the interior of \f$[\ell,u] \f$. 40  * 41  * We use this as follows: We transform the problem to the unit box \f$[0,1]^n \f$ by using an linear affine 42  * transformation \f$T(x) = Ax + b \f$ and perturb \f$T(x) \f$ if it is not an interior point. 43  * This has the advantage that we do not have to update the matrix of the LP for different edge-concave functions. 44  * 45  * For a given quadratic constraint \f$g(x) := x'Qx + b'x + c \le 0 \f$ we decompose \f$g \f$ into several 46  * edge-concave aggregations and a remaining part, e.g., 47  * 48  * \f[ 49  * g(x) = \sum_{i = 1}^k f_i(x) + r(x) 50  * \f] 51  * 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$ 54  * for \f$r \f$. The resulting cut looks like: 55  * 56  * \f[ 57  * \tilde f_i(x) + \tilde r(x) \le 0 58  * \f] 59  * 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 64  * based on binary flow arc variables. 65  */ 66  67 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 68  69 #ifndef __SCIP_SEPA_ECCUTS_H__ 70 #define __SCIP_SEPA_ECCUTS_H__ 71  72  73 #include "scip/scip.h" 74  75 #ifdef __cplusplus 76 extern "C" { 77 #endif 78  79 /** creates the edge-concave separator and includes it in SCIP */ 80 extern 82  SCIP* scip /**< SCIP data structure */ 83  ); 84  85 #ifdef __cplusplus 86 } 87 #endif 88  89 #endif SCIP_RETCODEenum SCIP_Retcode SCIP_RETCODEDefinition: type_retcode.h:53 SCIPincludeSepaEccutsSCIP_RETCODE SCIPincludeSepaEccuts(SCIP *scip) SCIPstruct Scip SCIPDefinition: type_scip.h:30 scip.hSCIP callable library. Generated on Wed Jul 22 2015 for SCIP Doxygen Documentation by doxygen (1.8.6) © 2024 by Zuse Institute Berlin (ZIB), Imprint designed with Bootstrap