An L-shaped method with strengthened lift-and-project cuts
Open Access
- 5 May 2022
- journal article
- research article
- Published by Springer Nature in Computational Management Science
- Vol. 19 (4) , 539-565
Abstract
Lift-and-project (L &P) cuts are well-known general 0–1 programming cuts which are typically deployed in branch-and-cut methods to solve MILP problems. In this article, we discuss ways to use these cuts within the framework of Benders’ decomposition algorithms for solving two-stage mixed-binary stochastic problems with binary first-stage variables and continuous recourse. In particular, we show how L &P cuts derived for the master problem can be strengthened with the second-stage information. An adapted L-shaped algorithm and its computational efficiency analysis is presented. We show that the strengthened L &P cuts can significantly reduce the number of iterations and the solution time.Keywords
Funding Information
- hungarian government and the european social fund (EFOP-3.6.1-16-2016-00006)
This publication has 35 references indexed in Scilit:
- Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programsMathematical Programming, 2012
- On the separation of disjunctive cutsMathematical Programming, 2009
- Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programmingMathematical Programming, 2005
- A survey on benders decomposition applied to fixed-charge network design problemsComputers & Operations Research, 2005
- The C3 Theorem and a D2 Algorithm for Large Scale Stochastic Mixed-Integer Programming: Set ConvexificationMathematical Programming, 2005
- Dual decomposition in stochastic integer programmingOperations Research Letters, 1999
- A cutting-plane approach to mixed 0–1 stochastic integer programsEuropean Journal of Operational Research, 1997
- A multicut algorithm for two-stage stochastic linear programsEuropean Journal of Operational Research, 1988
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic ProgrammingSIAM Journal on Applied Mathematics, 1969
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962