Premium
Solving the two‐facility network design problem with 3‐partition facets
Author(s) -
Hamid Faiz,
Agarwal Yogesh K.
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21602
Subject(s) - polyhedron , cutting plane method , mathematical optimization , linear programming , node (physics) , computer science , partition (number theory) , branch and cut , reduction (mathematics) , steiner tree problem , point (geometry) , branch and bound , mathematics , set (abstract data type) , graph theory , graph partition , upper and lower bounds , integer programming , graph , theoretical computer science , combinatorics , programming language , mathematical analysis , geometry , structural engineering , engineering
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. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(1), 11–32 2015