# Linear Programming I

Many optimization problems may be formulated as a linear program. Given matrix $A \in \mathbb{R}^{m \times n}$ and vectors $\vec{b} \in \mathbb{R}^{m}$$\vec{c} \in \mathbb{R}^{n}$, we seek some vector  $\vec{x} \in \mathbb{R}^{n}$ that satisfies

$A \vec{x} \leq \vec{b}$

and maximizes

$\max \{ \vec{c} \cdot \vec{x} \}$

where elements in $\vec{x} \geq 0$ are nonnegative. We call $\max \{ \vec{c} \cdot \vec{x} \}$ the objective function, and $A \vec{x} \leq \vec{b}$ are known as the constraints.

Flow Networks as Linear Programs

Pushing flow through a network reduces to linear programming!

objective:

$\max \{ \sum_{(s, u) \in E} f_{su}\}$

capacity constraints:

$\forall_{e \in E} 0 \leq f_{e} \leq c_{e}$

flow preservation:

$\forall_{v \neq s, t} \sum_{(u, v) \in E} f_{uv} = \sum_{(v, w) \in E} f_{vw}$

Decision Problem Formulation

Note that linear programs can be formulated as a decision problem. Given some $t \in \mathbb{R}$, does there exist some $\vec{x} \in \mathbb{R}^{n}$ such that

$\vec{c} \cdot \vec{x} \geq t$    and   $A \vec{x} \leq \vec{b}$

If YES, then simple provide the vector $\vec{x}$ to be verified. If NO, we need some polynomial certificate to verify there exists no such vector. This is where the notion of a ‘dual’ program comes in. But first, perhaps an example is appropriate

Diet Problem

Suppose you are given the following meal choices: burger at $9, yogurt at$6, and ramen at \$2. You also want to satisfy some dietary needs: you require at least 180 calories of protein, 100 calories of carbohydrates, and 20 calories of fat.

$\begin{tabular}{ c c c c }& protein & carbohydrates & fat \\burger & 40 & 10 & 8 \\yogurt & 15 & 20 & 5 \\ramen & 5 & 30 & 15\end{tabular}$

Given the above caloric breakdown of each meal, how can you satisfy your requirements while spending as little as possible? Let us formulate our problem as a linear program. Let $x, y, z$ be the units of burgers, yogurts, and ramen we purchase. Note that we have the following constraints

$40x + 15y + 5z \geq 180$

$10x + 20y + 30z \geq 100$

$8x + 5y + 15z \geq 20$

where we want to minimize our objective $9x + 6y + 2z$. Note that this is a minimization linear program, and to convert it to standard form, all we need to do is negate the objective and constraints, which yields the following linear program

objective:

$\max \{ -9x - 6y - 15z\}$

constraints:

$-40x - 15y - 5z \leq -180$

$-10x - 20y - 30z \leq -100$

$-8x - 5y - 15z \leq -20$

Another Problem

Consider following linear program

objective:

$\max \{ 4x_1 + x_2 + 5x_3 + 3x_4\}$

constraints:

(1) $x_1 - x_2 - x_3 + 3x_4 \leq 1$

(2) $5x_1 + x_2 + 3x_3 + 8x_4 \leq 55$

(3) $-x_1 + 2x_2 + 3x_3 - 5x_4 \leq 3$

Let us assign variable $y_{j}$ to constraint inequality (j), ensuring $y_{j} \geq 0$. Note that

\begin{aligned}y_1 (x_1 - x_2 - x_3 + 3x_4) &\leq y_1\\ y_2 (5x_1 + x_2 + 3x_3 + 8x_4) &\leq 55y_2\\ y_3 (-x_1 + 2x_2 + 3x_3 - 5x_4) &\leq 3y_3\end{aligned}

Adding each inequality together and grouping by $x_{i}$ yields

\begin{aligned}&x_1 (y_1 + 5y_2 - y_3) \\ &+ x_2 (-y_1 + y_2 + 2y_3) \\ &+ x_3 (-y_1 + y_2 + 3 y_3) \\ &+ x_4 (3y_1 + 8y_2 - 5y_3) \leq y_1 + 55 y_2 + 3 y_3\end{aligned}

For each $x_i$, constrain multiplicative term to be greater than or equal to $c_i$, yielding following constraints

$y_1 + 5y_2 - y_3 \geq 4$

$-y_1 + y_2 + 2y_3 \geq 1$

$-y_1 + 3y_2 + 3 y_3 \geq 5$

$3y_1 + 8y_2 - 5y_3 \geq 3$

These constraints ensure that $\max \{ 4x_1 + x_2 + 5x_3 + 3x_4 \} \leq \min \{ y_1 + 55 y_2 + 3 y_3 \}$. As such, this is the dual program for original linear program with objective $y_1 + 55 y_2 + 3y_3$ that we seek to minimize and constraints given above.

Dual Programs

Let $A \in \mathbb{R}^{m \times n}$ be matrix and $\vec{b} \in \mathbb{R}^{m}$$\vec{c} \in \mathbb{R}^{n}$ be vectors.

Given linear program with following objective and constraints

objective:

$\max \{ c_1x_1 + c_2x_2 + \dots + c_n x_n\}$

constraint $i$:

$a_{i1}x_1 + a_{i2}x_2 + \dots + a_{i1} x_n \leq b_{i}$

Dual program is given as follows

objective:

$\min \{ b_1y_1 + b_2y_2 + \dots + b_m y_m\}$

constraint $j$:

$a_{1j}y_1 + a_{2j}y_2 + \dots + a_{mj} y_m \geq c_{j}$

where $i \in [1, n]$$j \in [1, m]$. Weak duality states

$\max \{ \vec{c} \cdot \vec{x} | A \vec{x} \leq \vec{b}, \vec{x} \geq 0\} \leq \min \{ \vec{b} \cdot \vec{y} | A^{T} \vec{y} \geq \vec{c}, \vec{y} \geq 0\}$

Linear Programing Duality Theorem

Given primal program $P$, dual program $D$, there exist four possibilities

1. P is infeasible, which implies D is unbounded
2. P is unbounded, which implies D is infeasible
3. P, D are both infeasible
4. P, D are feasible

Linear program is infeasible if there exists no solution that satisfies all constraints, and is unbounded if objective function may be incremented towards positive or negative infinity. We shall demonstrate that in case (4), P, D have the same optimal value. We will need the following lemma to do this

Farkas’ Lemma

For any matrix $A \in \mathbb{R}^{m \times n}$, vector $\vec{b} \in \mathbb{R}^{m}$, exactly one of the following holds

1. There exists $\vec{x} \in \mathbb{R}^{n}$ such that

$\vec{x} \geq 0$ and $A \vec{x} = \vec{b}$

1. There exists $\vec{y} \in \mathbb{R}^{m}$ such that

$\vec{b} \cdot \vec{y} < 0$ and $A^{T} \vec{y} \geq 0$