About Lagrangian methods in integer optimization

About Lagrangian methods in integer optimization

0.00 Avg rating0 Votes
Article ID: iaor2006990
Country: Netherlands
Volume: 139
Issue: 1
Start Page Number: 163
End Page Number: 193
Publication Date: Oct 2005
Journal: Annals of Operations Research
Authors:
Keywords: Lagrangian methods, duality
Abstract:

It is well-known that the Lagrangian dual of an Integer Linear Program (ILP) provides the same bound as a continuous relaxation involving the convex hull of all the optimal solutions of the Lagrangian relaxation. It is less often realized that this equivalence is effective, in that basically all known algorithms for solving the Lagrangian dual either naturally compute an (approximate) optimal solution of the “convexified relaxation”, or can be modified to do so. After recalling these results we elaborate on the importance of the availability of primal information produced by the Lagrangian dual within both exact and approximate approaches to the original (ILP), using three optimization problems with different structure to illustrate some of the main points.

Reviews

Required fields are marked *. Your email address will not be published.