  # SCIP

Solving Constraint Integer Programs

benderscut_int.h File Reference

## Detailed Description

Generates a Laporte and Louveaux Benders' decomposition integer cut.

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)