Polyhedral theory

Introduction

In this article we describe the concept of polyhedral theory as a tool to describe e.g. combinatorial optimization problems by means of a set of solutions. Polyhedra can be used to formally describe the structure of a problem and this description can also be used to solve some optimization problems.

Convex polyhedron

A convex polyhedron $P$ is a set of points $\scriptstyle x\ \in\ \mathbb{R}^n$ that can be written as the solution set of an inequality system $\scriptstyle P = \{x\ \in\ \mathbb{R}^n |\ Ax\ \le\ b\}$, where $\scriptstyle A\ \in\ \mathbb{R}^{m \times n}$ is a matrix, and $\scriptstyle b\ \in\ \mathbb{R}^m$ is a vector. Thus a polyhedron is the intersection of finitely many inequalities of the form $a^Tx\ \le\ b_i$. Furthermore the number of points $\scriptstyle x\ \in\ \mathbb{R}^n$ in a polyhedron can be inifinite if the polyhedron contains infinite rays as shown in the following example.

Example

$P = \{x\ \in\ \mathbb{R}^n | \begin{pmatrix} -1 & 1\\ 1 & -2 \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix}\ \le\ \begin{pmatrix} 0 \\ 0 \end{pmatrix} \}\,\!$

Polytope

A polytope is a polyhedron covering a finite region.

Example

$P = \{x\ \in\ \mathbb{R}^n |\ \begin{pmatrix} -1 & 1 \\ 1 & -2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}\ \le\ \begin{pmatrix} 0 \\ 0 \\ 6 \end{pmatrix} \}\,\!$

Convex polytope

A convex polytope is the convex hull of finitely many points, in formulars

$\begin{array}{lcl} P & = & conv(\{x_1,...,x_r\}),\ with\ x_1,...,x_r\ \in \mathbb{R}^n \\ & = & \{x\ \in\ \mathbb{R}^n |\ x = \sum\limits_{j = 1}^s \lambda_j x_j,\ \lambda_j\ \ge\ 0\ \forall j = 1,...s,\ \sum\limits_{j = 1}^s \lambda_j = 1\}. \end{array}$

Example

By classical theorems of Minkowski & Weyl (cf. [Minkowski (1897)],[Weyl (1935)]), we always find a matrix $A$ and a vector $b$ such that a convex polytope $P$ can be written as the solution set of the inequality system $\scriptstyle P = \{x\ \in\ \mathbb{R}^n |\ Ax\ \le\ b\}$.

Valid inequalities

Given a polytope $P = \{x|\ Ax\ \le\ b\}$, an inequality $ax\ \le\ a_0$ is called a valid inequality, if $\scriptstyle a\bar{x}\ \le\ a_0$ for all points $\scriptstyle \bar{x}\ \in\ P$. In the notion of combinatorial optimization such a point $\scriptstyle \bar{x}\ \in\ P$ is called feasible solution and therefor $P$ represents the set of all feasible solutions of an optimization problem.

Faces and facets

Let the dimension of $P$ be $d$. The faces of maximum dimension of $P$, namely $d - 1$, are called facets of $P$. If $P\ \cap\ \{x|\ ax = a_0\}$ is a facet of $P$, the inequality $ax\ \le\ a_0$ is called facet defining inequality for $P$.

If $ax\ \le\ a_0$ is valid and the intersection of the affine subspace $H = \{x|\ a^Tx = a_0\}$ with the polytope $P$ is both empty and not equal to $P,\ H\ \cap\ P$ is called a face of $P$.

Example

In the picture above, the inequality $-x_1 + x_2\ \le\ 0$ is valid for the polytope.

Furthermore, $\{x\ \in\ P |\ -x_1 + x_2 = 0\}$ is a face of $P$.