INTEGER PROGRAMMING AND GRÖBNER BASES - Ferčec, Brigita; Mencinger, Matej (Journal of Energy Technology, 2024)
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.