SOLVING INTEGER OR MIXED LINEAR-PROGRAMS USING A HERMITE NORMAL-FORM COMPUTATION

Integer Linear Programming (ILP) is especially hard when the solutions of its integral relaxation are far from its true solutions. Such a si tuation is in some way related to the geometrical properties of the as sociated polyedron. We present here an approach for ILP which is based upon a systematical use of specific changes of variables. These chang es of variables involve Hermite Normal Form decompositions and nl[ow t he implementation of specific cutting plane methods and branch and bou nd methods. We describe and test these methods, and conclude this work by introducing several open problems.