isFeasiblePoint(A, b, X)
Fix a matrix $A \in \mathbb Z^{m \times n}$ and integer linear program in standard form with constraints $Ax = b$. The following is a characterization of when the vector $x \in \mathbb Z_{\ge 0}^n$ satisfies $Ax = b$, in which case we say that it is feasible. This condition is exactly [CLO, Chapter 8, Proposition 1.6].
Proposition. Let $A \in \mathbb Z^{m \times n}$ and consider the feasible region $Ax = b$. Define a homomorphism of rings $\varphi:k[w_1, \ldots, w_n] \to k[z_1, \ldots, z_m]$, where $k$ is any field, by $$\varphi: w_j \mapsto \prod_{i=1}^m z_i^{A_{i, j}} \quad \text{for all } j = 1, \ldots, n.$$ Then, a vector $x \in \mathbb Z_{\ge 0}^n$ satisfies $Ax = b$ if and only if $\varphi(w^x) = z^b$.
|
|
|
|
[CLO] David A. Cox, John Little, and Donal O'Shea. Using Algebraic Geometry. Second edition. Graduate Texts in Mathematics, 185. Springer, New York, 2005.
Assumes the program is in standard form.
The object isFeasiblePoint 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:387:0.