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 (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file benderscut_opt.h
17  * @ingroup BENDERSCUTS
18  * @brief Generates a standard Benders' decomposition optimality cut
19  * @author Stephen J. Maher
20  *
21  * The classical Benders' decomposition optimality cuts arise from a feasible instance of the Benders' decomposition
22  * subproblem. The optimality cuts are an underestimator of the subproblem objective function value. Auxiliary
23  * variables, \f$\varphi\f$ are added to the master problem as a lower bound on the subproblem objective function value.
24  *
25  * Consider a linear Benders' decomposition subproblem that takes the master problem solution \f$\bar{x}\f$ as input:
26  * \f[
27  * z(\bar{x}) = \min\{d^{T}y : Ty \geq h - H\bar{x}, y \geq 0\}
28  * \f]
29  * If the subproblem is feasible, and \f$z(\bar{x}) > \varphi\f$ (indicating that the current underestimators are not
30  * optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the
31  * subproblem. Let \f$w\f$ be the vector corresponding to the optimal dual solution of the Benders' decomposition
32  * subproblem. The resulting cut is:
33  * \f[
34  * \varphi \geq w^{T}(h - Hx)
35  * \f]
36  *
37  * Next, consider a nonlinear Benders' decomposition subproblem that takes the master problem solution \f$\bar{x}\f$ as input:
38  * \f[
39  * z(\bar{x}) = \min\{d^{T}y : g(\bar{x},y) \leq 0, y \geq 0\}
40  * \f]
41  * If the subproblem is feasible, and \f$z(\bar{x}) > \varphi\f$ (indicating that the current underestimators are not
42  * optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the
43  * subproblem. Let \f$w\f$ be the vector corresponding to the optimal dual solution of the Benders' decomposition subproblem.
44  * The resulting cut is:
45  * \f[
46  * \varphi \geq z(\bar{x}) + w^{T} \nabla_x g(\bar{x}, y) (x-\bar{x})
47  * \f]
48  *
49  */
50 
51 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
52 
53 #ifndef __SCIP_BENDERSCUT_OPT_H__
54 #define __SCIP_BENDERSCUT_OPT_H__
55 
56 
57 #include "scip/def.h"
58 #include "scip/type_benders.h"
59 #include "scip/type_benderscut.h"
60 #include "scip/type_cons.h"
61 #include "scip/type_lp.h"
62 #include "scip/type_misc.h"
63 #include "scip/type_nlp.h"
64 #include "scip/type_retcode.h"
65 #include "scip/type_scip.h"
67 
68 #ifdef __cplusplus
69 extern "C" {
70 #endif
71 
72 /** creates the optimality Benders' decomposition cut and includes it in SCIP
73  *
74  * @addtogroup BenderscutIncludes
75  * @{
76  */
79  SCIP* scip, /**< SCIP data structure */
80  SCIP_BENDERS* benders /**< Benders' decomposition */
81  );
82 
83 /** Generates a classical Benders' optimality cut using the dual solutions from the subproblem or the input arrays. If
84  * the dual solutions are input as arrays, then a mapping between the array indices and the rows/variables is required.
85  * This method can also be used to generate a feasiblity, is a problem to minimise the infeasibilities has been solved
86  * to generate the dual solutions
87  */
90  SCIP* masterprob, /**< the SCIP instance of the master problem */
91  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
92  SCIP_BENDERS* benders, /**< the benders' decomposition */
93  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
94  SCIP_SOL* sol, /**< primal CIP solution */
95  int probnumber, /**< the number of the pricing problem */
96  char* cutname, /**< the name for the cut to be generated */
97  SCIP_Real objective, /**< the objective function of the subproblem */
98  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
99  SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */
100  SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */
101  SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */
102  SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */
103  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
104  SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
105  SCIP_Bool addcut, /**< should the Benders' cut be added as a cut or constraint */
106  SCIP_Bool feasibilitycut, /**< is this called for the generation of a feasibility cut */
107  SCIP_RESULT* result /**< the result from solving the subproblems */
108  );
109 
110 /** 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
111  *
112  * Only computes gradient w.r.t. master problem variables.
113  * Computes also the directional derivative, that is, mult times gradient times solution.
114  */
117  SCIP* masterprob, /**< the SCIP instance of the master problem */
118  SCIP* subproblem, /**< the SCIP instance of the subproblem */
119  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
120  SCIP_NLROW* nlrow, /**< nonlinear row */
121  SCIP_EXPRINT* exprint, /**< expressions interpreter */
122  SCIP_Real mult, /**< multiplier */
123  SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
124  SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
125  SCIP_Real* dirderiv, /**< storage to add directional derivative */
126  SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
127  SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
128  int* nvars, /**< the number of variables in the cut */
129  int* varssize /**< the number of variables in the array */
130  );
131 
132 /** @} */
133 
134 #ifdef __cplusplus
135 }
136 #endif
137 
138 #endif
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_EXPORT SCIP_RETCODE SCIPaddNlRowGradientBenderscutOpt(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_NLROW *nlrow, SCIP_EXPRINT *exprint, 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 miscellaneous datastructures
type definitions for NLP management
type definitions for expression interpreter
#define SCIP_EXPORT
Definition: def.h:100
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
SCIP_EXPORT 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)
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_RETCODE SCIPincludeBenderscutOpt(SCIP *scip, SCIP_BENDERS *benders)
type definitions for LP management
type definitions for SCIP&#39;s main datastructure
#define SCIP_Bool
Definition: def.h:70
type definitions for Benders&#39; decomposition methods
type definitions for Benders&#39; decomposition cut
#define SCIP_Real
Definition: def.h:163
common defines and data types used in all packages of SCIP
type definitions for constraints and constraint handlers