2.1. Linear Programs

A linear program (LP) \(P\) is an optimization problem over a set of real-valued variables \(\{x_1, \ldots, x_n\}\). We usually represent this set of variables as a vector \(x = (x_1, \ldots, x_n)\). Its description includes a linear objective function \(f(x_1, \ldots, x_n)\) and a collection of \(m\) linear constraints, that is, linear inequalities involving the variables \(x_1, \ldots, x_n\). The goal is to find an assignment of real values \({\hat x} = (\hat x_1, \ldots, \hat x_n)\) to the variables in \(x = (x_1, \ldots, x_n)\) that satisfies all constraints in \(P\) and either minimizes or maximizes the objective function value \(f(\hat x_1, \ldots, \hat x_n)\). Whether a minimum or maximum objective function value is sought is part of the problem description and the problem is accordingly called a minimization LP or a maximization LP. An assignment \(\hat x\) that minimizes or maximizes the objective function value subject to the given set of linear constraints is called an optimal solution of the LP \(P\). If \(\hat x\) satisfies the constraints in \(P\) but may or may not maximize \(f(\hat x_1, \ldots, \hat x_n)\), then \(\hat x\) is called a feasible solution of \(P\).

Reading \((\hat x_1, \ldots, \hat x_n)\) as an \(n\)-dimensional vector, the set of feasible solutions for a single linear constraint is always a halfspace, the portion of \(\mathbb{R}^n\) on one side of an \((n-1)\)-dimensional hyperplane. This is called the feasible region of the constraint. Since a feasible solution for a set of constraints must satisfy every constraint in the set, the feasible region of the constraints in \(P\) is the intersection of the feasible regions of the individual constraints and is thus convex. This convexity, together with the linearity of the constraints and objective function is the key to solving linear programs efficiently.

As an example, consider the following linear program over two variables \(x\) and \(y\):

\[\begin{gathered} \text{Maximize } x + 2y\\ \begin{aligned} \text{s.t. (subject to) } \hphantom{3x + y} \llap{x} &\ge 0\\ y &\ge 0\\ 3x + y &\le 26\\ 4x - y &\le 31\\ 2y - x &\le 4 \end{aligned} \end{gathered}\tag{2.1}\]

The constraints and feasible region of (2.1) are shown in Figure 2.1. The optimal solution is the red point \(\bigl(\frac{48}{7}, \frac{38}{7}\bigr)\) with objective function value \(\frac{48}{7} + 2 \cdot \frac{38}{7} = \frac{124}{7}\).

Figure 2.1: The feasible region of the constraint \(3x + y \le 26\) is shaded light blue. The feasible region of the set of all constraints in (2.1) is shaded light red. The red dot is the optimal solution of (2.1). All solutions on each of the blue lines have the same objective function value. Moving in the direction indicated by the red arrow increases the objective function value.

The fact that, in this example, the optimal solution is a vertex of the feasible region is not a coincidence. Since moving the solution in a particular direction (the red arrow in Figure 2.1) increases the objective function, the maximum objective function value is always obtained at a point on the boundary of the feasible region. If this point is not a vertex of the feasible region, it is an interior point of a boundary facet of the feasible region (a segment in 2-d, an up to \((n-1)\)-dimensional convex region in higher dimensions), and every point in this facet has the same objective function value. Thus, the solution can be moved to a boundary vertex of this facet without changing the objective function value; this boundary vertex of this facet is a boundary vertex of the feasible region. The Simplex Algorithm exploits the fact that only vertices of the feasible region need to be considered in the search for an optimal solution.