• DocumentCode
    1781576
  • Title

    Facets of order polytopes

  • Author

    Doignon, Jean-Paul ; Fiorini, Samuel ; Rexhep, Selim

  • Author_Institution
    Dept. de Math., Univ. libre de Bruxelles, Brussels, Belgium
  • fYear
    2014
  • fDate
    3-5 Nov. 2014
  • Abstract
    The order polytopes we consider here are the linear order polytope, the interval order polytope, the semiorder polytope and the partial order polytope. Among their known facet defining inequalities (FDIs), many have their coefficients in {-1, 0, 1}. We consider the problem of finding all of these particular FDIs. The problem is easy for the partial order polytope. For the interval order polytope, we prove that the solution consists of the so-called io-clique inequalities of Müller and Schulz [5]. We present a characterisation of the {-1, 0, 1}-FDIs for the semiorder polytope. The similar problem for the linear order polytope remains open and seems harder to solve because of the large variety of known examples of FDIs which fall in this class.
  • Keywords
    optimisation; FDI; facet defining inequalities; interval order polytope; io-clique inequalities; linear order polytope; partial order polytope; semiorder polytope; Electronic mail; Equations; Face; Mathematical model; Psychology; Radio access networks; Vectors;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Control, Decision and Information Technologies (CoDIT), 2014 International Conference on
  • Conference_Location
    Metz
  • Type

    conf

  • DOI
    10.1109/CoDIT.2014.6996874
  • Filename
    6996874