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

isFeasiblePoint -- whether a point is feasible to an integer linear program

Description

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$.

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

o1 = | 1 2 |
     | 3 4 |

              2       2
o1 : Matrix ZZ  <-- ZZ
i2 : b = matrix{{4}, {10}}

o2 = | 4  |
     | 10 |

              2       1
o2 : Matrix ZZ  <-- ZZ
i3 : isFeasiblePoint(A, b, {1, 1})

o3 = false
i4 : isFeasiblePoint(A, b, matrix{{2}, {1}})

o4 = true

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

Assumes the program is in standard form.

See also

Ways to use isFeasiblePoint:

  • isFeasiblePoint(Matrix,List,List)
  • isFeasiblePoint(Matrix,List,Matrix)
  • isFeasiblePoint(Matrix,Matrix,List)
  • isFeasiblePoint(Matrix,Matrix,Matrix)

For the programmer

The object isFeasiblePoint is a method function with options.


The source of this document is in /build/reproducible-path/macaulay2-1.25.06+ds/M2/Macaulay2/packages/IntegerProgramming.m2:387:0.