Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477861 | European Journal of Operational Research | 2006 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
N. Mladenović, J. Brimberg, P. Hansen,