Premium
Lower bounding techniques for the degree‐constrained network design problem
Author(s) -
Şahin Güvenç,
Ahuja Ravindra K.
Publication year - 2009
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.20287
Subject(s) - bounding overwatch , subnetwork , upper and lower bounds , network planning and design , degree (music) , flow network , mathematical optimization , computer science , set (abstract data type) , node (physics) , computational complexity theory , limit (mathematics) , mathematics , algorithm , computer network , artificial intelligence , engineering , programming language , mathematical analysis , physics , structural engineering , acoustics
Abstract A typical network design problem consists of identifying a subnetwork of a given network that satisfies a set of constraints and minimizes the cost of flow. We consider degree‐constrained network design problems where we specify an upper limit on the number of arcs built at each node. We propose two lower bounding techniques using the concept of lower planes. The first lower bound is based on a known lower plane for network design problems; our second lower bound is stronger than the first, yet has the same polynomial computational complexity. We illustrate both lower bounds using a numerical example, test their performance, and present a real‐life case study from the area of railroad planning problems. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009