Comparing Ad-Hoc and MIP-Based Algorithms for the Online Facility Location Problem

We consider online variants of the uncapacitated facility location problem. Facilities need to be placed, at a cost, and clients need to be assigned to them, yielding revenues. We provide an experimental comparison of two classes of algorithms: ad-hoc ones, which rely on the specific structure of the problem, and generic ones, which rely on the solution of Mixed Integer Programs (MIPs) as sub-problems. Models and algorithms from the literature assume one client to appear at a time. We generalize them, assuming that clients may arrive in batches of fixed (but arbitrary) size. We compare our batch adaptation to the original versions of the algorithms. We design four generators of rewards and costs, two being “adversarial” and two stochastic. We propose a variant of an existent MIP-based algorithm to profitably deal with stochastic settings. Our analysis shows that in each of the four settings, suitable MIP-based algorithms provide better solutions than ad-hoc ones, with a comparable computing effort. Our experiments also show that batching is in fact useful.