Computing the integer hull of convex polyhedral sets
A convex polyhedron is a subset \(P\subset \mathbb{Q}^d\) such that \(P=\{\mathbf{x}\in\mathbb{Q}^d \ | \ A\mathbf{x}\le b \}\) where \(A\in \mathbb{Q}^{m\times d}\), \(b\in \mathbb{Q}^m\) and \(m\) and \(d\) are positive integers. The smallness convex polyhedron containing the integer points of \(P\) is called the integer hull of \(P\) and is denoted by \(P_I\). The aim of this paper is to describe a new algorithm for computing \(P_I\). The authors also provide two implementations of this algorithm in Maple and in the C programming language. The efficiency of the proposed algorithm compared to the related function in Normaliz has been discussed via a set of examples. For the entire collection see [Zbl 07573785].
- ``Outline of an algorithm for integer solutions to linear programs and ``An algorithm for the mixed integer problem
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- An Automatic Method of Solving Discrete Programming Problems
- Computing convex hulls and counting integer points with \texttt{polymake}
- Computing the face lattice of a polytope from its vertex-facet incidences
- Computing the integer points of a polyhedron. I: Algorithm
- Counting integer points in parametric polytopes using Barvinok's rational functions
- Edmonds polytopes and a hierarchy of combinatorial problems
- Effective lattice point counting in rational convex polytopes
- scientific article; zbMATH DE number 435565 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- Normaliz: Algorithms for affine monoids and rational cones
- On Cutting Planes
- On integer points in polyhedra
- On the pseudo-periodicity of the integer hull of parametric convex polygons
- The quickhull algorithm for convex hulls
- The vertices of the knapsack polytope
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- An algorithm for determining the minimal convex subset that contains all the integer points of a convex polyhedral set
- Finding the exact volume of a polyhedron.
- Computing the integer points of a polyhedron. I: Algorithm
- Computing the integer points of a polyhedron. II: Complexity estimates
- The randomized integer convex hull
- Note on the complexity of the mixed-integer hull of a polyhedron
- An algorithm for the construction of convex hulls in simple integer recourse programming
- How to find the convex hull of all integer points in a polyhedron?
- A new algorithm to find all vertices of a polytope
- Computing convex hulls and counting integer points with \texttt{polymake}
- Recursive Calculation of Relative Convex Hulls
- The integer hull of a convex rational polytope
- Computing Two-Dimensional Integer Hulls
- EFFICIENT ENUMERATION OF GRID POINTS IN A CONVEX POLYGON AND ITS APPLICATION TO INTEGER PROGRAMMING
- scientific article; zbMATH DE number 1960412 (Why is no real title available?)
- Transformations and consecutivities on a king for computational applications
- Facial Structure and Representation of Integer Hulls of Convex Sets
- Fully Bounded Polyhedral Analysis of Integers with Wrapping
- Towards the computation of the convex hull of a configuration from its corresponding separating matrix
- The integer hull of a convex rational polytope
Uses Software
This page was built for publication: Computing the integer hull of convex polyhedral sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2109987)
