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_EXPORT SCIP_RETCODE | SCIPincludeBenderscutInt (SCIP *scip, SCIP_BENDERS *benders) |