Grobner bases and Graver bases used in integer programming

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

Preview	Text Masterscriptie.pdf - Published Version Download (762kB) | Preview
	Text HoekstraMAkkoordTop.pdf - Other Restricted to Registered users 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 NP-hard 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:	https://fse.studenttheses.ub.rug.nl/id/eprint/11323

Actions (login required)

View Item