Dan Bienstock, Lecture 4



In the first two lectures we described theoretically good algorithmic schemes for approximately solving general classes of linear programs.

The paramount question that arises is: are these algorithms fast in practice? The question is relevant because there are many real-world applications, particularly arising in networking, which generate extremely demanding linear programs. For example, a network provisioning problem on a network with (say) ten thousand nodes will give rise to a linear program with hundreds or thousands of millions of variables and millions of constraints, beyond the capabilities of linear programming software available today and in the near future. Even smaller problems, for example concerning metropolitan area networks, have millions of variables and hundreds of thousands of constraint, and are already essentially unsolvable using the best LP solvers and fast computers.

We will describe a general-purpose implementation of the exponential potential function method, augmented with other methodological components, that yields very good performance (several orders of magnitude faster than commercial linear programming codes, and faster than special-purpose algorithms), while solving large-scale real-world problems to sufficient accuracy (and sometimes to very high accuracy). We will also discuss possible theoretical implications of our experiments, and future research directions.

Back to the IPCO VIII Program.