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) |