Extended formulations for order polytopes through network flows

DOI10.1016/j.jmp.2018.08.003zbMath1411.91181arXiv1710.02679OpenAlexW2963067120WikidataQ92582363 ScholiaQ92582363MaRDI QIDQ1736010

Samuel Fiorini, Jean-Paul Doignon, Michel Regenwetter, François Glineur, Clintin P. Davis-Stober

Publication date: 29 March 2019

Published in: Journal of Mathematical Psychology (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.02679

zbMATH Keywords

network flowsorder polytopesextended formulationsprobabilistic choicedistribution free random utility

Mathematics Subject Classification ID

Decision theory (91B06) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Individual preferences (91B08)

Related Items (5)

The interplay between transitivity and completeness: generalized \textsf{NaP}-preferences ⋮ Adjacencies on random ordering polytopes and flow polytopes ⋮ A correct response model in knowledge structure theory ⋮ Ising formulations of some graph-theoretic problems in psychological research: models and methods ⋮ Multinomial models with linear inequality constraints: overview and improvements of computational methods for Bayesian inference

Uses Software

• PORTA
• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
• Primary facets of order polytopes
• Uncapacitated flow-based extended formulations
• Applying mod-\(k\)-cuts for solving linear ordering problems
• Individual differences in the algebraic structure of preferences
• Weighted graphs defining facets: A connection between stable set and linear ordering polytopes
• The Bayes factor for inequality and about equality constrained models
• Analysis of multinomial models under inequality constraints: applications to measurement theory
• Interval graphs and interval orders
• A representation theorem for finite random scale systems
• A short proof that `proper = unit'
• Semiorders. Properties, representations, applications
• Weak order polytopes.
• A short proof of a theorem of Falmagne.
• Random relations, random utilities, and random functions
• Combinatorial optimization and small polytopes
• A short proof that the extension complexity of the correlation polytope grows exponentially
• Boolean quadric polytopes are faces of linear ordering polytopes
• A Bayesian approach to testing decision making axioms
• Facets of the linear ordering polytope: a unification for the fence family through weighted graphs
• How to recycle your facets
• Bayesian nonparametric model selection and model testing
• Composite measurement
• Intransitive indifference with unequal indifference intervals
• Description of some relations on the set of real-line intervals
• Facets of the Weak Order Polytope Derived from the Induced Partition Projection
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Ternary Paired Comparisons Induced by Semi- or Interval Order Preferences
• Facet Generating Techniques
• Constrained Statistical Inference
• Semiorders and a Theory of Utility Discrimination
• Foundational aspects of theories of measurement
• Bayes Factors
• The interval order polytope of a digraph
• 0, 1/2‐Cuts and the Linear Ordering Problem: Surfaces That Define Facets
• Extended formulations in combinatorial optimization
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Extended formulations for order polytopes through network flows