A Note on Duality Gap in the Simple Plant Location Problem

, , and

BibTeX reference

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 (1978), 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. The integer friendliness of the problem structure is also investigated.

, 18 pages


A note on duality gap in the simple plant location problem
, , and
European Journal of Operational Research, 174, 11–22, 2006 BibTeX reference