Primary facets of order polytopes
From MaRDI portal
Publication:730181
Abstract: Mixture models on order relations play a central role in recent investigations of transitivity in binary choice data. In such a model, the vectors of choice probabilities are the convex combinations of the characteristic vectors of all order relations of a chosen type. The five prominent types of order relations are linear orders, weak orders, semiorders, interval orders and partial orders. For each of them, the problem of finding a complete, workable characterization of the vectors of probabilities is crucial---but it is reputably inaccessible. Under a geometric reformulation, the problem asks for a linear description of a convex polytope whose vertices are known. As for any convex polytope, a shortest linear description comprises one linear inequality per facet. Getting all of the facet-defining inequalities of any of the five order polytopes seems presently out of reach. Here we search for the facet-defining inequalities which we call primary because their coefficients take only the values -1, 0 or 1. We provide a classification of all primary, facet-defining inequalities of three of the five order polytopes. Moreover, we elaborate on the intricacy of the primary facet-defining inequalities of the linear order and the weak order polytopes.
Recommendations
Cites work
- scientific article; zbMATH DE number 3152611 (Why is no real title available?)
- scientific article; zbMATH DE number 3156726 (Why is no real title available?)
- scientific article; zbMATH DE number 3902051 (Why is no real title available?)
- scientific article; zbMATH DE number 3683298 (Why is no real title available?)
- scientific article; zbMATH DE number 53952 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 0, 1/2‐Cuts and the Linear Ordering Problem: Surfaces That Define Facets
- A combinatorial study of partial order polytopes
- Betweenness, orders and interval graphs
- Combinatorial optimization and small polytopes
- Complexity results for extensions of median orders to different types of remoteness
- Consensus theories. An oriented survey
- Facets of the linear ordering polytope
- Facets of the weak order polytope derived from the induced partition projection
- How to recycle your facets
- Integer Programming
- NP-hardness results for the aggregation of linear orders into median orders
- On the computation of median linear orders, of median complete preorders and of median weak orders
- On the partial order polytope of a digraph
- Random relations, random utilities, and random functions
- Random utility representation of binary choice probabilities: A new class of necessary conditions
- Random utility representation of binary choice probabilities: Critical graphs yielding critical necessary conditions
- Several unresolved conceptual problems of mathematical psychology
- Shelling polyhedral 3-balls and 4-polytopes
- Ternary paired comparisons induced by semi- or interval order preferences
- The interval order polytope of a digraph
- The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
- The strongest facets of the acyclic subgraph polytope are unknown
- There Are Many Models of Transitive Preference: A Tutorial Review and Current Perspective
- Weak order polytopes.
Cited in
(11)- Adjacencies on random ordering polytopes and flow polytopes
- Multinomial models with linear inequality constraints: overview and improvements of computational methods for Bayesian inference
- Extended formulations for order polytopes through network flows
- Facets of linear signed order polytopes.
- Levelness of Order Polytopes
- A lexicographic semiorder polytope and probabilistic representations of choice
- Weak order polytopes.
- A correct response model in knowledge structure theory
- Order-chain polytopes
- Triangulations, order polytopes, and generalized snake posets
- Derivations of large classes of facet defining inequalities of the weak order polytope using ranking structures
This page was built for publication: Primary facets of order polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730181)
