# Groebner basis

### From Glossary

This arises in parametric
integer (linear) programming, varying the right-hand side .
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, , called a
*test set*, such that the objective function improves along those
directions. To elaborate, suppose we have

where and have integer elements. Let and (i.e., is feasible and bounded). A Gröbner basis for , holding fixed, is a set, , for which the following conditions hold:

- .
- (for minimization).
- For and , there exists such that.

Condition 1 says that if , and condition 2 says . Therefore, if is any feasible solution to either is optimal for a particular right-hand side , or condition 3 ensures there is an improvement by adding some vector, .

Here is a numerical example.