Linear Programming

Is a technique to solve problems that require maximising or minimising a linear objective function of variables that are subject to linear constraints specified as inequalities or equalities.

Such problems can be written in many forms, but to be solved by the Simplex Algorithm it must be on Slack form.

Standard form

$$\text{maximize}\sum _{j=1}^n{c}_j{x}_j$$

\begin{equation*} \begin{split} \text{subject to} \quad \sum_{j=1}^{n} a_{ij} x_{j} &\leq b_{i} \quad \text{ for } i = 1,2, \dots m \\ x_{j} &\geq 0 \quad \text{ for } j = 1,2,\dots,n \end{split} \end{equation*}

Standard form with vectors and matrices

If we create:

• $m\times n$ matrix $\mathbf{A}=(a_{ij})$
• $m$-vector $\mathbf{b}=(b_i)$
• $n$-vector $\mathbf{c}=(c_j)$,
• $n$-vector $\mathbf{x}=(x_j)$

then we can rewrite the linear program as

$$\text{maximize}{\mathbf{c}}^T\mathbf{x}$$

\begin{equation*} \begin{split} \text{subject to} \quad \boldsymbol{Ax} &\leq \boldsymbol{b} \\ \quad \boldsymbol{x} &\geq 0 \end{split} \end{equation*}

As such a linear program in standard form can be specified by a tuple $(\mathbf{A},\mathbf{b},\mathbf{c})$.

Convert to standard form

A linear program can be transformed into standard form by addressing four potential issues:

1. Minimisation problem instead of maximisation

Convert to maximisation by negating objective function coefficients.

2. Variables without non-negativity constraints

Replace these variables with two non-negative variables. E.g. use x = x’ - x” where x’, x” ≥ 0

3. Equality instead of inequality constraints

Replace each equality constraint (f(x) = b) with two inequality constraints: f(x) ≤ b f(x) ≥ b

4. Constraints with $\ge$ instead of $\le$

Convert ≥-constraints to ≤-constraints by multiplying the entire constraint by -1

Slack form

A representation where inequality constraints are converted to equalities by adding non-negative slack variables that measure the unused capacity in each constraint.

Let $N$ denote the set of indices of the nonbasic variables, i.e. the $x$ variables used in standard form. Let $B$ be the indices for the basic variables, i.e. the slack variables introduced in slack form. We then have that $|N|=n$, $|B|=m$, and $$\begin{gathered} N\cup B= \\ 1,2,\dots ,n+m \end{gathered}$$.

The equations are indexed by the entries of $B$, and the variables on the right-hand sides are indexed by the entries of $N$. As in standard form, we use $b_i$, $c_j$, and $a_{ij}$ to denote constant terms and coefficients. We also use $\nu$ to denote an optional constant term in the objective function. Slack form is then written as

$$z=\nu +\sum _{j\in N}{c}_j{x}_j$$ $$x_i=b_i-\sum _{j\in N}{a}_{ij}{x}_j\text{for }i\in B$$

in which all variables $x$ are constrained to be nonnegative, and where $z$ is the objective function.

Thus we can concisely define a slack form by a tuple $(N,B,A,b,c,\nu )$.

Other algorithmic problems as linear programming

Source Shortest Path

TODO, CLRS pp. 859+860.

Maximum Flow Problem

given a directed graph $G=(V,E)$ with capacity $c(u,v)\ge 0$ for each edge $(u,v)\in E$, a source $s$, and a sink $t$, a flow $f:V\times V\to {\mathbb{R}}^{+}$ satisfies:

• Capacity constraint: $f_{uv}\le c(u,v)$.
• Flow conservation: ${\sum }_{v\in V}{f}_{vu}={\sum }_{v\in V}{f}_{uv}$ for $$\begin{gathered} u\in V\setminus \\ s,t \end{gathered}$$.

The objective is to maximise the net flow out of the source.

$$\text{maximize}\sum _{v\in V}{f}_{sv}-\sum _{v\in V}{f}_{vs}$$

subject to

\begin{equation*} \begin{split} f_{uv} &\leq c(u, v) \quad \text{for each } u, v \in V, \\ \sum_{v \in V} f_{vu} &= \sum_{v \in V} f_{uv} \quad \text{for each } u \in V \setminus \{s, t\}, \\ f_{uv} &\geq 0 \quad \text{for each } u, v \in V. \end{split} \end{equation*}

Examples

Converting to standard form

TODO, CLRS p. 852 example.