benderscut_opt.h File Reference

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 alower bound on the subproblem objective function value.

Consider the 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) \]

Definition in file benderscut_opt.h.

#include "scip/def.h"
#include "scip/type_benders.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeBenderscutOpt (SCIP *scip, SCIP_BENDERS *benders)