A New Extended Formulation with Valid Inequalities for the Capacitated Concentrator Location Problem

In this paper, we first present a new extended formulation of the Capacitated Concentrator Location Problem (CCLP) using the notion of cardinality of terminals assigned to a concentrator location. The disaggregated formulation consists of O(mn2) variables and constraints, where m denotes the number of concentrators and n the number of terminals. An immediate benefit of the extended formulation is that it is stronger than the traditional formulation consisting of O(mn) variables and constraints. We also present two classes of inequalities which exploit the cardinality effect of the extended formulation. The first class of inequalities are generalizations of the well-known Cover and (1, k)- Configuration inequalities which collectively are stronger than the original Cover and (1, k)- Configuration inequalities. The second class of inequalities, called the 2-Facility Cardinality Matching Inequality is a facet of the un-capacitated version of the Concentrator Location Problem, which can be lifted to become a strong inequality for CCLP. In our solution approach, we first solve the LP relaxation of the extended formulation. We then use separation heuristics to identify and sequentially add valid inequalities described above to further improve the lower bound. This approach is embedded in a branch-and-bound to obtain the optimal solution. We test our solution approach on a large set of bench-mark problems. We were able to demonstrate clearly that this approach was able to identify the optimal solution at the root node itself in most of the reasonable sized instances. For the much larger sized test problems, the proposed branch-and-cut procedure using the disaggregated formulation outperforms the branch-and-cut procedure applied to the traditional formulation by a significant order both in terms of CPU and the number of branches required to solve the problem to optimality.



View A New Extended Formulation with Valid Inequalities for the Capacitated Concentrator Location Problem