SCIP
Solving Constraint Integer Programs
benderscut_feasalt.h File Reference
Detailed Description
Alternative feasibility cuts for Benders' decomposition.
The alternative feasibility cut for Benders' decomposition uses the optimality cut generation code to generate a cut that minimises the violation of the constraints. Consider the 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 infeasible as a result of the solution \(\bar{x}\), then some of the constraints are violated. In this case, we define an alternative/auxiliary subproblem to find a solution that minimises the constraint violations. Such a problem is given by
\[ \min\{\mathbb{1}{T}v : Ty + v \geq h - H\bar{x}, y \geq 0, v \geq 0\} \]
This auxiliary problem is guaranteed to always be feasible. Given a solution to this problem, it is possible to generate a classical Benders' optimality cut. For such a cut, the reader is referred to benderscut_opt.h.
If the Benders' decomposition subproblem contains non-linear constraints, an equivalent auxiliary subproblem can be formed to generate an alternative feasibility cut.
Definition in file benderscut_feasalt.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 | SCIPincludeBenderscutFeasalt (SCIP *scip, SCIP_BENDERS *benders) |