Solving Constraint Integer Programs

Detailed Description

Alternative feasibility cuts for Benders' decomposition.

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.


SCIP_RETCODE SCIPincludeBenderscutFeasalt (SCIP *scip, SCIP_BENDERS *benders)