Macaulay2 » Documentation
Packages » IntegerProgramming » adaptedMonomialOrder
next | previous | forward | backward | up | index | toc

adaptedMonomialOrder -- constructs a ring with monomial order adapted to an integer program

Description

Solving integer linear programs using Gröbner bases relies on constructing a monomial order that is adapted to the program at hand. This method returns a ring equipped with such an order.

Definition. Fix a matrix $A \in \mathbb Z^{m \times n}$ and vectors $b \in \mathbb Z^m$, $c \in \mathbb Z^n$. Consider the integer linear program in standard form: $$\text{minimize } c^Tx \quad \text{subject to } Ax = b \text{ and } x \in \mathbb Z_{\ge 0}^n.$$ Let $\varphi$ be as in isFeasiblePoint. A monomial order $<$ on $k[z_1, \ldots, z_m, w_1, \ldots, w_n]$ is adapted to the program if both of the following hold:

1. (Elimination) $z_i > w^\alpha$ for all $\alpha \in \mathbb Z_{\ge 0}^n$, for all $i = 1, \ldots, m$;

2. (Compatibility with the program) if $c^T \alpha > c^T \beta$ and $\varphi(w^\alpha) = \varphi(w^\beta)$, then $w^\alpha > w^\beta$.

Construction. We outline here the construction of such an order, following Exercise 7 in [CLO, Chapter 8, Section 1].

First, suppose that the vector $c$ defining the objective function contains only nonnegative entries. Define a weight order on the variables $w_1, \ldots, w_m$ by giving weight $c_j$ to $w_j$. We extend this to an adapted monomial order on $k[z_1, \ldots, z_n, w_1, \ldots, w_m]$ by treating each $z_i$ as lexicographically larger than every $w_j$.

Assume now that $c$ is not nonnegative. For each $j = 1, \ldots, n$, define $d_j = \sum_{i=1}^m A_{i,j}$. (Note that $d_j > 0$ for otherwise the constraints in the linear program do not depend on $x_j$.) Equip $k[z_1, \ldots, z_m, w_1, \ldots, w_m]$ with nonstandard grading: $\deg(z_i) = 1$ for all $i$ and $\deg(w_j) = d_j$ for all $j$. Now for the term order, pick $\mu$ such that the vector $(c_1, \ldots, c_n) + \mu(d_1, \ldots, d_n)$ contains only nonnnegative entries. This gives rise to a weight order on $k[w_1, \ldots, w_n]$ which satisfies condition (2) above. We extend this to an adapted monomial order on $k[z_1, \ldots, z_n, w_1, \ldots, w_m]$ by again treating each $z_i$ as lexicographically larger than every $w_j$.

References

[CLO] David A. Cox, John Little, and Donal O'Shea. Using Algebraic Geometry. Second edition. Graduate Texts in Mathematics, 185. Springer, New York, 2005.

See also

Ways to use adaptedMonomialOrder:

  • adaptedMonomialOrder(Matrix,List)
  • adaptedMonomialOrder(Matrix,Matrix)

For the programmer

The object adaptedMonomialOrder is a method function with options.


The source of this document is in IntegerProgramming.m2:332:0.