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_trustregion.h 26 * @ingroup PRIMALHEURISTICS 27 * @brief Large neighborhood search heuristic for Benders' decomposition based on trust region methods 28 * @author Stephen J. Maher 29 * 30 * The Trust Region heuristic draws upon trust region methods for solving optimization problems, especially in the 31 * context of Benders' decomposition. This heuristic has been developed to improve the heuristic performance of the 32 * Benders' decomposition algorithm within SCIP. 33 * 34 * The Trust Region heuristic copies the original SCIP instance and adds a constraint to penalize changes from the 35 * incumbent solution. Consider a problem that includes a set of binary variables \f$\mathcal{B}\f$. Given a feasible 36 * solution \f$\hat{x}\f$ to the original problem, we define the set \f$\mathcal{B}^{+}\f$ as the index set for the 37 * binary variables that are 1 in the input solution and \f$\mathcal{B}^{-}\f$ as the index set for binary variables 38 * that are 0. The trust region constraint, which is added to the sub-SCIP, is given by 39 * 40 * \f[ 41 * \sum_{i \in \mathcal{B}^{+}}(1 - x_{i}) + \sum_{i \in \mathcal{B}^{-}}x_{i} \le \theta 42 * \f] 43 * 44 * The variable \f$\theta\f$ measure the distance, in terms of the binary variables, of candidate solutions to the input 45 * solution. 46 * 47 * In addition, an upper bounding constraint is explicitly added to enforce a minimum improvement from the heuristic, 48 * given by \f$f(x) \le f(\hat{x}) - \epsilon\f$. The parameter \f$\epsilon \ge 0\f$ denotes the minimum improvement 49 * that must be achieved by the heuristic. 50 * 51 * The objective function is then modified to \f$f(x) + M\theta\f$, where \f$M\f$ is a parameter for penalizing the 52 * distance of solutions from the input solution \f$\hat{x}\f$. 53 * 54 * If a new incumbent solution is found by this heuristic, then the Trust Region heuristic is immediately 55 * re-executed with this new incumbent solution. 56 */ 57 58 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 59 60 #ifndef __SCIP_HEUR_TRUSTREGION_H__ 61 #define __SCIP_HEUR_TRUSTREGION_H__ 62 63 #include "scip/def.h" 64 #include "scip/type_retcode.h" 65 #include "scip/type_scip.h" 66 67 #ifdef __cplusplus 68 extern "C" { 69 #endif 70 71 /** creates local branching primal heuristic and includes it in SCIP 72 * 73 * @ingroup PrimalHeuristicIncludes 74 */ 75 SCIP_EXPORT 76 SCIP_RETCODE SCIPincludeHeurTrustregion( 77 SCIP* scip /**< SCIP data structure */ 78 ); 79 80 #ifdef __cplusplus 81 } 82 #endif 83 84 #endif 85