INTEGER PROGRAMMING AND GRÖBNER BASES
DOI:
https://doi.org/10.18690/jet.8.2.43-58.2015Keywords:
Integer linear programming, polynomial rings, Gröbner bases, nonlinear polynomial sys- tems of equationsAbstract
An approach to solve the integer linear programming problem (IP) using the Gröbner bases theory is presented. We consider the basics of commutative algebra on polynomial rings and their ideals and the multidivision algorithm. Gröbner bases were introduced to solve nonlinear polynomial systems of equations; therefore, we first present the generalization of the Gauss elimination method. In order to solve a general IP a special ideal depending on the coefficients of the system and number of constraints in the IP has to be constructed. Finally, a Gröbner basis of this ideal, which yields the solution to IP, must be sought.
Downloads
References
W.W. Adams, P. Loustaunau: An introduction to Gröbner bases: Graduate Studies in Mathematics. Vol. 3, Providence, RI: American Mathematical Society, 1994
B. Buchberger: Ein Algorithmus zum Auffinden der Basiselemente des Restlasseringes nach einem nulldimensionalen Polynomideal. PhD Thesis, Mathematical Institute, University of Innsbruck, Austria, 1965
P. Conti, C. Traverso: Buchberger algorithm and integer programming, Applied algebra, falgebraic algorithms and error-correcting codes (New Orleans, LA, 1991), Lecture Notes in Comput. Sci. vol. 539, p. 130-139, 1991
D. Cox, J. Little, D. O'Shea: Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geomety and Commutative Algebra. New York: Springer, 2007
S.R. Czapor: Gröbner basis methods for solving algebraic equations. Ph.D Thesis. University of Waterloo, Canada, 1988
V.F. Edneral, A. Mahdi, V.G. Romanovski, D.S. Shafer: The center problem on a center manifold in R3, Nonlinear Anal., vol. 75, p. 2614-2622, 2012
B. Ferčec, M. Mencinger: Isochronicity of centers at a center manifold, AIP conference pro- ceedings, 1468. Melville, N.Y.: American Institute of Physics, p. 148-157, 2012
S. Flory, E. Michel: Integer Programming with Gröbner basis. (http://www.iwr.uni-heidel-berg.de/groups/amj/People/Eberhard.Michel/Documents/Else/DiscreteOptimization.pdf)
G.M. Greuel, G. Pfister, H. Schönemann: Singular 3.0. A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, University of Kaiserslautern, 2005; http://www.singular.uni-kl.de.
V.G. Romanovski, M. Mencinger, B. Ferčec: Investigation of center manifolds of 3-dim systems using computer algebra. Program. comput. softw., vol. 39, no. 2, p. 67-73, 2013
V.G. Romanovski, D.S. Shafer: The center and cyclicity problems: A computational algebra approach. Boston: Birkhauser Verlag, 2009
C. Wendler: Groebner Bases with an Application to Integer Programming; (http://documents.kenyon.edu/math/CWendler.pdf), 2004
