Linear programming

Linear programs (LPs)

Linear program defines: variables $x_i$, objective and its constraints

Example

Determine the optimum product mix that maximizes the daily profit.

Daily demand for exterior paint cannot exceed that of exterior paint by more than 1 ton.
The maximum daily demand for interior paint is 2 tons.

Variables:

• $x_1$ … amount of exterior paint produced
• $x_2$ … amount of interior paint produced

Constraints:

• $6x_1+4x_2\le 24$
• $x_1+2x_2\le 6$
• $x_2\le x_1+1\to -x_1+x_2\le 1$
• $x_2\le 2$
• $x_1,x_2\ge 0$

Objective: maximize profit $z=5x_1+4x_2$

1. Graphical approach
   a. Find feasable solution space
   b. Find optimum
2. Matrix calculations ($x_i\ge 0$)

$$\left[\begin{array}{cc}6& 4\\ 1& 2\\ -1& 1\\ 0& 1\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]\le \left[\begin{array}{c}24\\ 6\\ 1\\ 2\end{array}\right]$$

Matrix form: $Ax\le b$, $x\ge 0$ $\to$ maximize $c^{T}x$
Standard form:

1. objective function is maximization instead of minimization $\to$ multiply with $-1$
2. all variables have non-negativity constraintes $\to$ replace single variable $x_2$ with $x_2^{\prime }-x_2^{\prime \prime }$ and have non-negativity constraints for both of those
3. turn equality constraintes into inequality constraints $\to$ replace $=$ with $\le$ and $\ge$ constraints
4. turn $\ge$ constraints into $\le$ constraints $\to$ multiply with $-1$

Example

Minimize $-2x_1+3x_2$
subject to:

• $x_1+x_2=7$
• $x_1-2x_2\le 4$
• $x_1\ge 0$

Transformations:

1. Maximize $2x_1-3x_2$
2. $x_2=x_2^{\prime }-x_2^{\prime \prime }\to x_2^{\prime },x_2^{\prime \prime }\ge 0$
3. $x_1+x_2=7\to x_1+x_2^{\prime }-x_2^{\prime \prime }\le 7$, $x_1+x_2^{\prime }-x_2^{\prime \prime }\ge 7$
4. $x_1+x_2^{\prime }-x_2^{\prime \prime }\ge 7\to -x_1-x_2^{\prime }+x_2^{\prime \prime }\le -7$

Final solution:
Maximize $2x_1-3x_2$
subject to:

• $x_1+x_2^{\prime }-x_2^{\prime \prime }\le 7$
• $-x_1-x_2^{\prime }+x_2^{\prime \prime }\le -7$
• $x_1-2x_2\le 4$
• $x_1,x_2^{\prime },x_2^{\prime \prime }\ge 0$

Convert problems to LPs

• Single-source shortest path
• Maximum flow
• Minimum-cost flow
• Multicommodity flow

Approximation algorithms with LP

Weighted vertex cover