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

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

Publish: Annals of Operations Research, Vol. 82, pp. 289-308, 1998

Author: K. Aardal

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 theses 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 relaxation are very effective and that the gain from the stronger linear relaxation far outweights the drawback of expanding the traditional models.

Main Focus

1. The single-level capacitated facility location problem

   1.1 Bipartitei Graph ((U, V)), A)

   1.2 Apply the minimal cover inequality for the minimum number of facility. 

         Lift the above inequalities.

   1.3 Apply the flow cover inequality for the demand node and facility node

   1.4 Effective capacity inequalities and the submodular inequalities 

2. The two-level capacitated facility location problem

   1.1. Normal formulation for TLCFLP

   1.2 Add the minimal cover inequality, the flow cover inequality and the fixed charge path inequality.

Conclusion

- This paper is very easy to understand the model formulation and the valid inequality development.

- It contribute to the enhancement of branch-and-bound algorithm.

- But, They do not consider to develop various models for solving the problem.