solveILP(A, b, c)
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].
|
|
|
|
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.
[CLO] David A. Cox, John Little, and Donal O'Shea. Using Algebraic Geometry. Second edition. Graduate Texts in Mathematics, 185. Springer, New York, 2005.
This method produces only one solution (that is, a feasible point that attains the minimum), even when multiple solutions exist.
The object solveILP is a method function with options.
The source of this document is in /build/reproducible-path/macaulay2-1.25.05+ds/M2/Macaulay2/packages/IntegerProgramming.m2:461:0.