Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Generates a standard Benders' decomposition optimality cut.

Author
Stephen J. Maher

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)