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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s