Enumeration of 2-level polytopes

DOI10.1007/978-3-662-48350-3_17zbMATH Open1414.05023arXiv1703.01943OpenAlexW1678874697WikidataQ129282662 ScholiaQ129282662MaRDI QIDQ1741129FDOQ1741129

Adam Bohn, Marco Macchia, Samuel Fiorini, Vissarion Fisikopoulos, Yuri Faenza, Kanstantsin Pashkovich

Publication date: 3 May 2019

Published in: Mathematical Programming Computation, Algorithms - ESA 2015 (Search for Journal in Brave)

Abstract: A (convex) polytope $P$ is said to be $2$-level if for every direction of hyperplanes which is facet-defining for $P$, the vertices of $P$ can be covered with two hyperplanes of that direction. The study of these polytopes is motivated by questions in combinatorial optimization and communication complexity, among others. In this paper, we present the first algorithm for enumerating all combinatorial types of $2$-level polytopes of a given dimension $d$, and provide complete experimental results for $dleqslant7$. Our approach is inductive: for each fixed $(d-1)$-dimensional $2$-level polytope $P_0$, we enumerate all $d$-dimensional $2$-level polytopes $P$ that have $P_0$ as a facet. This relies on the enumeration of the closed sets of a closure operator over a finite ground set. By varying the prescribed facet $P_0$, we obtain all $2$-level polytopes in dimension $d$.

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

zbMATH Keywords

optimizationformal concept analysispolyhedral computationpolyhedral combinatoricsalgorithm engineering

Mathematics Subject Classification ID

Semidefinite programming (90C22) Exact enumeration problems, generating functions (05A15) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational aspects related to convexity (52B55) Perfect graphs (05C17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polymake: an approach to modular software design in computational geometry
• Practical graph isomorphism. II.
• Enumeration of 2-level polytopes
• Comparing performance of algorithms for generating concept lattices
• Faces of Birkhoff Polytopes
• Complete enumeration of small realizable oriented matroids
• Algorithms for tight spans and tropical linear spaces
• Decompositions of Rational Convex Polytopes
• Lectures on Polytopes
• Triangulations. Structures for algorithms and applications
• Two poset polytopes
• Expressing combinatorial optimization problems by linear programs
• Geometric algorithms and combinatorial optimization.
• On certain polytopes associated with graphs
• On the geometric interpretation of the nonnegative rank
• Polytopes of minimum positive semidefinite rank
• Intersections of translates of convex bodies
• The number of faces of centrally-symmetric polytopes
• Combinatorial optimization. Packing and covering
• On determining the congruence of point sets in \(d\) dimensions
• Nonnegative polynomials and sums of squares
• Theta Bodies for Polynomial Ideals
• Theta rank, levelness, and matroid minors
• The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey
• Compressed polytopes and statistical disclosure limitation
• On Kalai's conjectures concerning centrally symmetric polytopes
• Finding all closed sets: A general approach
• Which nonnegative matrices are slack matrices?
• Four-dimensional polytopes of minimum positive semidefinite rank
• On Vertices and Facets of Combinatorial 2-Level Polytopes
• Computing the face lattice of a polytope from its vertex-facet incidences
• On a certain class of polytopes associated with independence systems.
• Many 2-level polytopes from matroids
• Two-Level Polytopes with a Prescribed Facet

Cited In (15)

• Slack matrices, \(k\)-products, and 2-level polytopes
• An algebraic approach to projective uniqueness with an application to order polytopes
• Projectively unique polytopes and toric slack ideals
• Octopuses in the Boolean cube: families with pairwise small intersections. I
• Two-Level Polytopes with a Prescribed Facet
• Bounds on the number of 2-level polytopes, cones, and configurations
• 2L_enum
• Complex psd-minimal polytopes in dimensions two and three
• Binary scalar products
• Octopuses in the Boolean cube: families with pairwise small intersections. II
• On Vertices and Facets of Combinatorial 2-Level Polytopes
• Four-dimensional polytopes of minimum positive semidefinite rank
• Enumeration of 2-level polytopes
• Properties of combinatorial optimization problems over polyhedral-spherical sets
• Extended formulations for matroid polytopes through randomized protocols

Uses Software

• nauty
• polymake
• Boost C++ Libraries
• CRAN
• Traces
• Boost
• uBLAS
• 01poly
• CPAN
• birkhoff faces
• 2L_enum

This page was built for publication: Enumeration of 2-level polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1741129)