Authors: Mladenović, Nenad 
Brimberg, Jack
Hansen, Pierre
Title: A note on duality gap in the simple plant location problem
Journal: European Journal of Operational Research
Volume: 174
Issue: 1
First page: 11
Last page: 22
Issue Date: 1-Oct-2006
Rank: M21
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2004.12.022
This paper studies the duality gap in the simple plant location problem, and presents general formulas for the gap when certain complementary slackness conditions are satisfied. We show that the duality gap derived by Erlenkotter [A dual-based procedure for uncapacitated facility location, Operations Research 26 (1978) 992-1009], and which has been widely used in the literature, is a special case of the formulas presented here. A counterexample demonstrates that an underlying assumption in Erlenkotter may be violated. The results may be used to obtain improved lower bounds for branch-and-bound algorithms.
Keywords: Duality gap | Simple plant location problem
Publisher: Elsevier

Show full item record


checked on Jun 15, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.