Şahin, Güvenç and Ahuja, Ravindra K. (2009) Lower bounding techniques for the degreeconstrained network design problem. Networks, 53 (4). pp. 334344. ISSN 00283045
This is the latest version of this item.
Official URL: http://dx.doi.org/10.1002/net.20287
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 degreeconstrained 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 reallife case study from the area of railroad planning problems.
Item Type:  Article 

Uncontrolled Keywords:  network design problems; degree constraints; lower bounds; lower planes; railroad scheduling; branchandbound 
Subjects:  T Technology > T Technology (General) > T055.460.8 Industrial engineering. Management engineering T Technology > T Technology (General) > T055.460.8 Industrial engineering. Management engineering > T57.657.97 Operations research. Systems analysis 
Divisions:  Faculty of Engineering and Natural Sciences 
Depositing User:  Güvenç Şahin 
Date Deposited:  04 Dec 2009 14:06 
Last Modified:  22 May 2019 12:26 
URI:  https://research.sabanciuniv.edu/id/eprint/13271 
Available Versions of this Item

Lower Bounding Techniques for the DegreeConstrained Network Design Problem. (deposited 28 Oct 2007 18:14)

Lower Bounding Techniques for the DegreeConstrained Network Design Problem. (deposited 07 Nov 2008 16:43)
 Lower bounding techniques for the degreeconstrained network design problem. (deposited 04 Dec 2009 14:06) [Currently Displayed]

Lower Bounding Techniques for the DegreeConstrained Network Design Problem. (deposited 07 Nov 2008 16:43)