Premium
A characterization of the two‐commodity network design problem
Author(s) -
Sastry Trilochan
Publication year - 2000
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/1097-0037(200008)36:1<9::aid-net2>3.0.co;2-l
Subject(s) - shortest path problem , polyhedron , mathematical optimization , flow network , minimum cost flow problem , integer programming , path (computing) , linear programming , characterization (materials science) , node (physics) , multi commodity flow problem , mathematics , longest path problem , graph , network planning and design , directed graph , integer (computer science) , computer science , combinatorics , computer network , materials science , structural engineering , engineering , programming language , nanotechnology
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. © John Wiley & Sons, Inc.