  # 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_EXPORT SCIP_RETCODE SCIPincludeBenderscutFeasalt (SCIP *scip, SCIP_BENDERS *benders)