Solution of integer or mixed linear programs using the Hermite normal form

Solution of integer or mixed linear programs using the Hermite normal form

0.00 Avg rating0 Votes
Article ID: iaor20001802
Country: France
Volume: 31
Issue: 4
Start Page Number: 399
End Page Number: 427
Publication Date: Jan 1997
Journal: RAIRO Operations Research
Authors: ,
Abstract:

Integer Linear Programming (ILP) is especially hard when the solutions of its integral relaxation are far from its true solutions. Such a situation is in some way related to the geometrical properties of the associated polyhedron. We present here an approach for ILP which is based upon a systematical use of specific changes of variables. These changes of variables involve Hermite Normal Form decompositions and allow the implementation of specific cutting plane methods and branch and bound methods. We describe and test these methods, and conclude this work by introducing several open problems.

Reviews

Required fields are marked *. Your email address will not be published.