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 presol_tworowbnd.h 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief do bound tightening by using two rows 28 * @author Dieter Weninger 29 * @author Patrick Gemander 30 * 31 * Perform bound tightening on two inequalities with some common variables. 32 * Two possible methods are being used. 33 * 34 * 1. LP-bound 35 * Let two constraints be given: 36 * \f{eqnarray*}{ 37 * A_{iR} x_R + A_{iS} x_S \geq b_i\\ 38 * A_{kR} x_R + A_{kT} x_T \geq b_k 39 * \f} 40 * with \f$N\f$ the set of variable indexes, \f$R \subseteq N\f$, \f$S \subseteq N\f$, \f$T \subseteq N\f$, 41 * \f$R \cap S = \emptyset\f$, \f$R \cap T = \emptyset\f$, \f$S \cap T = \emptyset\f$ and row indices \f$i \not= k\f$. 42 * 43 * Let \f$\ell\f$ and \f$u\f$ be bound vectors for x and solve the following two LPs 44 * \f{eqnarray*}{ 45 * L = \min \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \}\\ 46 * U = \max \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \} 47 * \f} 48 * and use \f$L\f$ and \f$U\f$ for getting bounds on \f$x_T\f$. 49 * 50 * If \f$L + \mbox{infimum}(A_{kT}x_T) \geq b_k\f$, then the second constraint above is redundant. 51 * 52 * 2. ConvComb with clique-extension 53 * Given two constraints 54 * \f{eqnarray*}{ 55 * A_{i\cdot} x \geq b_i \\ 56 * A_{k\cdot} x \geq b_k \\ 57 * \ell \leq x \leq u \\ 58 * \f} 59 * this method determines promising values for \f$\lambda \in (0,1)\f$ and 60 * applies feasibility-based bound tightening to the convex combinations 61 * 62 * \f$(\lambda A_{i\cdot} + (1 - \lambda) A_{k\cdot}) x \geq \lambda b_i + (1 - \lambda) b_k\f$. 63 * 64 * Additionally, cliques drawn from the SCIPcliqueTable are used 65 * to further strengthen the above bound tightening. Full details can be found in 66 * - Belotti P. "Bound reduction using pairs of linear inequalities" 67 * - Chen W. et. al "Two-row and two-column mixed-integer presolve using hashing-based pairing methods" 68 */ 69 70 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 71 72 #ifndef __SCIP_PRESOL_TWOROWBND_H__ 73 #define __SCIP_PRESOL_TWOROWBND_H__ 74 75 #include "scip/def.h" 76 #include "scip/type_retcode.h" 77 #include "scip/type_scip.h" 78 79 #ifdef __cplusplus 80 extern "C" { 81 #endif 82 83 /** creates the tworowbnd presolver and includes it in SCIP 84 * 85 * @ingroup PresolverIncludes 86 */ 87 SCIP_EXPORT 88 SCIP_RETCODE SCIPincludePresolTworowbnd( 89 SCIP* scip /**< SCIP data structure */ 90 ); 91 92 #ifdef __cplusplus 93 } 94 #endif 95 96 #endif 97