Affordable Access

Shortest Paths, Network Design and Associated Polyhedra

Authors
Publisher
Massachusetts Institute of Technology, Operations Research Center
Publication Date
Keywords
  • Shortest Paths
  • Multiple Capacitated Facilities
  • Polyhedral Structure
  • Convex Hull.
Disciplines
  • Communication
  • Computer Science
  • Design
  • Mathematics

Abstract

We study a specialized version of network design problems that arise in telecommunication, 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 breakeven 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 twofacility loading problem are strongly NP-hard, but that a shortest path solution provides an asymptotically "good" heuristic; and (iii) characterize the optimal solution (that is, specify a linear programming formulation with integer solutions) of the common breakeven 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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Incremental network design with shortest paths

on European Journal of Operationa...

Incremental network design with shortest paths

on European Journal of Operationa... Nov 01, 2014

Exact geodesics and shortest paths on polyhedral s...

on IEEE Transactions on Pattern A... June 2009

On finding shortest paths in nonnegative networks

on Discrete Mathematics Jan 01, 1974
More articles like this..