swMATH ID: 31753
Software Authors: Bohn, Adam; Faenza, Yuri; Fiorini, Samuel; Fisikopoulos, Vissarion; Macchia, Marco; Pashkovich, Kanstantsin
Description: Enumeration of 2-level polytopes. A (convex) polytope P is said to be 2-level if for each hyperplane H that supports a facet of P, the vertices of P can be covered with H and exactly one other translate of H. 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 𝑑⩽7 . Our approach is inductive: for each fixed (π‘‘βˆ’1) -dimensional 2-level polytope 𝑃0 , we enumerate all d-dimensional 2-level polytopes P that have 𝑃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 𝑃0 , we obtain all 2-level polytopes in dimension d.
Homepage: https://rd.springer.com/article/10.1007%2Fs12532-018-0145-6
Source Code:  https://zenodo.org/record/1405386#.XjvPDMZKjmI
Keywords: polyhedral computation; polyhedral combinatorics; optimization; formal concept analysis; algorithm engineering
Related Software: 01poly; Macaulay2; SageMath; birkhoff faces; polymake; SlackIdeals; Maple; uBLAS; Boost; Traces; Boost C++ Libraries; nauty; CPAN; CRAN
Cited in: 12 Documents

Citations by Year