SCIP
Solving Constraint Integer Programs
benderscut_opt.h File Reference
Detailed Description
Generates a standard Benders' decomposition optimality cut.
The classical Benders' decomposition optimality cuts arise from a feasible instance of the Benders' decomposition subproblem. The optimality cuts are an underestimator of the subproblem objective function value. Auxiliary variables, \(\varphi\) are added to the master problem as a lower bound on the subproblem objective function value.
Consider a linear Benders' decomposition subproblem that takes the master problem solution \(\bar{x}\) as input:
\[ z(\bar{x}) = \min\{d^{T}y : Ty \geq h - H\bar{x}, y \geq 0\} \]
If the subproblem is feasible, and \(z(\bar{x}) > \varphi\) (indicating that the current underestimators are not optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the subproblem. Let \(w\) be the vector corresponding to the optimal dual solution of the Benders' decomposition subproblem. The resulting cut is:
\[ \varphi \geq w^{T}(h - Hx) \]
Next, consider a nonlinear Benders' decomposition subproblem that takes the master problem solution \(\bar{x}\) as input:
\[ z(\bar{x}) = \min\{d^{T}y : g(\bar{x},y) \leq 0, y \geq 0\} \]
If the subproblem is feasible, and \(z(\bar{x}) > \varphi\) (indicating that the current underestimators are not optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the subproblem. Let \(w\) be the vector corresponding to the optimal dual solution of the Benders' decomposition subproblem. The resulting cut is:
\[ \varphi \geq z(\bar{x}) + w^{T} \nabla_x g(\bar{x}, y) (x-\bar{x}) \]
Definition in file benderscut_opt.h.
#include "scip/def.h"#include "scip/type_benders.h"#include "scip/type_benderscut.h"#include "scip/type_cons.h"#include "scip/type_lp.h"#include "scip/type_misc.h"#include "scip/type_nlp.h"#include "scip/type_retcode.h"#include "scip/type_scip.h"#include "scip/type_exprinterpret.h"Go to the source code of this file.
Functions | |
| SCIP_RETCODE | SCIPincludeBenderscutOpt (SCIP *scip, SCIP_BENDERS *benders) |
| 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) |
| 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) |