Deterministic Large-Scale Decomposition Methods

Lewis Ntaimo
Additional contact information
Lewis Ntaimo: Texas A&M University

Chapter Chapter 5 in Computational Stochastic Programming, 2024, pp 155-222 from Springer

Abstract: Abstract In this chapter, we study decomposition methods for deterministic large-scale linear programs (LPs). These methods were developed in the 1960s and lay the foundation for decomposition methods for stochastic programming that followed, starting with the classical L-shaped method of Van Slyke and Wets in 1969. We begin our study with Kelley’s cutting-plane method for optimizing a convex function over a convex compact set using cutting-planes in Sect. 5.2. We then move on to Benders decomposition method in Sect. 5.3 and Dantzig–Wolfe decomposition method in Sect. 5.4. Both of these methods were developed for large-scale LPs. Benders’ problem is a large-scale LP with a special structure involving a subset of decision variables appearing in all constraints, which are referred to as “linking” or “complicating” variables. Benders decomposition can be thought of as a special case of Kelley’s method when the convex function is a value function of an LP. Therefore, as in Kelley’s method, Benders decomposition algorithm generates cutting-planes (row generation). For problems in high-dimensional space, we introduce regularized Benders decomposition to potentially reduce the number of iterations in Benders decomposition algorithm. In this version of the algorithm, we add a quadratic term to the objective function to enable the iterates not to deviate too far from the incumbent solution. Dantzig–Wolfe decomposition considers the dual to Benders’ problem. The dual problem has “linking” or “complicating” constraints, and unlike Benders decomposition, Dantzig–Wolfe decomposition generates columns instead of rows and thus is also referred to as column generation. Finally, in Sect. 5.5, we introduce Lagrangian decomposition for the Dantzig–Wolfe problem when the linking constraints are placed in the objective with a penalty term. We derive the Lagrangian dual and show how it is related to the Dantzig–Wolfe problem. We then derive a subgradient optimization algorithm for solving the Lagrangian dual problem.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-52464-6_5

Ordering information: This item can be ordered from
http://www.springer.com/9783031524646

DOI: 10.1007/978-3-031-52464-6_5

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().