Approximately solving linear programs (Daniel Bienstock)
Large-scale optimization models arising in telecommunications and networking can give rise
to extremely intractable problems. A classical example, the maximum concurrent flow problem
(also known as the minimum congestion problem ) involves the routing of demands in a capacitated
network so that the maximum load is minimized. Real-life instances of this problem are essentially
unsolvable using commercial linear programming software. In general, optimization
models involving routing decisions, and arising in many practical contexts
(for example, logistics) show this behavior. A promising line of research concerns
the design of effective algorithms for finding approximate solutions (with
guaranteed error bounds) to optimization problems
of this type.
Our work in implementing and further developing
the so-called "exponential potential function" method has produced a code that approximately solves
linear programs of this type (and much more general linear programs) up to one thousand times faster than
possible using commercial software, and many times faster than possible using competing methods.
We are now working on (a) parallelizing our approach, (b) developing approximate methods for on-line
routing problems, and (c) generalizing the approach to other types of optimization problems.