An improved Lagrangian relaxation and dual ascent approach to facility location problems

Kurt Jörnsten and Andreas Klose ()
Additional contact information
Andreas Klose: Aarhus University

Computational Management Science, 2016, vol. 13, issue 3, No 1, 317-348

Abstract: Abstract The literature knows semi-Lagrangian relaxation as a particular way of applying Lagrangian relaxation to certain linear mixed integer programs such that no duality gap results. The resulting Lagrangian subproblem usually can substantially be reduced in size. The method may thus be more efficient in finding an optimal solution to a mixed integer program than a “solver” applied to the initial MIP formulation, provided that “small” optimal multiplier values can be found in a few iterations. Recently, a simplification of the semi-Lagrangian relaxation scheme has been suggested in the literature. This “simplified” approach is actually to apply ordinary Lagrangian relaxation to a reformulated problem and still does not show a duality gap, but the Lagrangian dual reduces to a one-dimensional optimization problem. The expense of this simplification is, however, that the Lagrangian subproblem usually can not be reduced to the same extent as in the case of ordinary semi-Lagrangian relaxation. Hence, an effective method for optimizing the Lagrangian dual function is of utmost importance for obtaining a computational advantage from the simplified Lagrangian dual function. In this paper, we suggest a new dual ascent method for optimizing both the semi-Lagrangian dual function as well as its simplified form for the case of a generic discrete facility location problem and apply the method to the uncapacitated facility location problem. Our computational results show that the method generally only requires a very few iterations for computing optimal multipliers. Moreover, we give an interesting economic interpretation of the semi-Lagrangian multiplier(s).

Keywords: Mixed integer programming; Lagrangian relaxation; Semi-Lagrangian relaxation; Facility location; Uncapacitated facility location problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10287-015-0244-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:comgts:v:13:y:2016:i:3:d:10.1007_s10287-015-0244-z

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-015-0244-z

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().