\documentclass{article} \usepackage{me} \usepackage{amssymb} \usepackage{amsfonts} \setlength{\parindent}{0pt} $\newcommand\vol{{\mbox{vol}}}$

Lecture 14: Algorithms for Solving LPs

LP Solving Algorithms

So far we learned a lot about the structure of LPs. But how do we actually solve them? Can we do it faster than by just enumerating all basic feasible solutions (BFS)?


Interlude: Vertices in Standard form/bases

Summary: $x$ is vertex of $P$ if for some basis $B$,

Back to the Simplex Method

Potential problems

Simplex and Duality

Polynomial Time Bounds

We know a lot about structure. And we've seen how to verify optimality in polynomial time. Now turn to question: can we solve in polynomial time?

Yes, sort of (Khachiyan 1979):

Ellipsoid Method

Basic idea: Reduce optimization to feasibility checking. (Remind how it is with polytope $P$.)

Feasibility vs. Separation vs. Optimization

Notice in ellipsoid, were only using one constraint at a time.

This is very useful in many applications. e.g. network design.

Can also show that optimization implies separation: