Derivations of large classes of facet defining inequalities of the weak order polytope using ranking structures

Adolfo R. Escobedo () and Romena Yasmin ()
Additional contact information
Adolfo R. Escobedo: North Carolina State University
Romena Yasmin: Arizona State University

Journal of Combinatorial Optimization, 2023, vol. 46, issue 3, No 2, 45 pages

Abstract: Abstract Ordering polytopes have been instrumental to the study of combinatorial optimization problems arising in a variety of fields including comparative probability, computational social choice, and group decision-making. The weak order polytope is defined as the convex hull of the characteristic vectors of all binary orders on n alternatives that are reflexive, transitive, and total. By and large, facet defining inequalities (FDIs) of this polytope have been obtained through simple enumeration and through connections with other combinatorial polytopes. This paper derives five new large classes of FDIs by utilizing the equivalent representations of a weak order as a ranking of n alternatives that allows ties; this connection simplifies the construction of valid inequalities, and it enables groupings of characteristic vectors into useful structures. We demonstrate that a number of FDIs previously obtained through enumeration are actually special cases of the large classes. This work also introduces novel construction procedures for generating affinely independent members of the identified ranking structures. Additionally, it states two conjectures on how to derive many more large classes of FDIs using the featured techniques.

Keywords: Order polyhedra; Weak orders; Rankings; 06A07; 52B12; 90C27; 90C57 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01075-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:46:y:2023:i:3:d:10.1007_s10878-023-01075-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01075-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().