Valid Inequalities for the Telecommunications Network Design Problem

This chapter addresses the problem of designing a backbone telecommunications network using transmission facilities (e.g., optical fibers) of a fixed capacity. Given a set of nodes, traffic demands among the nodes, and the costs of installing the facilities between the nodes, we need to design a minimum-cost network that can carry all the traffic demands. The problem can be modeled as a mixed integer program using a multicommodity network flow formulation. The chapter briefly introduces the concept of valid inequalities and reviews integer rounding and Chvátal-Gomory methods generating valid inequalities. It then identified the p-partition-based substructures for p = 2, 3, and 4, from which valid inequalities can be generated by applying the Chvatál-Gomory method. Several families of such inequalities are derived, and the effect of adding these inequalities is demonstrated through simple examples. A simple but effective shrinking heuristic is developed to find the p-partitions which are likely to result in violated valid inequalities. Some computational results are presented to demonstrate the effectiveness of the proposed approach.