benderscut_int.h File Reference

Detailed Description

Generates a Laporte and Louveaux Benders' decomposition integer cut.

Author

Stephen J. Maher

The classical Benders' decomposition algorithm is only applicable to problems with continuous second stage variables. Laporte and Louveaux (1993) developed a method for generating cuts when Benders' decomposition is applied to problem with discrete second stage variables. However, these cuts are only applicable when the master problem is a pure binary problem.

The integer optimality cuts are a point-wise underestimator of the optimal subproblem objective function value. Similar to benderscuts_opt.c, an auxiliary variable, $\varphi$. is required in the master problem as a lower bound on the optimal objective function value for 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 \mbox{ integer}\}$$

If the subproblem is feasible, and $z(\bar{x}) > \varphi$ (indicating that the current underestimators are not optimal) then the Benders' decomposition integer optimality cut can be generated from the optimal solution of the subproblem. Let $S_{r}$ be the set of indicies for master problem variables that are 1 in $\bar{x}$ and $L$ a known lowerbound on the subproblem objective function value.

The resulting cut is:

$$\varphi \geq (z(\bar{x}) - L)(\sum_{i \in S_{r}}(x_{i} - 1) + \sum_{i \notin S_{r}}x_{i} + 1)$$

Laporte, G. & Louveaux, F. V. The integer L-shaped method for stochastic integer programs with complete recourse Operations Research Letters, 1993, 13, 133-142

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