Solving the Two-Facility Network Design Problem with 3-Partition Facets

摘要

The article studies the problem of designing telecommunication networks using transmission facilities of two different capacities. The point-to-point communication demands are met by installing a mix of facilities of both capacities on the edges to minimize total cost. We consider 3-partitions of the original graph which results in smaller 3-node subproblems. The extreme points of this subproblem polyhedron are characterized using a set of propositions. A new approach for computing the facets of the 3-node subproblem is introduced based on polarity theory. The facets of the subproblem are then translated back to those of the original problem using a generalized version of a previously known theorem. The approach has been tested on several randomly generated and real life networks. The computational results show that the new family of facets significantly strengthen the linear programming formulation and reduce the integrality gap. Also, there is a substantial reduction in the size of the branch-and-bound (B&B) tree if these facets are used. Problems as large as 37 nodes and 57 edges have been solved to optimality within a few minutes of computer time.