Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms

Nevena Lazic, Brendan J. Frey, Parham AarabiAISTATS 2010

Abstract: This paper explores the intersection of probabilistic graphical models and combinatorial optimization by applying message-passing algorithms to the Uncapacitated Facility Location Problem (UFLP). We demonstrate that Max-Product Linear Programming (MPLP), combined with a novel greedy decoding scheme, provides a 3-approximation guarantee for metric instances and achieves near-optimal performance on standard non-metric benchmarks.

Introduction

The Uncapacitated Facility Location Problem (UFLP) is a fundamental NP-hard challenge in logistics and operations research. The objective is to minimize the total cost of opening facilities and assigning customers to them. Formally, given a set of potential facilities and customers, one must balance the fixed opening costs with the variable connection costs. Beyond logistics, UFLP is central to machine learning tasks like exemplar-based clustering, exemplified by algorithms such as Affinity Propagation.

Traditionally, UFLP is addressed via Integer Programming or Primal-Dual approximation algorithms. This work shifts the perspective toward probabilistic inference in graphical models, investigating whether message-passing algorithms—standard tools in machine learning—can offer the same rigorous guarantees as traditional optimization methods.

Methodology

We formulate the UFLP as a Maximum-a-Posteriori (MAP) inference problem on a factor graph. In this representation, assignment variables $x_{ij}$ indicate whether customer $i$ is served by facility $j$. Constraints, such as the requirement that every customer must be assigned to exactly one facility, are encoded as factors with infinite penalties for violations.

Factor graph representation of the UFLP, showing the relationship between assignment variables $x_{ij}$ and cost factors.

Message-Passing Algorithms

Two primary algorithms are evaluated:

  1. Max-Sum (Max-Product): An iterative algorithm that updates "messages" between nodes. While effective in practice, it lacks convergence guarantees on graphs with cycles.
  2. MPLP (Max-Product Linear Programming): A convexified version of max-product that is guaranteed to converge. MPLP performs coordinate ascent in the dual of a Linear Programming (LP) relaxation, effectively bridging the gap between message passing and traditional dual optimization.
Local message-passing structure for a variable $x_{ij}$, illustrating the exchange of beliefs between the variable and its associated factors.

Greedy Decoding

A key innovation of this work is a greedy variable assignment scheme (Algorithm 1) applied at the MPLP fixed point. When the algorithm encounters "tied beliefs"—where multiple assignments appear equally optimal—it utilizes a support graph to make decisions. This scheme ensures a 3-approximation guarantee for metric instances (where costs satisfy the triangle inequality).

Experimental Evaluation

The approach was tested on several datasets:

  • ORLIB: A standard benchmark containing non-metric UFLP instances.
  • Synthetic Metric Clustering: Euclidean distances in a 2D unit square.
  • Olivetti Face Database & Document Summarization: Non-metric clustering tasks used to evaluate versatility.

Key Results

  • Optimality: On the non-metric ORLIB dataset, MPLP with greedy decoding found globally optimal solutions for 13 out of 15 instances.
  • Decoding Efficacy: The proposed greedy decoding consistently outperformed arbitrary tie-breaking across all test cases.
  • Convergence and Bounds: While damped Max-Sum (Affinity Propagation) often converged faster, MPLP provided a theoretical upper bound on the optimal solution, offering a "safety net" for optimization.

Discussion and Conclusion

This research demonstrates that MPLP is not merely a heuristic but a mathematically rigorous tool for combinatorial optimization. By showing that message-passing messages contain sufficient information to guide a greedy algorithm to near-optimal solutions, we provide a framework for turning message-passing fixed points into approximation algorithms. Future work will focus on narrowing the approximation gap (currently 3, compared to 1.5 in specialized algorithms) and improving the computational speed of MPLP convergence.

Summary updated

BibTeX
@article{lazic2010solving,
  author = {Nevena Lazic and Brendan J. Frey and Parham Aarabi},
  title = {{Solving the Uncapacitated Facility Location Problem Using Message Passing Algorithms}},
  journal = {AISTATS},
  year = {2010},
}
Figure