title: Minimised geometric Buchberger algorithm for integer programming
abstract: Recently, various algebraic integer programming (IP) solvers have been proposed based on the theory of Grobner bases. The main difficulty of these solvers is the size of the Grobner bases generated. In algorithms proposed so far, large Grobner bases are generated by either introducing additional variables or by considering the generic IP problem IP/sub A,C/. Some improvements have been proposed such as Hosten and Sturmfels' method (GRIN) designed to avoid additional variables and Thomas' truncated Grobner basis method which computes the reduced Grobner basis for a specific IP problem IP/sub A,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 Grobner basis method to compute the fundamental segments of an IP problem IP/sub A,C/ directly in its original space and also the truncated Grobner basis for a specific IP problem IP/sub A,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
keyphrases: minimised geometric Buchberger algorithm geometric Buchberger algorithm algebraic integer programming Grobner bases truncated Grobner basis method reduced Grobner basis fundamental segments truncated geometric Buchberger algorithm performance improvement GRIN algorithm