Solving Constraint Integer Programs

Detailed Description

Generates a Laporte and Louveaux Benders' decomposition integer cut.

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.


SCIP_RETCODE SCIPincludeBenderscutInt (SCIP *scip, SCIP_BENDERS *benders)