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 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 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) \]

Next, consider the nonlinear Benders' decomposition subproblem that takes the master problem solution \(\bar{x}\) as input:

\[ z(\bar{x}) = \min\{d^{T}y : g(\bar{x}, y) \leq 0, 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 a minimal infeasible solution, i.e., a solution of the NLP

\[ \min\left\{\sum_i u_i : g(\bar{x}, y) \leq u, y \geq 0, u \geq 0\right\} \]

Let \(\bar{y}\), \(w\) be the vectors corresponding to the primal and dual solution of this auxiliary NLP. The resulting cut is:

\[ 0 \geq w^{T}\left(g(\bar{x},\bar{y}) + \nabla_x g(\bar{x},\bar{y}) (x - \bar{x})\right) \]

Note, that usually NLP solvers already provide a minimal infeasible solution when declaring the Benders' decomposition subproblem as infeasible.

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)