|
New lower planes for the network design problems R.K. Ahuja and V.V.S. Murty, Networks 17, 113-127, 1987 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(n4) and produces a lower bound which is sharper than those of existing lower planes. The second lower plane is of complexity O(n3) 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. |