Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms

Nevena Lazic, Brendan Frey, Parham Aarabi
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:429-436, 2010.

Abstract

The Uncapacitated Facility Location Problem (UFLP) is one of the most widely studied discrete location problems, whose applications arise in a variety of settings. We tackle the UFLP using probabilistic inference in a graphical model - an approach that has received little attention in the past. We show that the fixed points of max-product linear programming (MPLP), a convexified version of the max-product algorithm, can be used to construct a solution with a 3-approximation guarantee for metric UFLP instances. In addition, we characterize some scenarios under which the MPLP solution is guaranteed to be globally optimal. We evaluate the performance of both max-sum and MPLP empirically on metric and non-metric problems, demonstrating the advantages of the 3-approximation construction and algorithm applicability to non-metric instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v9-lazic10a, title = {Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms}, author = {Lazic, Nevena and Frey, Brendan and Aarabi, Parham}, booktitle = {Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics}, pages = {429--436}, year = {2010}, editor = {Teh, Yee Whye and Titterington, Mike}, volume = {9}, series = {Proceedings of Machine Learning Research}, address = {Chia Laguna Resort, Sardinia, Italy}, month = {13--15 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v9/lazic10a/lazic10a.pdf}, url = {https://proceedings.mlr.press/v9/lazic10a.html}, abstract = {The Uncapacitated Facility Location Problem (UFLP) is one of the most widely studied discrete location problems, whose applications arise in a variety of settings. We tackle the UFLP using probabilistic inference in a graphical model - an approach that has received little attention in the past. We show that the fixed points of max-product linear programming (MPLP), a convexified version of the max-product algorithm, can be used to construct a solution with a 3-approximation guarantee for metric UFLP instances. In addition, we characterize some scenarios under which the MPLP solution is guaranteed to be globally optimal. We evaluate the performance of both max-sum and MPLP empirically on metric and non-metric problems, demonstrating the advantages of the 3-approximation construction and algorithm applicability to non-metric instances.} }
Endnote
%0 Conference Paper %T Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms %A Nevena Lazic %A Brendan Frey %A Parham Aarabi %B Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2010 %E Yee Whye Teh %E Mike Titterington %F pmlr-v9-lazic10a %I PMLR %P 429--436 %U https://proceedings.mlr.press/v9/lazic10a.html %V 9 %X The Uncapacitated Facility Location Problem (UFLP) is one of the most widely studied discrete location problems, whose applications arise in a variety of settings. We tackle the UFLP using probabilistic inference in a graphical model - an approach that has received little attention in the past. We show that the fixed points of max-product linear programming (MPLP), a convexified version of the max-product algorithm, can be used to construct a solution with a 3-approximation guarantee for metric UFLP instances. In addition, we characterize some scenarios under which the MPLP solution is guaranteed to be globally optimal. We evaluate the performance of both max-sum and MPLP empirically on metric and non-metric problems, demonstrating the advantages of the 3-approximation construction and algorithm applicability to non-metric instances.
RIS
TY - CPAPER TI - Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms AU - Nevena Lazic AU - Brendan Frey AU - Parham Aarabi BT - Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics DA - 2010/03/31 ED - Yee Whye Teh ED - Mike Titterington ID - pmlr-v9-lazic10a PB - PMLR DP - Proceedings of Machine Learning Research VL - 9 SP - 429 EP - 436 L1 - http://proceedings.mlr.press/v9/lazic10a/lazic10a.pdf UR - https://proceedings.mlr.press/v9/lazic10a.html AB - The Uncapacitated Facility Location Problem (UFLP) is one of the most widely studied discrete location problems, whose applications arise in a variety of settings. We tackle the UFLP using probabilistic inference in a graphical model - an approach that has received little attention in the past. We show that the fixed points of max-product linear programming (MPLP), a convexified version of the max-product algorithm, can be used to construct a solution with a 3-approximation guarantee for metric UFLP instances. In addition, we characterize some scenarios under which the MPLP solution is guaranteed to be globally optimal. We evaluate the performance of both max-sum and MPLP empirically on metric and non-metric problems, demonstrating the advantages of the 3-approximation construction and algorithm applicability to non-metric instances. ER -
APA
Lazic, N., Frey, B. & Aarabi, P.. (2010). Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 9:429-436 Available from https://proceedings.mlr.press/v9/lazic10a.html.

Related Material