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
Link To Document