G-2002-67
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.
Published December 2002 , 18 pages
Publication
Jan 2006
A note on duality gap in the simple plant location problem
, , and
European Journal of Operational Research, 174, 11–22, 2006
BibTeX reference