Approximation Algorithms for Linear Programming:
From Theory to Growing Practice

Daniel Bienstock
Department of Industrial Engineering and 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.