Polyhedral theory

From cophywiki
Jump to: navigation, search


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.


Convex Polyhedron example.jpg

 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} \}\,\!


A polytope is a polyhedron covering a finite region.


Polytope example.jpg

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

 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}


Convex Polytope example.jpg

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.


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.