# 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 that can be written as the solution set of an inequality system , where is a matrix, and is a vector. Thus a polyhedron is the intersection of finitely many inequalities of the form *a*^{T}*x* ≤ *b*_{i}. Furthermore the number of points in a polyhedron can be inifinite if the polyhedron contains infinite rays as shown in the following example.

#### Example

### Polytope

A polytope is a polyhedron covering a finite region.

#### Example

### Convex polytope

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

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

### Valid inequalities

Given a polytope *P* = {*x* | *A**x* ≤ *b*}, an inequality *a**x* ≤ *a*_{0} is called a *valid inequality*, if for all points . In the notion of combinatorial optimization such a point 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* | *a**x* = *a*_{0}} is a facet of *P*, the inequality *a**x* ≤ *a*_{0} is called *facet defining inequality* for *P*.

If *a**x* ≤ *a*_{0} is valid and the intersection of the affine subspace *H* = {*x* | *a*^{T}*x* = *a*_{0}} with the polytope *P* is both empty and not equal to *P*, *H* ∩ *P* is called a *face* of
*P*.

#### Example

In the picture above, the inequality − *x*_{1} + *x*_{2} ≤ 0 is valid for the polytope.

*x*∈

*P*| −

*x*

_{1}+

*x*

_{2}= 0} is a face of

*P*.