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: | Quilliot A., Maublanc J. |
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.