A primal all-integer algorithm based on irreducible solutions

A primal all-integer algorithm based on irreducible solutions

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

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