On capacitated network design cut–set polyhedra

This paper provides an analysis of capacitated network design cut–set polyhedra. We give a complete linear description of the cut–set polyhedron of the single commodity – single facility capacitated network design problem. Then we extend the analysis to single commodity – multifacility and multicommodity – multifacility capacitated network design problems. Valid inequalities described here are applicable to directed network design problems with any number of facility types and any level of capacities. We report results from a computational study done for testing the effectiveness of the new inequalities.

Authors and Affiliations

1. Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720-1777, USA, e-mail: atamturk@ieor.berkeley.edu, , , , , , US

   Alper Atamtürk

Received: January 2, 2001 / Accepted: September 13, 2001¶Published online February 14, 2002

Reprints and permissions