Linear Programming Fundamentals and Applications in Optimization

Purpose

Linear programming optimizes a linear objective subject to linear constraints. A huge number of combinatorial problems reduce to it, and LPs are solvable in polynomial time. This note covers the geometry, the standard form transformations, and three worked formulations: max-flow, min-cost flow, and the LP relaxation of weighted vertex cover.

Linear Systems

Systems of linear equations (key word being equality) can be solved via Gaussian elimination. The solution space of such a system is a point, a line, a plane, or a hyperplane in higher dimensions.

Let $a$ be a column vector in ${\mathbb{R}}^d$, and $x$ a column vector of $d$ variables. We can represent a linear expression using the inner product of these two vectors:

A hyperplane is the set of points $x$ such that $⟨a,x⟩=b$ for some $b$. A half-space is the set of points on one side of a hyperplane, $\{x:⟨a,x⟩\ge b\}$ or $\{x:⟨a,x⟩\le b\}$.

The intersection of a set of half-spaces is a polytope, which is a convex set. A convex set is a set where the line segment between any two points in the set stays inside the set.

Linear Programs

A linear program optimizes a linear objective function subject to linear constraints. For example:

In matrix form, stacking the constraint vectors $a_i^T$ as rows of $A$:

Standard Form

Any linear program can be written in the standard form below.

The transformations: negate the objective to turn a min into a max, negate a constraint to flip a $\ge$ into a $\le$, and split an equality into two inequalities. For example:

becomes

When a variable lacks a non-negativity constraint, replace it with the difference of two non-negative variables. For example, in

replace $y_1$ with $z_1-z_1^{\prime }$, where $z_1,z_1^{\prime }\ge 0$:

Standard form in one line

Maximize $⟨c,x⟩$ subject to $Ax\le b$ and $x\ge 0$. Four transformations reach it from any LP: negate the objective to turn min into max, negate a constraint to flip $\ge$ into $\le$, split an equality into two inequalities, and write an unconstrained variable as the difference of two non-negative ones.

Components of a Linear Program

When formulating a problem as an LP, decide each of these:

• The set of variables.
• Bounds on the variables, e.g. non-negativity.
• The objective function, and whether it is a minimization or maximization.
• The constraints, which must be linear, each either an equality or an inequality.

LPs capture problems like 2-person zero-sum games, shortest path, max-flow, matching, and multi-commodity flow, and the polynomial solvability of LPs makes them a workhorse for approximation algorithms.

Max-Flow

Given a graph $G=(V,E)$ with source $s$ and sink $t$, introduce a variable $x_e$ for the flow on each edge $e$ (see network flows).

The constraints:

• $x_e\ge 0$ for all $e$, since flow is non-negative
• $x_e\le c(e)$ for all $e$, the capacity constraint
• ${\sum }_{e\text{ out of }v}{x}_e={\sum }_{e\text{ into }v}{x}_e$ for all $v\ne s,t$, the conservation constraint

The objective maximizes flow out of the source:

The optimal LP solution is not necessarily an integer flow, though for max-flow an integer optimum always exists when capacities are integers.

Duality intuition

Every maximization LP has a dual minimization LP with the same optimal value. The dual of the max-flow LP is a fractional min-cut, so the max-flow min-cut theorem is LP duality specialized to this program.

Min-Cost Flow

Add a cost $p(e)$ per unit of flow on each edge, and minimize total cost while shipping a required flow value $f$:

Weighted Vertex Cover

Given a graph $G=(V,E)$ where each vertex has a cost $c_v$, find the vertex cover $S$ minimizing ${\sum }_{v\in S}{c}_v$.

Give each vertex a variable $x_v$, intended to be $1$ if $v\in S$ and $0$ otherwise. Covering every edge means each edge needs at least one chosen endpoint, which is the linear constraint $x_u+x_v\ge 1$:

With the extra restriction $x_v\in \{0,1\}$ this is exactly weighted vertex cover, which is NP-hard, so the integer program is not directly solvable in polynomial time. Dropping the integrality restriction gives the LP relaxation above, which is solvable in polynomial time and whose optimum $L{P}^{\ast }$ satisfies $L{P}^{\ast }\le OPT$, since every true vertex cover is a feasible LP solution.

Rounding recovers a real cover: take $S=\{v:x_v\ge \frac{1}{2}\}$. Every edge constraint $x_u+x_v\ge 1$ forces at least one endpoint to be $\ge \frac{1}{2}$, so $S$ is a vertex cover. Rounding at most doubles each variable, so

which makes this a 2-approximation for weighted vertex cover.

The LP optimum can sit strictly below OPT

On a triangle with unit costs, $x_v=\frac{1}{2}$ everywhere is feasible with value $\frac{3}{2}$, while the smallest vertex cover has two vertices. On $K_n$ the gap between $OPT=n-1$ and $L{P}^{\ast }=\frac{n}{2}$ approaches a factor of $2$, so any analysis that bounds the output against $L{P}^{\ast }$ cannot prove a ratio better than $2$ for this relaxation.

Related notes

• matrix theory
• linear algebra glossary
• network flows
• approximation algorithms