Minimised geometric Buchberger algorithm for integer programming

Minimised geometric Buchberger algorithm for integer programming

0.00 Avg rating0 Votes
Article ID: iaor2003379
Country: Netherlands
Volume: 108
Issue: 1
Start Page Number: 87
End Page Number: 109
Publication Date: Nov 2001
Journal: Annals of Operations Research
Authors: , , ,
Abstract:

Recently, various algebraic integer programming (IP) solvers have been proposed based on the theory of Gröbner bases. The main difficulty of these solvers is the size of the Gröbner bases generated. In algorithms proposed so far, large Gröbner bases are generated by either introducing additional variables or by considering the generic IP problem IPA.C. Some improvements have been proposed such as Hosten and Sturmfels' method (GRIN) designed to avoid additional variables and Thomas' truncated Gröbner basis method which computes the reduced Gröbner basis for a specific IP problem IPA.C(b) (rather than its generalisation IPA.C). In this paper we propose a new algebraic algorithm for solving IP problems. The new algorithm, called Minimised Geometric Buchberger Algorithm, combines Hosten and Sturmfels' GRIN and Thomas' truncated Gröbner basis method to compute the fundamental segments of an IP problem IPA.C directly in its original space and also the truncated Gröbner basis for a specific IP problem IPA.C(b). We have carried out experiments to compare this algorithm with others such as the geometric Buchberger algorithm, the truncated geometric Buchberger algorithm and the algorithm in GRIN. These experiments show that the new algorithm offers significant performance improvement.

Reviews

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