|
Lower bounding techniques for the degree-constrained network design problem G. Sahin, and R.K. Ahuja, To appear in Networks, 2009 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. In this paper, we consider degree-constrained network design problems where we specify an upper limit on the number of arcs built at each node. Such problems arise in several contexts; one application is the blocking problem, an important railroad planning problem. Degree-constrained network design problems are NP-complete problems and implicit enumeration algorithms such as branch and bound are perhaps the most practical algorithms to solve such problems to optimality. Any branch and bound algorithm requires a lower bounding technique. In this paper, we propose two lower bounding techniques using the concept of lower planes. We use combinatorial arguments to prove the correctness of these lower planes, and illustrate them using a numerical example. |