No label defined (Q4356874)

This paper discusses the ways Hermite normal form decompositions may be used in order to solve integer linear programs. First, we notice that if a given square matrix defines a fractional vertex of some polyhedron, then setting this matrix in Hermite normal form means performing some change of variables which preserves the integrality constraint, provides some local regularization of the polyhedron in the neighbourhood of this vertex, and makes appear an integral ``candidate'' vector. It induces the possible implementation of cutting plane methods and of branch and bound methods. Next we combine these methods with a stochastic control allowing the current vertex to jump throughout the polyhedron, in search of the best areas for cutting it. We end by discussing the impact of the thickness of the constraint polyhedron on the behavior of descent algorithms for ILP, and tried to provide methods for increasing this thickness through well-chosen variable changes. For the entire collection see [Zbl 0868.00069].