Linear programming notes

Summary

1. Many problems can be modeled as linear programs (LPs)
2. If you can write your problem as an LP, you can use existing, highly optimized solvers to give polynomial time algorithms to solve them

Linear program

Definition of LP

We are given

• n variables
• m linear inequalities in these variables

Matrix form

1. A matrix A with m rows and n columns
2. A vector b of length m
3. A vector c of length n

Find a length-n vector x such that :

And so that

Is as large as possible

A little more general

• Rewrite to maximize

A geometric view of linear programming

Linear optimization, find the point in the feasible solution, that is farthest from the current plot.

The optimal point would be at the corner of the polygon

History of LP algorithms

1. The simplex method
   • Not a polynomial time algorithm: for all proposed variants, there are example LPs that take exponential time to solve
2. The ellipsoid method
   • The first polynomial time algorithm for linear programming
   • Horribly slow in practice and essentially never used
3. Interior point method
   • Polynomial
   • Practical

Questions

Maximum flow as LP

We could rewrite the maximum flow problem as a linear program

Minimum cost flow as LP

Maximum Bipartite Matching

Integer linear program

If we add one more kind of constraints, we can get an integer linear program (ILP)

ILPs seem to be much more powerful and expressive than just LPs

In particular, solving ILP has no known polynomial time algorithm