Geometry

Simple Example

A company makes 2 products, A and B, each unit of A makes $1 of profit and each unit of B makes $2. The demand is \leq 300 units of A and \leq 200 units of B. Suppose the total number of work hours available is 700, and making each A takes 1 hour, making each B takes 3.

We can write this into a linear program that looks like

\begin{aligned}
    \max\,& x_1 + 6x_2\\
    \text{such that}\,& x_1 + 3x_2 &&\leq 700\\
    &x_1&&\leq 300\\
    &x_2&&\leq 200\\
    &x_1&&\geq 0\\
    &x_2&&\geq 0\\
\end{aligned}

Properties of LP

1. Real number LP is solvable in poly time.
2. Integer LP (ILP) is NP-complete.
3. Feasible region is convex. (pick any 2 points in the space, the line connecting them is in the feasible region)
4. Optimal answers appear only at vertices

Standard Form

We want to solve for values of n variables x_1, x_2, \dots x_n that satisfies m constrains while minimizing or maximizing the objective function.

\begin{aligned}
    \max\, & c^\top\bold x\\
    \text{such that}\,& A\bold x &&\leq\bold b\\
    &\bold x&&\geq 0
\end{aligned}

where A is a m\times n matrix. A and \bold b together form the constraints.

Geometric view

The feasible region is the intersection of halfspaces cut by the hyperplanes given by the constraints in \R^n.

There are at least {n+m}\choose{n} vertices. For each vertex, it has \leq nm neighbors.

LP algorithms

Simplex algorithm has worst case exponential time, but fast in practice.

Basic idea:

1. Start at \bold x = \bold 0
2. Check all neighbor vertices with better objective value. Keep doing this
3. If we can't find anything better in the neighborhood, then \bold x is already the global best.

Check for Infeasibility

Add a new variable z\in \R, then try to solve

\begin{aligned}
    \max\, & z\\
    A\bold x + z &\leq \bold b\\
    \bold x&\geq 0
\end{aligned}