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

solveILP -- solve an integer linear program in standard form

Description

Consider the integer linear program $$\text{minimize } c^T x \quad\text{subject to } Ax = b \text{ and } x \in \mathbb Z_{\ge 0}^n,$$ where $A$ is an $m \times n$ integer-valued matrix and $b \in \mathbb Z^m$, $c \in \mathbb Z^n$. Suppose that every entry in $A$ and $b$ is nonnegative. A solution to the problem is given by [CLO, Chapter 8, Theorem 1.11], which we now detail.

We work in the polynomial ring $R = k[z_1, \ldots, z_m, w_1, \ldots, w_n]$, where $k$ is a field, equipped with an monomial order adapted to the program. For each $j = 1, \ldots, n$, let $f_j = \prod_{i=1}^m z_i^{A_{i,j}}$ and let $\mathcal G$ be a Gröbner basis for $\langle f_1 - w_1 , \ldots, f_n - w_n \rangle$ in $R$. Consider the remainder on division $\overline f^{\mathcal G}$ of $f = z^b$. The result of [CLO, Chapter 8, Proposition 1.8] guarantees that $\overline f^{\mathcal G}$ is a monomial. Moreover, the program is feasible if $\overline f^{\mathcal G}$ involves only the variables $w_1, \ldots, w_n$ and, in this case, a solution is given by the exponent vector of $\overline f^{\mathcal G}$.

The following example is from [CLO, Chapter 8, Section 1].

i1 : A = matrix{{4, 5, 1, 0}, {2, 3, 0, 1}}

o1 = | 4 5 1 0 |
     | 2 3 0 1 |

              2       4
o1 : Matrix ZZ  <-- ZZ
i2 : b = {37, 20}

o2 = {37, 20}

o2 : List
i3 : c = {-11, -15, 0, 0}

o3 = {-11, -15, 0, 0}

o3 : List
i4 : solveILP(A, b, c)

o4 = {4, 4, 1, 0}

o4 : List

Alternately, one can write the program not in standard form, see IsInStandardForm.

Remark. Maximization and minimization (integer) linear programs are equivalent by multiplying objective functions by $-1$. This package treats every problem as a minimization problem and leaves the multiplication for maximiation problems to the user.

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.

Caveat

This method produces only one solution (that is, a feasible point that attains the minimum), even when multiple solutions exist.

See also

Ways to use solveILP:

  • solveILP(Matrix,List,List)
  • solveILP(Matrix,List,Matrix)
  • solveILP(Matrix,Matrix,List)
  • solveILP(Matrix,Matrix,Matrix)

For the programmer

The object solveILP is a method function with options.


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