Reformulation of capacitated facility location problems: How redundant information can help

When solving hard combinatorial optimization problems by branch-and-bound, obtaining a good lower bound (considering a minimization problem) from the linear relaxation is crucial for the performance of the algorithm. On the other hand, we want to avoid an initial formulation that is too large. This requires careful modeling of the problem. One way of obtaining a good linear formulation is by applying a cutting plane algorithm where strong cutting planes are added if they violate the current fractional solution. By ‘strong’ cutting planes, we mean linear inequalities that define high-dimensional faces of the convex hull of feasible solutions. For some classes of inequalities, effective algorithms for identifying violated inequalities belonging to these classes have been implemented as standard features in commercial branch-and-bound packages. Such classes are for instance the knapsack cover inequalities and the flow cover inequalities that were originally developed for the knapsack problem and the single-node flow problem. These problems form relaxations of several capacitated combinatorial optimization problems such as various capacitated facility location problems. If, however, we consider traditional models for location problems, then the knapsack and single-node flow relaxations are not explicitly stated in the models, and unless we modify the models, the mentioned classes of inequalities will not be generated ‘automatically’ by the systems. The extra variables and constraints that we need to add to the traditional models in order to make the various relaxations explicit are redundant, not only to the integer formulation but also to the linear relaxation. Computational experiments do, however, indicate that the inequalities that are generated based on the relaxations are very effective and that the gain from the stronger linear relaxation far outweighs the drawback of expanding the traditional models.