Article ID: | iaor20041799 |
Country: | Germany |
Volume: | 96 |
Issue: | 2 |
Start Page Number: | 205 |
End Page Number: | 246 |
Publication Date: | Jan 2003 |
Journal: | Mathematical Programming |
Authors: | Weismantel R., Haus U.-U., Kppe M. |
This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer problems from the MIPLIB demonstrate the practical power of the method.