On solving large instances of the capacitated facility location problem

We present two sets of results pertaining to the solution of capacitated facility location problems that are large, especially with regard to the number of customers. One set of results relates to customer aggregation, while another set of results concerns the judicious selection of variable-upper-bounding (VUB) constraints to include in the initial integer-programming formulation.In many real-world instances of facility location problems, cities and towns define ‘customers’ and their ‘demands’. Such problems typically feature large metropolises that have numerous satellite townships whose total population is exceeded (often, greatly) by that of the associated metropolis. We argue that both sets of our results would be relevant in solving such problems. We discuss our computational experiences with reference to a real-world variant of the classical capacitated facility location problem that spurred the results reported here.