On the Poset Polytope of a Digraph 1992

Abstract:  . We introduce the poset polytope of a digraph D, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets of D. For this polytope we prove some classes of inequalities to be facetdefining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the 2-chorded odd cycle inequalities. The polyhedral results concerning the poset polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can as well be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simple t-reinforced k-fence-inequalities is NP-complete. 1. Introduction Many combinatorial optimization ...