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 heur_mpec.h 26 * @ingroup PRIMALHEURISTICS 27 * @brief mpec primal heuristic 28 * @author Felipe Serrano 29 * @author Benjamin Mueller 30 * 31 * This heuristic is based on the paper: 32 * @par 33 * Lars Schewe and Martin Schmidt@n 34 * [Computing Feasible Points for MINLPs with MPECs](http://www.optimization-online.org/DB_HTML/2016/12/5778.html) 35 * 36 * An MPEC is a mathematical program with complementarity constraint. 37 * For example, the constraint \f$x \in \{0, 1\}\f$ as \f$x (1-x) = 0\f$ 38 * can be modeled as complementarity constraint \f$x = 0\f$ or \f$x = 1\f$. 39 * 40 * This heuristic applies only to mixed binary nonlinear problems. 41 * The idea is to rewrite the MBNLP as MPEC and solve the MPEC instead (to a 42 * a local optimum) by replacing each integrality constraint by the 43 * complementarity constraint \f$x = 0\f$ or \f$x = 1\f$. 44 * In principle, this MPEC can be reformulated to a NLP by rewriting this 45 * constraint as equation \f$x (1-x) = 0\f$. 46 * However, solving this NLP reformulation with a generic NLP solver will 47 * often fail. One issue is that the reformulated complementarity constraints 48 * will not, in general, satisfy constraint qualifications (for instance, 49 * Slater's conditions, which requires the existence of a relative interior 50 * point, will not be satisfied). 51 * In order to increase the chances of solving the NLP reformulation of 52 * the MPEC by a NLP solver, the heuristic applies a regularization 53 * (proposed by Scholtes): it relaxes \f$x(1-x) = 0\f$ to 54 * \f$x(1-x) \leq \theta\f$. 55 * 56 * So the heuristic proceeds as follows. 57 * - Build the regularized NLP (rNLP) with a starting \f$\theta \in (0, \tfrac{1}{4}\f$. 58 * - Give the current LP solution as starting point to the NLP solver. 59 * - Solves rNLP and let \f$x^*\f$ be the best point found (if there is no point, abort). 60 * - If feasible, then reduce \f$\theta\f$ by a factor \f$\sigma\f$ and use 61 * its solution as the starting point for the next iteration. 62 * 63 * - If the rNLP is found infeasible, but the regularization constraints are feasible, abort. 64 * 65 * - If some variable violates the regularization constraint, i.e., 66 * \f$x^*_i(1-x^*_i) > \tau\f$ then solve the rNLP again using its starting solution 67 * modified by \f$x_i = 0\f$ if \f$x^*_i > 0.5\f$ and \f$x_i = 1\f$ if \f$x^*_i < 0.5\f$. 68 * One possible explanation for this choice is that, assuming \f$x^*_i > 0.5\f$, 69 * if really \f$x_i = 1\f$ were a solution, then the NLP solver should not have had troubles 70 * pushing \f$x_i\f$ towards 1, making at least the regularization constraint feasible. 71 * Instead, it might be that there is a solution with \f$x_i = 0\f$, but since \f$x^*_i > 0.5\f$ 72 * the NLP solver is having more problems pushing it to 0. 73 * 74 * - If the modification of the starting point did not help finding a feasible solution, 75 * solve the problem again, but now fixing the problematic variables using the same criteria. 76 * 77 * - If still we do not get a feasible solution, abort (note that the paper suggests to backtrack, 78 * but this might be just too expensive). 79 * 80 * - If the maximum binary infeasibility is small enough, call sub-NLP heuristic 81 * with binary variables fixed to the value suggested by \f$x^*\f$. 82 */ 83 84 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 85 86 #ifndef __SCIP_HEUR_MPEC_H__ 87 #define __SCIP_HEUR_MPEC_H__ 88 89 #include "scip/def.h" 90 #include "scip/type_retcode.h" 91 #include "scip/type_scip.h" 92 93 #ifdef __cplusplus 94 extern "C" { 95 #endif 96 97 /** creates the mpec primal heuristic and includes it in SCIP 98 * 99 * @ingroup PrimalHeuristicIncludes 100 */ 101 SCIP_EXPORT 102 SCIP_RETCODE SCIPincludeHeurMpec( 103 SCIP* scip /**< SCIP data structure */ 104 ); 105 106 #ifdef __cplusplus 107 } 108 #endif 109 110 #endif 111