We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Survey on Lagrangian relaxation for MILP: importance, challenges, historical review, recent advancements, and opportunities.
- Authors
Bragin, Mikhail A.
- Abstract
Operations in areas of importance to society are frequently modeled as mixed-integer linear programming (MILP) problems. While MILP problems suffer from combinatorial complexity, Lagrangian Relaxation has been a beacon of hope to resolve the associated difficulties through decomposition. Due to the non-smooth nature of Lagrangian dual functions, the coordination aspect of the method has posed serious challenges. This paper presents several significant historical milestones (beginning with Polyak's pioneering work in 1967) toward improving Lagrangian Relaxation coordination through improved optimization of non-smooth functionals. Finally, this paper presents the most recent developments in Lagrangian Relaxation for fast resolution of MILP problems. The paper also briefly discusses the opportunities that Lagrangian Relaxation can provide at this point in time.
- Subjects
LINEAR programming; NONSMOOTH optimization; LAGRANGIAN functions; COMBINATORIAL optimization; FUNCTIONALS
- Publication
Annals of Operations Research, 2024, Vol 333, Issue 1, p29
- ISSN
0254-5330
- Publication type
Article
- DOI
10.1007/s10479-023-05499-9