In the previous section we saw how the feasible region of a linear program is constructed as the intersection of a number of halfplanes, one for each constraint. Using this insight we developed a graphical approach for solving 2D LPs. Together with Fourier-Motzkin elimination as a means for reducing the dimensionality of an LP, this gave us a general method for solving linear programs.

Unfortunately Fourier-Motzkin produces a rather large number of constraints, so it is unsuited for solving problems with many variables.

In this section I will talk more about the properties of the feasible region. With more knowledge about the feasible region, we’ll eventually be able to understand a very popular method for solving linear programs, the Simplex Method.

Let us start by introducing some notation and some terms.

Already in the last part we started writing the variables x1,,xnx_1,\ldots, x_n as a column vector x\vec x and the constants aija_{ij} as a row vector ai\vec a_i. We did the same with the cost function, writing the weights for each variable as a row vector c\vec c. This way we could use the dot product instead of writing sums explicitly.

aix=ai1x1++ainxn \vec a_i \cdot \vec x = a_{i1}x_1+\ldots+a_{in}x_n

The constraints can be written using a matrix vector product. We write the ajia_{ji} in a matrix AA like so

A=(a11a12a1na21am1amn) A=\left(\begin{aligned} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & \ldots \\ \vdots & \\ a_{m1} & \ldots & & a_{mn} \end{aligned}\right)

Note that the rows of AA are simply the vectors ai\vec a_i.

Now we can write the constraints simply as AxbAx\le b, where bb is a column vector of the bjb_j. Summarizing we get the general form of a linear program:

minimize:cxsubject to:Axb\begin{aligned} \text{minimize:}& \vec c \cdot \vec x \\ \text{subject to:} & A \cdot \vec x \le \vec b\end{aligned}

Note that it really doesn’t matter whether we use \le or \ge. Just multiplying by 1-1 switches a constraint around without changing it.

Def A polyhedron is a set in Rn\text{R}^n whose members obey a set of linear inequalities {xRn|Axb}ARm×n,bRm\{x\in \text{R}^n | Ax \geq b\} \qquad A\in \text{R}^{m\times n},\ b\in \text{R}^m If the region is bounded (i.e. it has a finite volume) it can also be called polytope. We say nn is the dimensionality of the polyhedron.

I already used the word halfspace without giving a formal definition. Let us remedy this.

Def Let a,xRna,x\in \text{R}^n, a0a\neq 0.

  1. {x|ax=b}\{x|ax=b\} is a hyperplane (a line in 2D)
  2. {x|axb}\{x|ax\geq b\} is a halfspace (halfplane in 2D)

With this definition we can say that a polyhedron is an intersection of a bunch of halfspaces.

Corners of Polyhedra

A corner of a nn-dimensional polyhedron is, intuitively, a point where nn edges meet. I will give a bunch of different definitions and them prove them to be equal.

The simplest definition uses a line. A corner of a polyhedron is a point pp in the polyhedron where we can find a line that touches the polyhedron only at pp.

Def Let PP be a polyhedron. A vector xPx\in P is a vertex of P if cRn\exists \vec c\in \text{R}^n s.t. cx<cycx < cy for all yP,yxy\in P, y \neq x; that is, xx is the minimal point for some cost vector cc (the unique optimal solution for some LP with the feasible set P). See figure [Fig:vertex]

[Fig:vertex] A vertex x is the optimal solution for a cost vector c

[Fig:vertex] A vertex xx is the optimal solution for a cost vector cc

Corners are interesting for optimization because the converse is also kind of true, at least for bounded polyhedra. For any cost vector cc, we can find a vertex xx of the (bounded) polyhedron such that cxcycx \le cy for all points yy in the polyhedron. There is no strict inequality here because the line defined by cc might be parallel to one of the edges of the polyhedron. If the polyhedron is not bounded, there are some cc such that for any point yy there is a point yy' such that cy<cycy' < cy, that is, the optimal value for this cost vector is unbounded. These are of course the cost vectors that define a line that doesn’t leave the polyhedron.

However, we need some more definitions and theorems before we can prove the above statement.

Def An extreme point of a polyhedron P is a vector xPx\in P s.t. xx is not a convex combination of any two distinct vectors y,zPy,z\in P different from xx.

Convex combinations of two points x,yx,y are all points zz for which the equation λx+(1λ)y=z\lambda x + (1-\lambda) y = z has a solution for λ\lambda in [0,1][0,1]. Geometrically, the points zz lie on a line between xx and yy. You can also take the convex combinations of more than two points. The principle is the same though, you add all the points, scaling each one with a non-negative scaling factor λi\lambda_i. The combination is convex if the λi\lambda_i sum to 1.

Example: In 2D we can always select the two adjacent corners of a point xx on the edge of PP if and only if xx is not a corner. Then xx will be on the line between the two corners.

Def Let PP be a polyhedron that is defined by some linear inequalities aia_i: P={x|aixbi}P=\{x|a_ix\geq b_i\}. We’ll say that the ii-th constraint is active at a point xx if we have equality: aix=bia_ix = b_i

The constraints define the edges of polyhedron. If a point is on an edge that constraint is active. Intuitively the point must be a corner if it lies on the intersection of nn edges.

Def Let PRnP\in \text{R}^n be a polyhedron in standard form and let x*Rnx^{*}\in \text{R}^n. The vector x*x^{*} is a basic solution if at x*x^* all equality constraints are active and there are nn active constraints that are linearly independent. See solution AA in figure [Fig:bsfVSbs] for an example of a basic solution. If a basic solution is also feasible, we call it a basic feasible solution (b.f.s.). See the point BB in figure [Fig:bsfVSbs] for an example of a basic feasible solution.

[Fig:bsfVSbs] Some LP. Solution A is a basic solution. Solution B is a basic feasible solution.

[Fig:bsfVSbs] Some LP. Solution AA is a basic solution. Solution BB is a basic feasible solution.

A polyhedron with fever than nn constraints never has a basic solution.

Now we want to prove that the three definitions are all equivalent to each other.

Theorem Let PP be a polyhedron and xPx\in P. The following statements are equivalent

  1. xx is a vertex
  2. xx is an extreme point
  3. xx is a basic feasible solution


We show 1.) \Rightarrow 2.) \Rightarrow 3.) \Rightarrow 1.).

CC-BY-SA Adrian Neumann (PGP Key A0A8BC98)