Solving Constraint Integer Programs

Detailed Description

Standard feasibility cuts for Benders' decomposition.

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.


SCIP_RETCODE SCIPincludeBenderscutFeas (SCIP *scip, SCIP_BENDERS *benders)