Specially Structured Uncapacitated Facility Location Problems

This paper considers a specially structured uncapacitated facility location problem. We show that several problems, including certain tool selection problems, substitutable inventory problems, supplier sourcing problems, discrete lot sizing problems, and capacity expansion problems, can be formulated as instances of the problem. We also show that the problem with m facilities and n customers can be solved in O(mn), as a shortest path problem on a directed graph.