Groebner basis

From Glossary

Jump to: navigation, search

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

\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 thatLaTeX:  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.

Personal tools