benderscut_feas.h File Reference

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_RETCODE	SCIPincludeBenderscutFeas (SCIP *scip, SCIP_BENDERS *benders)