Premium
Shortest paths, single origin‐destination network design, and associated polyhedra
Author(s) -
Magnanti Thomas L.,
Mirchandani Prakash
Publication year - 1993
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/net.3230230205
Subject(s) - shortest path problem , polyhedron , generalization , mathematical optimization , heuristic , facility location problem , network planning and design , integer programming , computer science , point (geometry) , integer (computer science) , path (computing) , container (type theory) , linear programming , mathematics , combinatorics , theoretical computer science , graph , mathematical analysis , computer network , geometry , engineering , programming language , mechanical engineering
We study a specialized version of network design problems that arise in telecommunications, transportation, and other industries. The problem, a generalization of the shortest path problem, is defined on an undirected network consisting of a set of arcs on which we can install (load), at a cost, a choice of up to three types of capacitated facilities. Our objective is to determine the configuration of facilities to load on each arc that will satisfy the demand of a single commodity at the lowest possible cost. Our results (i) demonstrate that the single‐facility loading problem and certain “common break‐even point” versions of the two‐facility and three‐facility loading problems are polynomially solvable as a shortest path problem; (ii) show that versions of the two‐facility loading problem are strongly NP‐hard, but that a shortest path solution provides an asymptotically “good” heuristic; and (iii) characterize the optimal solution (i.e., specify a linear programming formulation with integer solutions) of the common break‐even point versions of the two‐facility and three‐facility loading problems. In this development, we introduce two new families of facets, give geometric interpretations of our results, and demonstrate the usefulness of partitioning the space of the problem parameters to establish polyhedral integrality properties. Generalizations of our results apply to (i) multicommodity applications and (ii) situations with more than three facilities. © 1993 by John Wiley & Sons, Inc.