I enjoyed reading different papers about using Groebner basis to solve integer programming.
Is there any literature about the complexity and/or comparison with other (more classical) methods like gomory, branch and bound?
I enjoyed reading different papers about using Groebner basis to solve integer programming.
Is there any literature about the complexity and/or comparison with other (more classical) methods like gomory, branch and bound?
For a typical Integer Programming problem, assume it has the form: $\min {c*z} ~ \text{ s.t.} ~ A*z=b$
If the matrix A has large enough size, i.e. 10 *20, the method to calculate the Groebner basis take a huge amount of time and the number of vectors in the basis is also large. Hence the corresponding Groebner test set will not be effective compared to other cutting plane or branch and bound (checking using IBM CPLEX software)
However, when the matrix A has a smaller size, finding the Groebner basis and Groebner test set by using Project and Lift method (4ti2 package) is quite good and competitive to other traditional methods.
You can check out the paper of S. Hosten and B. Sturmfels. GRIN: An implementation of Gröbner bases for integer programming (1995).