# Polyhedral theory

## 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

$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 ≤ 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.