SMAPO

Linear ordering polytope

The linear ordering polytope LOP(n) is the convex hull of incidence vectors of acyclic tournaments in a digraph with n nodes.

References

A library of problem instances is provided by LOLIB.

LOP(6)

Status: complete description.
Number of facets: 910 in total.
5 classes wrt. node permutations.

LOP(7)

Status: complete description.
Number of facets: 87,472 in total.
27 classes wrt. node permutations.

LOP(8)

Status: conjectured complete description (updated December 2014 with PANDA by S. Lörwald and G. Reinelt).
Number of facets: 488,875,156 in total.
12,241 classes wrt. node permutations.
1,392 classes wrt. node permutations and rotation mappings.
Previous result by Christof, Reinelt:
Number of facets: 488,602,996 in total.
12,231 classes wrt. node permutations.
1,390 classes wrt. node permutations and rotation mappings.