Computational Experience with Network Design Algorithms


Daniel Bienstock
Affiliation: Columbia University and Bellcore
Abstract: Network design problems can be broadly defined as follows. Given a graph (directed or not) we must route a set of $demands$ between certain pairs of vertices. To make such a routing feasible, ``capacity'' must be installed on edges (or vertices, or both) of the graph. This capacity is installed in discrete amounts, and we pay for each discrete unit of capacity (and possibly also for the demand flows). There may be additional constraints on the multicommodity routing, and on how the capacities can be added. The objective is to find a feasible combination of capacities and routing that is of minimum cost. Problems of this sort arise most commonly in telecommunications applications.

The resulting optimization problems tend to be quite difficult. In this talk we will discuss computational experience using polyhedral-based exact and approximation algorithms, as applied to actual problem instances.