ON THE PARTIAL ORDER POLYTOPE OF A DIGRAPH

摘要

We introduce the partial order polytope of a digraph D, defined as the convex hull of the incidence vectors of all transitive acyclic are sets of D. For this polytope we prove some classes of inequalities to be facet-defining 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 two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can 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 N P-complete. [References: 27]