Linear Programming

A linear program consists of two components.

1. An objective function to minimize or maximize.
2. Constraints that define the feasible region.

For example, minimize $2x + 5y + 6z$ such that $3x + 4y + 3z \ge 5$, $x + y \ge 10, x,y,z \ge 0$.

There are two major methods to solve this.

Simplex Method

The simplex algorithm is based on the fact that an optimal solution always exists at a vertex of the feasible polytope (a corner formed by intersecting constraints). The reason is that the feasible region is convex and the objective is linear.

Start with a feasible solution $V = (v_1, v_2, \ldots, v_n)$.
$\operatorname{while}$ moving $V$ along a constraint boundary improves the objective

Move $V$ in the direction that most improves the objective.

Return $V$.

In practice, simplex is fast, but it cannot be guaranteed to run in polynomial time. Therefore, there is an alternative.

Ellipsoid Method

The ellipsoid algorithm uses a so-called separation oracle. A separation oracle is a procedure that, given a candidate solution, either confirms it is feasible or returns a violated constraint — all in polynomial time. Given such an oracle, we can bisect the solution space into two parts at each step: one containing an optimal solution and one discarded. Using this approach, the ellipsoid method solves any linear program in polynomial time.