Many of the problems we want are optimization tasks: the shortest path, the cheapest MST, the longest increasing subsequence. In such cases, the desired solution (1) satisfies certain constraints, and (2) is the best possible, among all solutions that satisfy these constraints.
<aside> 💡 Linear programming describes a broad class of optimization tasks in which both the constraints and the optimization criterion are linear functions.
</aside>
Given the vastness of this topic, we can separate the subject into the following dependencies:
In linear programming, we are given a set of variables, and we want to assign real values to them so as to (1) satisfy a set of linear equations and/or linear inequalities involving these variables and (2) maximize or minimize a given linear objective function.
For example, a chocolatier has two products: Pyramide, and Pyramide Nuit. How much of each should the chocolatier produce to maximize its profit? Let $x_1$ be the boxes of Pyramide it produces daily, at a profit of $1 each, and $x_2$ be the boxes of Nuit it produces, at a profit of $6 each. The daily demand of Pyramide is at most 200, and Nuit is 300. The current workforce can produce 400 boxes of chocolate total each day.
We represent the situation with a linear program:
$$ \text{Objective}\quad \max(x_1+6x_2)\\\text{Constraints}\quad\begin{aligned} x_1&\leq 200 \\x_2&\leq300\\x_1+x_2&\leq400\\x_1,x_2&\geq0\end{aligned} $$
A linear equation in $x_1$ and $x_2$ defines a line in the 2D plane, and an inequality designates a half-space, the region on one side of the line. The set of all feasible solutions, the points of $(x_1,x_2)$ that satisfy all constraints, is the intersection of the five half-spaces, as show in the figure above.
<aside> 💡 The objective line is the line obtained if you graph the objective function.
</aside>
The optimum solution is the last feasible point the objective line sees, which is a vertex of the polygon; if the slopes matched, then its last contact with the polygon could be an entire edge, at which point the optimum solution is not unique, but rather as an optimum vertex.
As a general rule of linear programs, the optimum is achieved at a vertex of the feasible program. There are two exceptions:
The linear program is infeasible — the constraints are so tight, it is impossible to satisfy all of them. For example,
$$ x_1\leq1,x_2\geq2 $$
The constraints are so loose that the region is unbounded, and it is possible to achieve an arbitrarily high value. For example,
$$ \max(x_1+x_2)\\x_1,x_2\geq 0 $$
Linear programs (LPs) can be solved by George Dantzig's simplex method. This algorithm begins at a vertex, and repeatedly looks for an adjacent vertex (connected by an edge of the feasible region) of better objective value. In this way, it performs hill-climbing, walking from neighbor to neighbor to steadily increase profit.
The simplex method uses a local test — whether a vertex has a local neighbor — to declare global optimality, because of simple geometry. Consider the profit line passing through this vertex: since all its neighbors lie below the line, the rest of the feasible polygon must also be below this line.
We could also extend LP to three dimensions. The chocolatier introduces a third product, of which it makes $x_3$ units of and brings it a $13 profit each, called Luxe. The old constraints remain the same, and the workforce can only produce a total of 400 boxes daily. In addition, Nuit and Luxe use the same packaging, and imposes a constraint of $x_2+3x_3\leq 600$. Determine the optimal production level.