Notes - ADS HT24, Linear programming

For any linear programming, exactly one of the following holds:

1. It is infeasible
2. It is feasible but unbounded
3. It is feasible, bounded, and there exists a solution that achieing the optimal

1. Convert objective function to maximum (e.g. by negating)
2. Replace equality constraints with two identical “$\le$” and “$\ge$” constraints
3. Replace “$\ge$” constraints with “$\le$” by negating
4. Make all variables non-negative by replacing $x$ with $x^+ - x^-$ where $x^+, x^- \ge 0$

\[\begin{aligned} \text{max }& c^\top x \\\\ \text{s.t. }& Ax \le b \\\\ &x\ge 0 \end{aligned}\]

\[\begin{aligned} \text{min }& b^\top y \\\\ \text{s.t. }& A^\top y \ge c \\\\ &y\ge 0 \end{aligned}\]

Observations:

• max becomes min
• $n$ variables, $m$ constraints in primal $\implies$ $m$ variables and $n$ constraints in dual
• $b _ j$s and $c _ i$s switch
• Rows of $A$ become columns in the dual

• Multiply all constraints by new variables $y _ i$
• Add new constraints that mean we can the sum as a bound for the original objective

Expanding out, we have

\[\begin{aligned} \text{max }& \sum^n_{i = 1} c_i x_i \\\\ \text{s.t. }& \sum_{j=1}^n a_{ij} x_j \le b_i \quad\text{for }i = 1, \ldots, m \\\\ &x_1, \cdots, x_n \le 0 \end{aligned}\]

We introduce new variables nonnegative $y _ i$ in hopes of using the information in the constraints to place an upper bound on the objective function. To do this, consider

\[\begin{aligned} S &:= \sum^m_{i = 1} y_i \left( \sum^n_{j = 1} a_{ij} x_j \right) \\\\ &= \sum^n_{j = 1} x_j \left( \sum^m_{i = 1} a_{ij} y_i \right) \end{aligned}\]

and the corresponding inequalities

\[\sum^m_{i = 1} a_{ij} y_i \ge c_j\]

Here, the intuition is that we are considering the sum of all possible linear combinations of constraints, and by using the new inequality, we ensure that the original objective function is bounded above by $S$, since

\[\sum^n_{i = 1} c_i x_i \le \sum^n_{j = 1} x_j \left( \sum^m_{i = 1} a_{ij} y_i \right)\]

The value that $S$ gives us is bounded by

\[\sum^m_{i = 1} b_i y_i\]

(since this is just the RHS) and so to get the best possible estimate on the value of the original objective function, we want to minimise this. Putting it all together, we see that this is equivalent to

\[\begin{aligned} \text{min }& \sum^m_{i = 1} b_i y_i \\\\ \text{s.t. }& \sum^m_{i = 1} a_{ij} y_i \ge c_j \\\\ &y \ge 0 \end{aligned}\]

or, in matrix notation

\[\begin{aligned} \text{min }& b^\top y \\\\ \text{s.t. }& A^\top y \ge c \\\\ &y\ge 0 \end{aligned}\]

as required.

• Informally, any feasible solution to the dual problem gives an upper bound on the solution to the primal problem.
• Formally, let $x \in \text{Feasible(Primal)}$ and $y \in \text{Feasible(Dual)}$. Then $c^\top x \le b^\top y$

Quick proof:

\[c^\top x = x^\top c \le x^\top A^\top y = (Ax)^\top y \le b^\top y\]

Suppose that one of the primal or dual programs is bounded and feasible. Then both are and the optimal solution for one equals the optimal solution for the other.

\[\forall y, z \in P \setminus \\{x^\star\\}, x^\star \ne \frac{y + z}{2}\]

The set $\{a _ i \mid a _ i^\top x^\star = b _ i\}$ is a linear independent collection of $n$ vectors

$x^\star$ is an extreme $\implies$ $x^\star$ is a vertex

• Let $I = \{i \in \mathbb N \mid a^\top _ i x^\star = b _ i\}$ and $A = \{a _ i \mid i \in I\}$.
• We want to show that $A$ is a collection of $n$ linearly independent vectors. Suppose it were not.
• Then $\exists w \ne 0$ s.t. $a _ i^\top w = 0$ $\forall i \in I$ (slightly confusing notation, this is a way of stating that the system $Aw = 0$ has a nontrivial solution, rather than a statement about a linear combination that make zero)
• But then we can find two vectors $x^\star \pm \varepsilon w \in P$, since
  • $\forall i \notin I$, $a _ i^\top x^\star < b _ i \implies \exists \varepsilon \text{ s.t. } a _ i^\top(x^\star \pm \varepsilon w) < b _ i$ (where the inequality stems from the original linear program)
  • $\forall i \in I$, $a _ i^\top (x^\star \pm \varepsilon w) = 0$
  • …hence $x^\star \pm \varepsilon w \in P$
• This is a contradiction, because these average to $x^\star$, contradicting the fact $x^\star$ is an extreme point

$x^\star$ is a vertex $\implies$ $x^\star$ is an extreme point

• Let $y, z \in P$ be such that $x^\star = \frac{y+z}{2}$. We aim to show $x^\star = y = z$
• Let $I = \{i \in \mathbb N \mid a _ i^\top x^\star = b _ i\}$ and $A = \{a _ i \mid i \in I\}$.
• $A$ contains $n$ linearly indepedent vectors, since $x^\star$ is a vertex
• $x^\star = \frac{y + z}{2} \implies a _ i^\top x^\star = \frac{a _ i^\top y + a _ i^\top z}{2}$.
• Since $a _ i^\top x^\star = b _ i$ but also $a _ i^\top y \le b _ i$ and $a _ i^\top z \le b _ i$, the only way this can be true if $a _ i^\top y$ and $a _ i^\top z$ both equal $b _ i$ also.
• Then $x^\star, y, z$ are solutions to the system $\{i \in I \mid a _ i^\top x = b _ i\}$. Since this system consists of $n$ linearly independent constraints, the solution must be unique and hence $x^\star = y = z$.

Start from an arbitrary vertex of the induced polyhedron, and then keep moving to neighbours with bigger values.

\[\begin{aligned} \text{max }& \sum_{e \text{ out of }s} f_e\\\\ \text{s.t. }& f_e \ge 0 \quad \text{for all edges e} \\\\ &f_e \le c(e) \quad \text{for all edges e} \\\\ &\sum_{e \text{ out of }v} f_e - \sum_{e \text{ into } v} f_e = 0 \end{aligned}\]

\[\begin{aligned} \min &\sum_{e \in E} c(e) z_e \\\\ \text{s.t. } &z_{u,v} \ge y_u - y_v &&\forall e = (u, v) \\\\ &z_e \ge 0 &&\forall e = (u, v) \\\\ &y_s = 1, y_t = 0 \end{aligned}\]

We interpret any integer optimal solution $(\pmb y^\star, \pmb z^\star)$ to the LP as forming a cut

\[(\\{u \mid y_u \ge 1\\}, \\{v \mid y_v \le 0\\})\]

and $z _ e = 1$ if the edge crosses the cut.

We add a dual variable $y _ v$ for each $v \ne s, t$, and add a dual variable $z _ e$ for each edge $e$. Then proceeding as normal, we get something close to the dual above:

\[\begin{aligned} \min &\sum_{e \in E} c(e) z_e \\\\ \text{s.t. } &y_v - y_u + z_{u,v} \ge 0 &&(1\star)\text{ } \forall e=(u,v) \text{ where } u \ne s, v \ne t \\\\ &y_v + z_{s, v} \ge 1 &&(2\star)\text{ } \forall e = (s, v) \text{ where } v \ne t \\\\ &{-y_u} + z_{u,t} \ge 0 &&(3\star)\text{ } \forall e = (s, v) \text{ where } u \ne s \\\\ &z_{s,t} \ge 1 &&(4\star)\text{ } \text{if }(s, t) \in E \\\\ &z_e \ge 0 &&(5\star)\text{ } \forall e \in E \\\\ &y_v \in \mathbb R&&(6 \star) \text{ } \text{unrestricted} \end{aligned}\]

Where does this come from? Note that in general, the constraints in any dual come from the making sure the coefficients of each primal variable in the sum of all the primal constraints are bounded below by the coefficient of each primal variable in the objective.

Here the primal objective is “really”

\[\max \sum_{e \in E} f_e \cdot \mathbb 1(e \text{ out of }s?)\]

i.e. the coefficients are $1$ if $e$ is an edge leaving $s$ and $0$ if not.

Then:

• $(1\star)$: this is the most general case. $e$ is not an edge leaving $s$
• $(2\star)$: this is the case where $e$ is an edge leaving $s$, so there is no subtraction of any $y _ s$ since no edges enter $s$
• $(3\star)$: this is the case where $e$ is entering $t$, so there is no addition of any $y _ t$ since no edges leave $t$
• $(4\star)$: this considers the case where $(s, t)$ is an edge – there are no constraints on $v = s, t$ in the primal, so we have no $y _ u$ and no $y _ v$ terms
• $(5\star)$: this is the standard nonnegativity constraints in the dual
• $(6\star)$: since we have equality constraints in the primal, the corresponding dual variable in unrestricted

To simplify this in the direction of the formulation in the question, we can add two new variables $y _ s$ and $y _ t$ with $y _ s = 1$ and $y _ t = 0$ always. This simplifies constraints $1, 2, 3, 4$ all to

\[z_{u, v} \ge y_u - y_v\]

for each edge $(u, v)$.

This gives the dual formulation in the question:

\[\begin{aligned} \min &\sum_{e \in E} c(e) z_e \\\\ \text{s.t. } &z_{u,v} \ge y_u - y_v &&\forall e = (u, v) \\\\ &z_e \ge 0 &&\forall e = (u, v) \\\\ &y_s = 1, y_t = 0 \end{aligned}\]

Now suppose we have an optimal solution $(\pmb y, \pmb z)$. Then we can replace all $y _ u > 1$ with $y _ u = 1$ and $y _ v < 0$ with $y _ v = 0$. This doesn’t change the value of the objective, but might violate the constraints.

Consider some $z _ {u, v} \ge y _ u - y _ v$. This constraint is only relevant if $y _ u > y _ v$, otherwise the constraint that $z _ e \ge 0$ is more restrictive.

Otherwise, if initially $1 \le y _ v < y _ u$, then $y _ u$ and $y _ v$ are both replaced by $1$ and the constraint on $z _ {u, v}$ becomes $z _ {u, v} \ge 0$ which is again irrelevant.

Similarly if $y _ v < y _ u \le 0$, then again the constraint becomes $z _ {u, v} \ge 0$.

Only if $y _ u \ge 1 > 0 \ge y _ v$ do we need to worry. In this case, after we modify it says $z _ {u, v} \ge 1$.

When this change is made, all active constraints have the form $z _ {u, v} \ge 1$. In any case, replacing values of $z _ {u, v}$ that are greater than $1$ with $z _ {u, v} = 1$ only decreases the objective and does not violate any constraint. So we can apply the interpretation that an optimal solution corresponds to the min cut

\[(\\{u \mid y_u \ge 1\\}, \\{v \mid y_v \le 0\\})\]

\[\begin{aligned} \text{max }& 0\\\\ \text{s.t. }& \ell(e) \le f_e \le c(e) \quad \forall e \in E\\\\ &\sum_{e \text{ into } v} f_e - \sum_{e \text{ out of } v} f_e =d(v) \quad \forall v \in V\\\\ \end{aligned}\]

We need slack variables since otherwise it’s difficult to find a point in the feasible region. This can be done like so:

\[\begin{aligned} \text{min }& \sum_{v \in V} q_v^+ + q_v^-\\\\ \text{s.t. }& \ell(e) \le f_e \le c(e) \quad \forall e \in E\\\\ &\sum_{e \text{ into } v} f_e - \sum_{e \text{ out of } v} f_e =d(v) + q_v^+-q_v^- \quad \forall v \in V\\\\ &q_v^+, q_v^- \ge 0 \quad \forall v \in V \end{aligned}\]

To find an initial solution, we can define:

\[\begin{aligned} f_e &= l(e) \\\\ A_v &= \sum_{e \text{ into }v} f_e - \sum_{e \text{ out of }v} f_e - d(v) \end{aligned}\]

Then, if $A _ v \ge 0$, set $(q _ v^+, q _ v^-) = (A _ v, 0)$, else set $(q _ v^+, q _ v^-) = (0, -A _ v)$.

\[\begin{aligned} \text{min }& \sum_{e \in E} k(e) f_e\\\\ \text{s.t. }& \ell(e) \le f_e \le c(e) \quad \forall e \in E\\\\ &\sum_{e \text{ into } v} f_e - \sum_{e \text{ out of } v} f_e =d(v) \quad \forall v \in V \end{aligned}\]

\[\begin{aligned} \text{min }& \sum_{e \in E} c(e) x_e \\\\ \text{s.t. }& \sum_{e \text{ incident on }v} x_e = 1 &\text{for } v \in L \cup R \\\\ &x_e \in \\{0, 1\\} \end{aligned}\]

Suppose $x^\star$ is an extreme point in the feasible set. This means that $\forall y, z \in \text{Feasible}, x^\star \ne \frac 1 2 (y + z)$.

Let $E’ = \{e \mid 0 < x _ e < 1\}$ and suppose for a contradiction that $ \vert E’ \vert \ne 0$. We aim to find $y, z$ such that $x^\star = \frac 1 2 (y + z)$. (Why does it suffice to consider $0 < x _ e < 1$ rather than $x _ e \in \mathbb R$? Since if we were to formulate it as a normal integer program, we would add $0 \le x _ e \le 1$)

We do this by finding a cycle of even length, and then adding a small $\pm \varepsilon$ to each edge to get the two required feasible points $y, z$.

Consider $G’ = (V, E’)$. Every vertex in $V$ has degree $0$ or degree greater than or equal to $2$. This is because either $v$ is not connected to any edges in $E’$ (though it still is connected in $E$)1, or it is and then the condition that

\[\sum_{e \text{ incident on }v} x_e = 1\]

and the fact that $0 < x _ e < 1$ means we need at least two $x _ e$ in the sum.

Then $G’$ contains a cycle $C$, and this cycle is of even length since $G$ is bipartite.

Let $\{e _ 1, \cdots, e _ {2k}\}$ be the edges of the cycle $C$, and take $\varepsilon := \min\{x _ {e _ 1}, \cdots, x _ {e _ {2k}\,}\}$. Define $y, z$ as follows:

• For even edges $e _ {2i} \in C$, $y _ {e _ {2i}\,} = x _ {e _ {2i}\,} + \varepsilon$, $z _ {e _ {2i}\,} = x _ {e _ {2i}\,} - \varepsilon$
• For odd edges $e _ {2i+1} \in C$, $y _ {e _ {2i+1}\,} = x _ {e _ {2i+1}\,} - \varepsilon$, $z _ {e _ {2i+1}\,} = x _ {e _ {2i+1}\,} + \varepsilon$
• For edges $e \notin C$, $y _ e = x _ e$ and $z _ e = x _ e$.

Note that $y$ and $z$ are still feasible: taking the $\varepsilon$ as the minimum ensures that each $x _ e$ is greater than or equal to zero, and since we alternate $\pm \varepsilon$, these cancel out for each vertex so the sum of edges incident on each $v$ is still $1$ (for clarity, note that $G$ is not a directed graph, so an edge being incident on a vertex really just means the edge is connected to that vertex).

Also $x^\star = \frac 1 2 (y + z)$, so we are done.

We can use two different approaches, the “mechanical way” and the “first principles way”.

Mechanical way: Consider the linear program as

\[\begin{aligned} \max& &&\pmb x^\top \pmb 1 \\\\ \text{s.t.}& &&A\pmb x \le \pmb 1 \\\\ & &&\pmb x \ge 0 \end{aligned}\]

where $A$ is the $m \times n$ matrix where each row corresponds to an edge, specified by two $1$s and the rest being $0$s.

Then the dual is given by:

\[\begin{aligned} \min& &&\pmb y^\top \pmb 1 \\\\ \text{s.t.}& &&A^\top\pmb y \ge \pmb 1 \\\\ & &&\pmb y \ge 0 \end{aligned}\]

which, expanding out, gives

\[\begin{aligned} \min& &&\sum_{(u, v) \in E} y_{u, v} &&& \\\\ \text{s.t.}& &&\sum_{(u, v) \in V} y_{u, v} \ge 1 &&& \forall u \in V \\\\ & &&y_{u, v} \ge 0 &&& (u, v) \in E \end{aligned}\]

From first principles: Introduce dual variables $y _ {u, v} \ge 0$ for each constraint, and consider the sum of all the constraints multiplied by these:

\[\sum_{(u, v) \in E} y_{u, v} (x_u + x_v) \le \sum_{(u, v) \in E} y_{u, v}\]

We want something of the form

\[\sum_{v \in V} x_v \Big( \cdots \Big)\]

so that it maches the objective function. Note that

\[\begin{aligned} &\sum_{(u, v) \in E} y_{u, v} (x_u + x_v) \le \sum_{(u, v) \in E} y_{u, v} \\\\ \iff& \sum_{(u, v) \in E} y_{u, v} x_u + \sum_{(u, v) \in E} y_{u, v} x_v \le \sum_{(u, v) \in E} y_{u, v} \\\\ \iff& \sum_{v \in V} x_v \sum_{(u, v) \in E} y_{u, v} \le \sum_{(u, v) \in E} y_{u, v} \end{aligned}\]

Hence we require the constraint that

\[\sum_{(u, v) \in E} y_{u, v} \le 1 \quad \forall v \in V\]

to give the overall linear program:

\[\begin{aligned} \min& &&\sum_{(u, v) \in E} y_{u, v} &&& \\\\ \text{s.t.}& &&\sum_{(u, v) \in V} y_{u, v} \ge 1 &&& \forall u \in V \\\\ & &&y_{u, v} \ge 0 &&& (u, v) \in E \end{aligned}\]

\[\begin{aligned} \text{min }& b^\top y \\\\ \text{s.t. }& A^\top y \ge c \\\\ &y \in \mathbb R\text{ (unrestricted)} \end{aligned}\]

Converting into standard maximum form you end up with

\[\begin{aligned} \text{max }& c^\top x \\\\ \text{s.t. }& Ax \le b \\\\ & {-Ax} \le {-b} \\\\ &x\ge 0 \end{aligned}\]

introducting $y^+ \ge 0$ for $Ax \le b$ and $y^- \ge 0$ for $-Ax \le -b$, you end up collecting terms to get something like

\[\sum^m_{i = 1} a_{ij} (y_i^+ - y_i^-) \ge c_j\]

But then making the substitution $y = y^+ - y^-$ means we lose the restriction on the signs.

Plot graphically. It can be hard to tell which vertex is the optimal solution, but since there aren’t that many constraints and each one is only a system of two equations, it won’t take too long to just check every vertex – also, if you don’t want to plot graphically, you can consider all pairwise intersections of the constraints and make sure that the solution satisfies the other constraint.

If $\pmb x$ and $\pmb y$ are optimal solutions to the primal and the dual, then

• For each $i = 1, \cdots, n$, if $A _ {(i)} \pmb x < b _ i$, then $y _ i = 0$
• For each $j = 1, \cdots, m$, if $\pmb y^\top A^{(j)} > c _ j$, then $x _ j = 0$

Where $A _ {(i)}$ denotes the $i$-th row, and $A^{(j)}$ denotes the $j$-th column.

By using the inequalities, we have

\[\pmb c^\top \pmb x \le y^\top A \pmb x \le \pmb y^\top \pmb b\]

By strong duality, we have that $\pmb c^\top \pmb x$ and that $\pmb y^\top \pmb b$. So these are actually equalities:

\[\pmb c^\top \pmb x = y^\top A \pmb x = \pmb y^\top \pmb b\]

Rearranging, we see

\[\pmb y^\top (\pmb b - \pmb A \pmb x) = \pmb 0\]

Then we can rewrite as

\[\sum^n_{i = 1} y_i (b_i - A_{(i)}\pmb x) = 0\]

Since $\pmb x$ is a feasible solution to the LP, all the summands are nonnegative (since $A\pmb x \le \pmb b)$. Hence if $A _ {(i)}\pmb x < b _ i$ for some $i \in \{1, \cdots, n\}$, then $y _ i = 0$.

For the dual program, the argument is symmetric.