CELOŠTEVILSKO PROGRAMIRANJE IN GRÖBNERJEVE BAZE
Povzetek
V članku je podan pristop k reševanju celoštevilskega linearnega programiranja (IP) z uporabo teorije Gröbnerjevih baz. Obravnavamo osnovne elemente komutativne algebre na polinomskih kolobarjih, njihove ideale in algoritem multi-deljenja. Gröbnerjeve baze so bile vpeljane za reševanje nelinearnih polinomskih sistemov enačb, zato je v članku najprej predstavljen primer posplošitve Gaussove eliminacijske metode. Pri reševanju splošnega IP konstruiramo poseben ideal, ki je odvisen od koeficientov sistema in števila enačb v IP. Končno rešitev dobimo s pomočjo Gröbnerjeve baze tega ideala.
Prenosi
Literatura
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
