Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Standard feasibility cuts for Benders' decomposition.

Author
Stephen J. Maher

The classical Benders' decomposition feasibility cuts arise from an infeasible instance of the Benders' decomposition subproblem. 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 infeasible as a result of the solution \(\bar{x}\), then the Benders' decomposition feasibility cut can be generated from the dual ray. Let \(w\) be the vector corresponding to the dual ray of the Benders' decomposition subproblem. The resulting cut is:

\[ 0 \geq w^{T}(h - Hx) \]

Definition in file benderscut_feas.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 SCIPincludeBenderscutFeas (SCIP *scip, SCIP_BENDERS *benders)