Permutation Polyhedra

Certain combinatorial optimization problems can be solved easily because of the existence of a linear cost function over special polyhedra whose extreme points can be associated with the feasible combinations. One of the simpler examples is the polyhedron associated with assignment problems. This paper introduces the concept of permutation polyhedra which provides a natural framework for discussing linear programming formulations of combinatorial problems that is dependent on isomorphisms between feasible combinations and extreme points of a polyhedron rather than construction of meaningful variables and their intuitively associated linear constraints. In addition, a new permutation polyhedron is constructed starting with an isomorphism between permutations and special graphs.