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

Linear Programming


Problem description:

lemma: every lp is infeasible, has opt, or is unbounded

Problem formulation:

Some steps towards efficient solution:

Linear Equalities

How solve? First review systems of linear equalities.

To talk formally about polynomial size/time, need to talk about size of problems.

Claim: if $A$ is $n \times n$ matrix, then $\det(A)$ is poly in size of $A$


What if $A$ isn't square? Can we find an answer?

So can check answer in polynomial time.

2013 Lecture 13 end

Can we show there isn't an answer?




Basic Feasible Solutions

Again, let's start by thinking about structure of optimal solution.

Where can optimum be? At “corners.”

Basic solutions:

In fact, vertex, extreme point, bfs are equivalent.

Any standard form lp $\min cx,\ Ax=b,\ x\ge 0$ with opt has one at a BFS.



Vertices and Extreme Points

Two other characterizations of corner.


Extreme Point

Shows output is polynomial size:

Yields first algorithm for LP: try all bfs.

OK, this is an exponential method for finding the optimum. Maybe we can do better if we just try to verify the optimum. Let's look for a way to prove that a given solution $x$ is optimal.

2011 Lecture 10 end
2012 Lecture 12 end
Quest for nonexponential algorithm: start at an easier place: how decide if a solution is optimal?