title   
  

Lower bounding techniques for the degree-constrained network design problem

Şahin, Güvenç and Ahuja, Ravindra K. (2009) Lower bounding techniques for the degree-constrained network design problem. Networks, 53 (4). pp. 334-344. ISSN 0028-3045

This is the latest version of this item.

Full text not available from this repository.

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 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.

Item Type:Article
Uncontrolled Keywords:network design problems; degree constraints; lower bounds; lower planes; railroad scheduling; branch-and-bound
Subjects:T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
ID Code:13271
Deposited By:Güvenç Şahin
Deposited On:04 Dec 2009 14:06
Last Modified:25 May 2011 14:20

Available Versions of this Item

Repository Staff Only: item control page