Hoekstra, M. (2013) Grobner bases and Graver bases used in integer programming. Master's Thesis / Essay, Mathematics.

Text
Masterscriptie.pdf  Published Version Download (762kB)  Preview 

Text
HoekstraMAkkoordTop.pdf  Other Restricted to Repository staff only Download (25kB) 
Abstract
This thesis combines topics from the field of Algebra and the field of Optimization. It will be discussed how two different algebraic concepts can be used to solve integer linear minimization problems. The first concept studied is the (reduced) Groebner basis of a monomial ideal in the polynomial ring over a field k. We will see how we can transform a linear system Ax=b to a system of polynomial equations, so that Groebner bases can be used to solve it. The second topic is the Graver basis, introduced by Jack E. Graver in 1975. An integer linear minimization programming problem where all variables are bounded from below and above is NPhard and hence presumably cannot be solved in polynomial time. However, given the Graver basis Gr(A) of the toric ideal defined by the matrix A, it can be solved in polynomial time. Moreover, Gr(A) can be used to solve bounded separable convex integer minimization problems. We implemented algorithms by Adams and Loustaunau (1994) and by Onn (2010), using Groebner and Graver basis respectively, in Maple. The results will be displayed and discussed.
Item Type:  Thesis (Master's Thesis / Essay) 

Degree programme:  Mathematics 
Thesis type:  Master's Thesis / Essay 
Language:  English 
Date Deposited:  15 Feb 2018 07:54 
Last Modified:  15 Feb 2018 07:54 
URI:  http://fse.studenttheses.ub.rug.nl/id/eprint/11323 
Actions (login required)
View Item 