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?

  • 2
    $\begingroup$ The worst case complexity of Groebner bases is really bad: something like $d^{2^n}$ where $n$ is the number of variables and $d$ the maximum total degree of the inputs. That doesn't prevent this approach from being useful in particular instances. $\endgroup$ – Robert Israel Aug 7 '16 at 17:47

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).

| cite | improve this answer | |
  • $\begingroup$ can someone let me know links or papers about the complexity of building a grobner basis (i am interested in the case of binomials which must be easier) ? $\endgroup$ – teller Sep 19 '16 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.