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 benderscut_opt.h 26 * @ingroup BENDERSCUTS 27 * @brief Generates a standard Benders' decomposition optimality cut 28 * @author Stephen J. Maher 29 * 30 * The classical Benders' decomposition optimality cuts arise from a feasible instance of the Benders' decomposition 31 * subproblem. The optimality cuts are an underestimator of the subproblem objective function value. Auxiliary 32 * variables, \f$\varphi\f$ are added to the master problem as a lower bound on the subproblem objective function value. 33 * 34 * Consider a linear Benders' decomposition subproblem that takes the master problem solution \f$\bar{x}\f$ as input: 35 * \f[ 36 * z(\bar{x}) = \min\{d^{T}y : Ty \geq h - H\bar{x}, y \geq 0\} 37 * \f] 38 * If the subproblem is feasible, and \f$z(\bar{x}) > \varphi\f$ (indicating that the current underestimators are not 39 * optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the 40 * subproblem. Let \f$w\f$ be the vector corresponding to the optimal dual solution of the Benders' decomposition 41 * subproblem. The resulting cut is: 42 * \f[ 43 * \varphi \geq w^{T}(h - Hx) 44 * \f] 45 * 46 * Next, consider a nonlinear Benders' decomposition subproblem that takes the master problem solution \f$\bar{x}\f$ as input: 47 * \f[ 48 * z(\bar{x}) = \min\{d^{T}y : g(\bar{x},y) \leq 0, y \geq 0\} 49 * \f] 50 * If the subproblem is feasible, and \f$z(\bar{x}) > \varphi\f$ (indicating that the current underestimators are not 51 * optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the 52 * subproblem. Let \f$w\f$ be the vector corresponding to the optimal dual solution of the Benders' decomposition subproblem. 53 * The resulting cut is: 54 * \f[ 55 * \varphi \geq z(\bar{x}) + w^{T} \nabla_x g(\bar{x}, y) (x-\bar{x}) 56 * \f] 57 * 58 */ 59 60 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 61 62 #ifndef __SCIP_BENDERSCUT_OPT_H__ 63 #define __SCIP_BENDERSCUT_OPT_H__ 64 65 66 #include "scip/def.h" 67 #include "scip/type_benders.h" 68 #include "scip/type_benderscut.h" 69 #include "scip/type_cons.h" 70 #include "scip/type_lp.h" 71 #include "scip/type_misc.h" 72 #include "scip/type_nlp.h" 73 #include "scip/type_retcode.h" 74 #include "scip/type_scip.h" 75 #include "scip/type_exprinterpret.h" 76 77 #ifdef __cplusplus 78 extern "C" { 79 #endif 80 81 /** creates the optimality Benders' decomposition cut and includes it in SCIP 82 * 83 * @ingroup BenderscutIncludes 84 */ 85 SCIP_EXPORT 86 SCIP_RETCODE SCIPincludeBenderscutOpt( 87 SCIP* scip, /**< SCIP data structure */ 88 SCIP_BENDERS* benders /**< Benders' decomposition */ 89 ); 90 91 /** @addtogroup BENDERSCUTS 92 * @{ 93 */ 94 95 /** Generates a classical Benders' optimality cut using the dual solutions from the subproblem or the input arrays. If 96 * the dual solutions are input as arrays, then a mapping between the array indices and the rows/variables is required. 97 * This method can also be used to generate a feasiblity, is a problem to minimise the infeasibilities has been solved 98 * to generate the dual solutions 99 */ 100 SCIP_EXPORT 101 SCIP_RETCODE SCIPgenerateAndApplyBendersOptCut( 102 SCIP* masterprob, /**< the SCIP instance of the master problem */ 103 SCIP* subproblem, /**< the SCIP instance of the pricing problem */ 104 SCIP_BENDERS* benders, /**< the benders' decomposition */ 105 SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */ 106 SCIP_SOL* sol, /**< primal CIP solution */ 107 int probnumber, /**< the number of the pricing problem */ 108 char* cutname, /**< the name for the cut to be generated */ 109 SCIP_Real objective, /**< the objective function of the subproblem */ 110 SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */ 111 SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */ 112 SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */ 113 SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */ 114 SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */ 115 SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */ 116 SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */ 117 SCIP_Bool addcut, /**< should the Benders' cut be added as a cut or constraint */ 118 SCIP_Bool feasibilitycut, /**< is this called for the generation of a feasibility cut */ 119 SCIP_RESULT* result /**< the result from solving the subproblems */ 120 ); 121 122 /** adds the gradient of a nonlinear row in the current NLP solution of a subproblem to a linear row or constraint in the master problem 123 * 124 * Only computes gradient w.r.t. master problem variables. 125 * Computes also the directional derivative, that is, mult times gradient times solution. 126 */ 127 SCIP_EXPORT 128 SCIP_RETCODE SCIPaddNlRowGradientBenderscutOpt( 129 SCIP* masterprob, /**< the SCIP instance of the master problem */ 130 SCIP* subproblem, /**< the SCIP instance of the subproblem */ 131 SCIP_BENDERS* benders, /**< the benders' decomposition structure */ 132 SCIP_NLROW* nlrow, /**< nonlinear row */ 133 SCIP_Real mult, /**< multiplier */ 134 SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */ 135 SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */ 136 SCIP_Real* dirderiv, /**< storage to add directional derivative */ 137 SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */ 138 SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */ 139 int* nvars, /**< the number of variables in the cut */ 140 int* varssize /**< the number of variables in the array */ 141 ); 142 143 /** @} */ 144 145 #ifdef __cplusplus 146 } 147 #endif 148 149 #endif 150