Scippy

SCIP

Solving Constraint Integer Programs

benderscut_opt.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright 2002-2022 Zuse Institute Berlin */
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"
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
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
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
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
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
type definitions for miscellaneous datastructures
type definitions for NLP management
type definitions for expression interpreter
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:51
type definitions for return codes for SCIP methods
type definitions for LP management
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPgenerateAndApplyBendersOptCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, char *cutname, SCIP_Real objective, SCIP_Real *primalvals, SCIP_Real *consdualvals, SCIP_Real *varlbdualvals, SCIP_Real *varubdualvals, SCIP_HASHMAP *row2idx, SCIP_HASHMAP *var2idx, SCIP_BENDERSENFOTYPE type, SCIP_Bool addcut, SCIP_Bool feasibilitycut, SCIP_RESULT *result)
#define SCIP_Bool
Definition: def.h:93
SCIP_RETCODE SCIPaddNlRowGradientBenderscutOpt(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_NLROW *nlrow, SCIP_Real mult, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx, SCIP_Real *dirderiv, SCIP_VAR ***vars, SCIP_Real **vals, int *nvars, int *varssize)
type definitions for Benders&#39; decomposition methods
type definitions for Benders&#39; decomposition cut
SCIP_RETCODE SCIPincludeBenderscutOpt(SCIP *scip, SCIP_BENDERS *benders)
#define SCIP_Real
Definition: def.h:186
common defines and data types used in all packages of SCIP
type definitions for constraints and constraint handlers