# 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 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 . 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 and a vector such that a convex polytope can be written as the solution set of the inequality system .

### Valid inequalities

Given a polytope , an inequality is called a *valid inequality*, if for all points . In the notion of combinatorial optimization such a point is called feasible solution and therefor represents the set of all feasible solutions of an optimization problem.

### Faces and facets

Let the dimension of be . The faces of maximum dimension of , namely , are called *facets* of . If is a facet of , the inequality is called *facet defining inequality* for .

If is valid and the intersection of the affine subspace with the polytope is both empty and not equal to is called a *face* of
.

#### Example

In the picture above, the inequality is valid for the polytope.

Furthermore, is a face of .