Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Alternative feasibility cuts for Benders' decomposition.

Author
Stephen J. Maher

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)