Premium
New lower planes for the network design problem
Author(s) -
Ahuja R. K.,
Murty V. V. S.
Publication year - 1987
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.3230170202
Subject(s) - upper and lower bounds , plane (geometry) , mathematics , function (biology) , combinatorics , computational complexity theory , network planning and design , mathematical optimization , algorithm , computer science , geometry , mathematical analysis , telecommunications , evolutionary biology , biology
A lower plane for the network design problem is a linear lower approximation of the objective function and is used to obtain a lower bound in the branch and bound algorithm. In this article, we derive two new lower planes for the network design problems through combinatorial arguments. The first lower plane is of complexity O ( n 4 ) and produces a lower bound which is sharper than those of existing lower planes. The second lower plane is of complexity O ( n 3 ) and produces a reasonably good lower bound. Computational results are presented comparing the bounds obtained by the new lower planes with those of the existing lower planes.