Approximation Algorithms for Linear Programming: From Theory to Growing Practice

Daniel Bienstock

Professor of Operations Research

Columbia University

After several decades of sustained research and testing, linear programming has evolved into a remarkably reliable, accurate and useful tool for handling industrial optimization problems.  Yet, large problems arising from several concrete applications routinely defeat the very best linear programming codes, running on the fastest computing hardware.  This is a trend that may well continue and intensify, as problem sizes escalate and the need for fast algorithms becomes more stringent.

An analysis of hard linear programming instances arising e.g. in routing problems, show that in fact traditional L.P. codes have difficulty even approximating the optimal solution to a rough degree of accuracy.  These facts have spurred a new body of research, which seeks to develop approximation algorithms for classes of linear programming problems.  This work both has roots in fundamental areas of mathematical programming and is also framed in the context of the modern theory of algorithms.  The result of this work has been a family of algorithms with solid theoretical foundations.

In this talk we present theoretical developments and experimental testing of an algorithm for computing approximate solutions to block-angular linear programs.  Our implementation decisively improves over commercial linear programming codes on large-scale problems arising in telecommunications applications.