How to Find the Convex Hull of All Integer Points in a Polyhedron?

2020/10/25 by Sergey O. Semenov, Semenov, S. O., Nikolai Yu. Zolotykh +1
Computer Science · Engineering · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2010.13147

openalex publication_date 2020/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a cut-based algorithm for finding all vertices and all facets of the convex hull of all integer points of a polyhedron defined by a system of linear inequalities. Our algorithm DDM Cuts is based on the Gomory cuts and the dynamic version of the double description method. We describe the computer implementation of the algorithm and present the results of computational experiments comparing our algorithm with a naive one.

Related

• Computing convex hulls and counting integer points with polymake
• An integer programming formulation using convex polygons for the convex\n partition problem
• Enumerating integer points in polytopes with bounded subdeterminants
• Mathematical Programming Algorithms for Convex Hull Approximation with a Hyperplane Budget
• A New Algorithm for Computing Integer Hulls of 2D Polyhedral Sets