A characterization of the two-commodity network design problem

A characterization of the two-commodity network design problem

0.00 Avg rating0 Votes
Article ID: iaor20022989
Country: United States
Volume: 36
Issue: 1
Start Page Number: 9
End Page Number: 16
Publication Date: Aug 2000
Journal: Networks
Authors:
Keywords: programming: linear
Abstract:

We study the uncapacitated version of the two-commodity network design problem. We characterize optimal solutions and show that when flow costs are zero there is an optimal solution with at most one shared path. Using this characterization, we solve the problem on a transformed graph with O(n) nodes and O(m) arcs based on a shortest path algorithm. Next, we describe a linear programming reformulation of the problem using O(m) variables and O(n) constraints and show that it always has an integer optimal solution. We also interpret the dual constraints and variables as generalizations of the arc constraints and node potentials for the shortest path problem. We show that the polyhedron described by the constraints of the reformulation always has an integer optimal solution for a more general two-commodity problem with flow costs and an additional condition on the cost function.

Reviews

Required fields are marked *. Your email address will not be published.