corc logo

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.