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