Enumeration and unimodular equivalence of empty delta-modular simplices

DOI10.1007/978-3-031-35305-5_8MaRDI QIDQ6134052zbMATH OpenFDO

Authors

Publication date 21 August 2023

Published in Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

unimodular equivalenceenumeration algorithmlattice simplexempty simplexbounded sub-determinantsdelta-modular matrix

Mathematics Subject Classification ID

Integer programming (90C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Canonical forms, reductions, classification (15A21) Lattices and convex bodies (number-theoretic aspects) (11H06)

Abstract: Consider a class of simplices defined by systems $Axleqb$ of linear inequalities with $Delta$-modular matrices. A matrix is called $Delta$-modular, if all its rank-order sub-determinants are bounded by $Delta$ in an absolute value. In our work we call a simplex $Delta$-modular, if it can be defined by a system $Axleqb$ with a $Delta$-modular matrix $A$. And we call a simplex empty, if it contains no points with integer coordinates. In literature, a simplex is called lattice-simplex, if all its vertices have integer coordinates. And a lattice-simplex called empty, if it contains no points with integer coordinates excluding its vertices. Recently, assuming that $Delta$ is fixed, it was shown that the number of $Delta$-modular empty simplices modulo the unimodular equivalence relation is bounded by a polynomial on dimension. We show that the analogous fact holds for the class of $Delta$-modular empty lattice-simplices. As the main result, assuming again that the value of the parameter $Delta$ is fixed, we show that all unimodular equivalence classes of simplices of the both types can be enumerated by a polynomial-time algorithm. As the secondary result, we show the existence of a polynomial-time algorithm for the problem to check the unimodular equivalence relation for a given pair of $Delta$-modular, not necessarily empty, simplices.

Recommendations

• On lattice point counting in \(\varDelta\)-modular polyhedra
• A faster algorithm for counting the integer points number in \(\Delta \)-modular polyhedra
• On the Column Number and Forbidden Submatrices for \(\Delta\)-Modular Matrices
• scientific article; zbMATH DE number 1342145
• On the maximal number of columns of a \(\varDelta \)-modular matrix

Cites work

• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 1254301 (Why is no real title available?)
• scientific article; zbMATH DE number 1342145 (Why is no real title available?)
• scientific article; zbMATH DE number 1405493 (Why is no real title available?)
• scientific article; zbMATH DE number 5165610 (Why is no real title available?)
• scientific article; zbMATH DE number 3046578 (Why is no real title available?)
• A geometric approach to cut-generating functions
• A polynomial algorithm for minimizing discrete convic functions in fixed dimension
• A strong dual for conic mixed-integer programs
• Algebraic and geometric ideas in the theory of discrete optimization
• Classification of empty lattice 4-simplices of width larger than 2
• Computing parametric rational generating functions with a primal Barvinok algorithm
• Computing the Continuous Discretely
• Constructing lattice-free gradient polyhedra in dimension two
• Constructive characterizations of the value function of a mixed-integer program. II
• Constructive characterizations of the value-function of a mixed-integer program. I
• Covering minima and lattice-point-free convex bodies
• Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
• Duality for mixed-integer convex minimization
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• FPT-algorithm for computing the width of a simplex given by a convex hull
• FPT-algorithms for some problems related to integer programming
• Fast integer programming in fixed dimension
• Hollow polytopes of large width
• Improving the Cook et al. proximity bound given integral valued constraints
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
• Inequalities from Two Rows of a Simplex Tableau
• Integer Programming with a Fixed Number of Variables
• Integer conic function minimization based on the comparison oracle
• Integer points in polyhedra
• Integer programming duality: Price functions and sensitivity analysis
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Lattice Tetrahedra
• Lattice-free simplices with lattice width \(2d - o(d)\)
• Linear and Integer Programming vs Linear Integration and Counting
• Minimal valid inequalities for integer constraints
• New bounds in some transference theorems in the geometry of numbers
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• On Four-Dimensional Terminal Quotient Singularities
• On Lovász' lattice reduction and the nearest lattice point problem
• On integer programming with bounded determinants
• On lattice width of lattice-free polyhedra and height of Hilbert bases
• On the complexity of quasiconvex integer minimization problem
• On the maximal width of empty lattice simplices
• On the width of lattice-free simplices
• Optimality certificates for convex minimization and Helly numbers
• Quotient Singularities, Integer Ratios of Factorials, and the Riemann Hypothesis
• Relaxations of mixed integer sets from lattice-free polyhedra
• Short rational generating functions for lattice point problems
• Terminal Quotient Singularities in Dimensions Three and Four
• The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
• The b-hull of an integer program
• The structure of simple sets in \(\mathbb Z^3\)
• The width and integer optimization on simplices with bounded minors of the constraint matrices

Cited in

(1)

• A faster algorithm for counting the integer points number in \(\Delta \)-modular polyhedra

This page was built for publication: Enumeration and unimodular equivalence of empty delta-modular simplices

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