Capacitated facility location: Separation algorithms and computational experience

We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems.