I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating this into an integer program and then solving it by the usual branch & bound method?


The professor teaching the course has told me to think about it, but I have no clue. Any suggessions?



Gröbner basis via integer programming
ILP is $NP$-complete, while computing a Grobner Basis is $EXPSPACE$-complete. As one has the containments $NP\subseteq PSPACE\subsetneq EXPSPACE$, one should expect that you can reduce ILP to computing a Grobner basis, but not the other direction.


