1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file sepa_eccuts.h 26 * @ingroup SEPARATORS 27 * @brief edge concave cut separator 28 * @author Benjamin Mueller 29 * 30 * We call \f$ f \f$ an edge-concave function on a polyhedron \f$P\f$ iff it is concave in all edge directions of 31 * \f$P\f$. For the special case \f$ P = [\ell,u]\f$ this is equivalent to \f$f\f$ being concave componentwise. 32 * 33 * Since the convex envelope of an edge-concave function is a polytope, the value of the convex envelope for a 34 * \f$ x \in [\ell,u] \f$ can be obtained by solving the following LP: 35 * 36 * \f{align}{ 37 * \min \, & \sum_i \lambda_i f(v_i) \\ 38 * s.t. \, & \sum_i \lambda_i v_i = x \\ 39 * & \sum_i \lambda_i = 1 40 * \f} 41 * where \f$ \{ v_i \} \f$ are the vertices of the domain \f$ [\ell,u] \f$. Let \f$ (\alpha, \alpha_0) \f$ be the dual 42 * 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$ 43 * if \f$ x \f$ is in the interior of \f$ [\ell,u] \f$. 44 * 45 * We use this as follows: We transform the problem to the unit box \f$ [0,1]^n \f$ by using a linear affine 46 * transformation \f$ T(x) = Ax + b \f$ and perturb \f$ T(x) \f$ if it is not an interior point. 47 * This has the advantage that we do not have to update the matrix of the LP for different edge-concave functions. 48 * 49 * For a given quadratic constraint \f$ g(x) := x'Qx + b'x + c \le 0 \f$ we decompose \f$ g \f$ into several 50 * edge-concave aggregations and a remaining part, e.g., 51 * 52 * \f[ 53 * g(x) = \sum_{i = 1}^k f_i(x) + r(x) 54 * \f] 55 * 56 * where each \f$ f_i \f$ is edge-concave. To separate a given solution \f$ x \f$, we compute a facet of the convex 57 * envelope \f$ \tilde f \f$ for each edge-concave function \f$ f_i \f$ and an underestimator \f$ \tilde r \f$ 58 * for \f$ r \f$. The resulting cut looks like: 59 * 60 * \f[ 61 * \tilde f_i(x) + \tilde r(x) \le 0 62 * \f] 63 * 64 * We solve auxiliary MIP problems to identify good edge-concave aggregations. From the literature it is known that the 65 * convex envelope of a bilinear edge-concave function \f$ f_i \f$ differs from McCormick iff in the graph 66 * representation of \f$ f_i \f$ there exist a cycle with an odd number of positive weighted edges. We look for a 67 * subgraph of the graph representation of the quadratic function \f$ g(x) \f$ with the previous property using a model 68 * based on binary flow arc variables. 69 * 70 * This separator is currently disabled by default. It requires additional 71 * tuning to be enabled by default. However, it may be useful to enable 72 * it on instances with nonconvex quadratic constraints, in particular boxQPs. 73 */ 74 75 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 76 77 #ifndef __SCIP_SEPA_ECCUTS_H__ 78 #define __SCIP_SEPA_ECCUTS_H__ 79 80 81 #include "scip/def.h" 82 #include "scip/type_retcode.h" 83 #include "scip/type_scip.h" 84 85 #ifdef __cplusplus 86 extern "C" { 87 #endif 88 89 /** creates the edge-concave separator and includes it in SCIP 90 * 91 * @ingroup SeparatorIncludes 92 */ 93 SCIP_EXPORT 94 SCIP_RETCODE SCIPincludeSepaEccuts( 95 SCIP* scip /**< SCIP data structure */ 96 ); 97 98 #ifdef __cplusplus 99 } 100 #endif 101 102 #endif 103