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_qpkktref.h 26 * @ingroup PRESOLVERS 27 * @brief qpkktref presolver 28 * @author Tobias Fischer 29 * 30 * This presolver tries to add the KKT conditions as additional (redundant) constraints to the (mixed-binary) quadratic 31 * program 32 * \f[ 33 * \begin{array}{ll} 34 * \min & x^T Q x + c^T x + d \\ 35 * & A x \leq b, \\ 36 * & x \in \{0, 1\}^{p} \times R^{n-p}. 37 * \end{array} 38 * \f] 39 * 40 * We first check if the structure of the program is like (QP), see the documentation of the function 41 * checkConsQuadraticProblem(). 42 * 43 * If the problem is known to be bounded (all variables have finite lower and upper bounds), then we add the KKT 44 * conditions. For a continuous QPs the KKT conditions have the form 45 * \f[ 46 * \begin{array}{ll} 47 * Q x + c + A^T \mu = 0,\\ 48 * Ax \leq b,\\ 49 * \mu_i \cdot (Ax - b)_i = 0, & i \in \{1, \dots, m\},\\ 50 * \mu \geq 0. 51 * \end{array} 52 * \f] 53 * where \f$\mu\f$ are the Lagrangian variables. Each of the complementarity constraints \f$\mu_i \cdot (Ax - b)_i = 0\f$ 54 * is enforced via an SOS1 constraint for \f$\mu_i\f$ and an additional slack variable \f$s_i = (Ax - b)_i\f$. 55 * 56 * For mixed-binary QPs, the KKT-like conditions are 57 * \f[ 58 * \begin{array}{ll} 59 * Q x + c + A^T \mu + I_J \lambda = 0,\\ 60 * Ax \leq b,\\ 61 * x_j \in \{0,1\} & j \in J,\\ 62 * (1 - x_j) \cdot z_j = 0 & j \in J,\\ 63 * x_j \cdot (z_j - \lambda_j) = 0 & j \in J,\\ 64 * \mu_i \cdot (Ax - b)_i = 0 & i \in \{1, \dots, m\},\\ 65 * \mu \geq 0, 66 * \end{array} 67 * \f] 68 * where \f$J = \{1,\dots, p\}\f$, \f$\mu\f$ and \f$\lambda\f$ are the Lagrangian variables, and \f$I_J\f$ is the 69 * submatrix of the \f$n\times n\f$ identity matrix with columns indexed by \f$J\f$. For the derivation of the KKT-like 70 * conditions, see 71 * 72 * Branch-And-Cut for Complementarity and Cardinality Constrained Linear Programs,@n 73 * Tobias Fischer, PhD Thesis (2016) 74 * 75 * Algorithmically: 76 * 77 * - we handle the quadratic term variables of the quadratic constraint like in the method 78 * presolveAddKKTQuadQuadraticTerms() 79 * - we handle the bilinear term variables of the quadratic constraint like in the method presolveAddKKTQuadBilinearTerms() 80 * - we handle the linear term variables of the quadratic constraint like in the method presolveAddKKTQuadLinearTerms() 81 * - we handle linear constraints in the method presolveAddKKTLinearConss() 82 * - we handle aggregated variables in the method presolveAddKKTAggregatedVars() 83 * 84 * we have a hashmap from each variable to the index of the dual constraint in the KKT conditions. 85 */ 86 87 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 88 89 #ifndef __SCIP_PRESOL_QPKKTREF_H__ 90 #define __SCIP_PRESOL_QPKKTREF_H__ 91 92 #include "scip/def.h" 93 #include "scip/type_retcode.h" 94 #include "scip/type_scip.h" 95 96 #ifdef __cplusplus 97 extern "C" { 98 #endif 99 100 /** creates the QP KKT reformulation presolver and includes it in SCIP 101 * 102 * @ingroup PresolverIncludes 103 */ 104 SCIP_EXPORT 105 SCIP_RETCODE SCIPincludePresolQPKKTref( 106 SCIP* scip /**< SCIP data structure */ 107 ); 108 109 #ifdef __cplusplus 110 } 111 #endif 112 113 #endif 114