Polyhedral theory

From Cophy
Jump to: navigation, search

Contents

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 aTx ≤ bi. 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

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


Polytope

A polytope is a polyhedron covering a finite region.

Example

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

\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

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 ≤ b}, an inequality ax ≤ a0 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 ∩ {x |  ax = a0} is a facet of P, the inequality ax ≤ a0 is called facet defining inequality for P.

If ax ≤ a0 is valid and the intersection of the affine subspace H = {x |  aTx = a0} with the polytope P is both empty and not equal to PH ∩ P is called a face of P.

Example

In the picture above, the inequality x1 + x2 ≤ 0 is valid for the polytope.

Furthermore, {x ∈ P |   − x1 + x2 = 0} is a face of P.
Personal tools