How to find the convex hull of all integer points in a polyhedron?

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, DDMCuts , is based on the Gomory cuts and the dynamic version of the double description method. We describe the...

Full description

Saved in:
Bibliographic Details
Published in:Optimization letters 2022-09, Vol.16 (7), p.2177-2189
Main Authors: Semenov, S. O., Zolotykh, N. Yu
Format: Article
Language:English
Subjects:
Computational Intelligence
Mathematics
Mathematics and Statistics
Numerical and Computational Physics
Operations Research/Decision Theory
Optimization
Original Paper
Simulation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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, DDMCuts , 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 and an algorithm implemented in Normaliz.
ISSN:1862-4472
1862-4480
DOI:10.1007/s11590-021-01729-w