Technical Report 401-1994

Title

The Interval Order Polytope of a Digraph

Authors

Rudolf Müller and Andreas S. Schulz

Publication

Springer, Lecture Notes in Computer Science 920, Integer Programming and Combinatorial Optimization, ed. Egon Balas and Jens Clausen, 1995, pp. 50-64

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

We introduce the interval order polytope of a digraph D as the convex hull of interval order inducing arc subsets of D. Two general schemes for producing valid inequalities are presented. These schemes have been used implicitly for several polytopes and they are applied here to the interval order polytope. It is shown that almost all known classes of valid inequalities of the linear ordering polytope can be explained by the two classes derived from these schemes. We also provide a list of applications of the interval order polytope to combinatorial optimization problems for which to our knowledge no polyhedral descriptions have been given so far. One of them is related to analysing DNA subsequences.