# Groebner basis

This arises in parametric integer (linear) programming, varying the right-hand side $LaTeX: (b)$. A precise definition is involved, stemming from ideal theory in abstract algebra, and there are many other applications outside of integer programming. In the context of ILP, a Gröbner basis is a minimal set of change directions, $LaTeX: \{h^1, h^2, \ldots, h^k\}$, called a test set, such that the objective function improves along those directions. To elaborate, suppose we have

$LaTeX: \mbox{ILP}(b): \min c^Tx : Ax = b, \; x \in \mathbb{Z}^n, \; x \ge 0,$

where $LaTeX: A$ and $LaTeX: b$ have integer elements. Let $LaTeX: X^*(b) = \arg\!\min \{c^Tx : Ax = b, \;x \in \mathbb{Z}^n, \; x \ge 0\}$ and $LaTeX: B = \{b: X^*(b) \neq \emptyset\}$ (i.e., $LaTeX: \mbox{ILP}(b)$ is feasible and bounded). A Gröbner basis for $LaTeX: A$, holding $LaTeX: c$ fixed, is a set, $LaTeX: G_c = \{h^i\}$, for which the following conditions hold:

1. $LaTeX: Ah^i = 0$.
2. $LaTeX: c^T h^i < 0$ (for minimization).
3. For $LaTeX: b \in B$ and $LaTeX: x \not\in X^*(b)$, there exists $LaTeX: h^i \in G_c$ such that$LaTeX: x + h^i \ge 0$.

Condition 1 says that $LaTeX: A(x+h^i)=b$ if $LaTeX: Ax=b$, and condition 2 says $LaTeX: c^T(x+h^i) < c^Tx$. Therefore, if $LaTeX: x$ is any feasible solution to $LaTeX: \mbox{ILP}(b),$ either $LaTeX: x$ is optimal for a particular right-hand side $LaTeX: b$, or condition 3 ensures there is an improvement by adding some vector, $LaTeX: h^i \in G_c$.

Here is a numerical example.