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.
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.
A polytope is a polyhedron covering a finite region.
A convex polytope is the convex hull of finitely many points, in formulars
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 .
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
In the picture above, the inequality is valid for the polytope.Furthermore, is a face of .