Title:
Computational Experience with Network Design Algorithms
Author:
- 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.