This is IntegerProgramming.info, produced by Macaulay2, version 1.25.11

IntegerProgramming -- solving integer programs with Gröbner bases
*****************************************************************

Description
===========

Integer linear programming concerns optimization problems of the form $$
\begin{matrix} \text{minimize} & c^T x \\ \text{such that} & Ax = b \\
\text{and} & x \in \mathbb Z^n_{\ge 0} \end{matrix} $$ for some $m \times n$
matrix $A$ and vectors $b$ and $c$. In general, solving integer linear programs
is an NP-hard problem. Work from the early 1990s (see [CT, O, P]) developed
algorithms for solving integer linear programs using Gröbner bases.

The key to this approach is constructing a term order that is compatible with
the objective function of the program. We implement this in
adaptedMonomialOrder, which returns a ring equipped with
such a term order. This order is used in solveILP, to solve
integer programs.

Acknowledgement
===============

This package was developed as part of the graduate course Computational
Commutative Algebra and Algebraic Geometry during the Fields Institute's
Thematic Program in Commutative Algebra and Applications in Winter 2025. We
thank Mike Stillman, for his instruction of the course, and the organizers of
the thematic program: David Eisenbud, Elisa Gorla, Megumi Harada, Jenna
Rajchgot, Hal Schenck, and Adam Van Tuyl.

Cummings is partially supported by NSERC CGS-D 588999–2024 and a University of
Waterloo President's Graduate Scholarship.

References
==========

[CT] Pasqualina Conti and Carlo Traverso. Buchberger algorithm and integer
programming. Applied algebra, algebraic algorithms and error-correcting codes
(New Orleans, LA, 1991), 130–139, Lecture Notes in Comput. Sci., 539, Springer,
Berlin, 1991.

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

[O] François Ollivier . Canonical bases: relations with standard bases,
finiteness conditions and application to tame automorphisms. Effective methods
in algebraic geometry (Castiglioncello, 1990), 379–400, Progr. Math., 94,
Birkhäuser Boston, Boston, MA, 1991.

[P] Loïc Pottier . Minimal solutions of linear Diophantine systems: bounds and
algorithms. Rewriting techniques and applications (Como, 1991), 162–173,
Lecture Notes in Comput. Sci., 488, Springer , Berlin, 1991.

Author
======

  * Mike Cummings (see https://mikecummings.ca ) <mike.cummings@uwaterloo.ca>

Version
=======

This documentation describes version 0.1 of IntegerProgramming, released April
21, 2025.

Citation
========

If you have used this package in your research, please cite it as follows:

+-----------------------------------------------------------------------------+
|@misc{IntegerProgrammingSource,                                              |
|  title = {{IntegerProgramming: solving integer programs with Gröbner bases. |
|  author = {Mike Cummings},                                                  |
|  howpublished = {A \emph{Macaulay2} package available at                    |
|    \url{https://github.com/Macaulay2/M2/tree/stable/M2/Macaulay2/packages}} |
|}                                                                            |
|-----------------------------------------------------------------------------|
|Version~0.1}},                                                               |
+-----------------------------------------------------------------------------+

Exports
=======

  * Functions and commands
      * adaptedMonomialOrder -- constructs a ring
        with monomial order adapted to an integer program
      * isFeasiblePoint -- whether a point is feasible
        to an integer linear program
      * solveILP -- solve an integer linear program in
        standard form
      * toStandardForm -- converts an LP to standard
        form
  * Methods
      * "adaptedMonomialOrder(Matrix,List)" -- see adaptedMonomialOrder,
        -- constructs a ring with monomial order adapted
        to an integer program
      * "adaptedMonomialOrder(Matrix,Matrix)" -- see
        adaptedMonomialOrder, -- constructs a ring with
        monomial order adapted to an integer program
      * "isFeasiblePoint(Matrix,List,List)" -- see isFeasiblePoint,
        -- whether a point is feasible to an integer linear
        program
      * "isFeasiblePoint(Matrix,List,Matrix)" -- see isFeasiblePoint,
        -- whether a point is feasible to an integer linear
        program
      * "isFeasiblePoint(Matrix,Matrix,List)" -- see isFeasiblePoint,
        -- whether a point is feasible to an integer linear
        program
      * "isFeasiblePoint(Matrix,Matrix,Matrix)" -- see isFeasiblePoint,
        -- whether a point is feasible to an integer linear
        program
      * "solveILP(Matrix,List,List)" -- see solveILP, -- solve
        an integer linear program in standard form
      * "solveILP(Matrix,List,Matrix)" -- see solveILP, --
        solve an integer linear program in standard form
      * "solveILP(Matrix,Matrix,List)" -- see solveILP, --
        solve an integer linear program in standard form
      * "solveILP(Matrix,Matrix,Matrix)" -- see solveILP, --
        solve an integer linear program in standard form
      * "toStandardForm(Matrix)" -- see toStandardForm,
        -- converts an LP to standard form
      * "toStandardForm(Matrix,List)" -- see toStandardForm,
        -- converts an LP to standard form
      * "toStandardForm(Matrix,Matrix)" -- see toStandardForm,
        -- converts an LP to standard form
  * Symbols
      * Field -- field over which to define polynomial rings
      * IsInStandardForm -- specify whether the
        integer program is in standard form

For the programmer
==================

The object IntegerProgramming, is a package (Macaulay2Doc),
defined in IntegerProgramming.m2.

-------------------------------------------------------------------------------

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

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

  * Usage:
        adaptedMonomialOrder(A, c)
        adaptedMonomialOrder(A, c, Variables=>L)
  * Inputs:
      * A, a matrix (Macaulay2Doc), with nonnegative entries in
        ZZ (Macaulay2Doc),
      * c, a matrix (Macaulay2Doc), or a list (Macaulay2Doc),
        with entries in ZZ (Macaulay2Doc),
      * L, a list (Macaulay2Doc), optionally, a list of length two
        containing strings that we use as variable names in the ring
  * Optional inputs (Macaulay2Doc),:
      * Field, => ..., default value QQ, field over which to
        define polynomial rings
      * Variables => ..., default value {w, z}
  * Outputs:
      * a ring (Macaulay2Doc), equipped with a term order adapted
        to the given 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
========

  * solveILP -- solve an integer linear program in standard
    form
  * toStandardForm -- converts an LP to standard form
  * Field -- field over which to define polynomial rings

Ways to use adaptedMonomialOrder:
=================================

  * "adaptedMonomialOrder(Matrix,List)"
  * "adaptedMonomialOrder(Matrix,Matrix)"

For the programmer
==================

The object adaptedMonomialOrder, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

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

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

  * Usage:
        isFeasiblePoint(A, b, X)
  * Inputs:
      * A, a matrix (Macaulay2Doc), with nonnegative entries in
        ZZ (Macaulay2Doc),
      * b, a matrix (Macaulay2Doc), or a list (Macaulay2Doc),
        with nonnegative entries in ZZ (Macaulay2Doc),
      * X, a matrix (Macaulay2Doc), or a list (Macaulay2Doc),
        with nonnegative entries in ZZ (Macaulay2Doc),
  * Optional inputs (Macaulay2Doc),:
      * Field, => ..., default value QQ, field over which to
        define polynomial rings
  * Outputs:
      * a Boolean value (Macaulay2Doc),

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
========

  * solveILP -- solve an integer linear program in standard
    form
  * Field -- field over which to define polynomial rings
  * IsInStandardForm -- specify whether the integer
    program is in standard form

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 (Macaulay2Doc).

-------------------------------------------------------------------------------

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

solveILP -- solve an integer linear program in standard form
************************************************************

  * Usage:
        solveILP(A, b, c)
  * Inputs:
      * A, a matrix (Macaulay2Doc), with nonnegative entries in
        ZZ (Macaulay2Doc),
      * b, a matrix (Macaulay2Doc), or a list (Macaulay2Doc),
        with nonnegative entries in ZZ (Macaulay2Doc),
      * c, a matrix (Macaulay2Doc), or a list (Macaulay2Doc),
        with entrines in ZZ (Macaulay2Doc),
  * Optional inputs (Macaulay2Doc),:
      * Field, => ..., default value QQ, field over which to
        define polynomial rings
      * IsInStandardForm, => ..., default value true,
        specify whether the integer program is in standard form
  * Outputs:
      * a Boolean value (Macaulay2Doc), false if there is no
        solution, otherwise:
      * a matrix (Macaulay2Doc), or a list (Macaulay2Doc),
        a minimizer of the ILP, if a solution exists, of
        the same type as b

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
========

  * adaptedMonomialOrder -- constructs a ring with
    monomial order adapted to an integer program
  * isFeasiblePoint -- whether a point is feasible to
    an integer linear program
  * toStandardForm -- converts an LP to standard form
  * Field -- field over which to define polynomial rings
  * IsInStandardForm -- specify whether the integer
    program is in standard form

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 (Macaulay2Doc).

-------------------------------------------------------------------------------

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

toStandardForm -- converts an LP to standard form
*************************************************

  * Usage:
        toStandardForm A
        toStandardForm(A, c)
  * Inputs:
      * A, a matrix (Macaulay2Doc),
      * c, a matrix (Macaulay2Doc), or a list (Macaulay2Doc),
  * Outputs:
      * a matrix (Macaulay2Doc), or a sequence (Macaulay2Doc),
        the standard form corresponding to the given
        program

Description
===========

The standard form of an integer linear program is $$\text{minimize } c^T x
\quad\text{subject to } Ax = b \text{ and } x \in \mathbb Z_{\ge 0}^n.$$ An
integer linear program with constraints $Bx \le b$ is equivalent to one in
standard form in the following way: One constraint $B_{j,1}x_1 + \cdots +
B_{j,r}x_r \le d_j$ in this system is equivalent to the pair of constraints
$B_{j,1}x_1 + \cdots + B_{j, r}x_r + y_j = d_j$ and $y_j \ge 0$.

Hence we rewrite the constrains $Bx \le b$ as $Ax = b$ by introducing slack
variables $y_j$ and concatenating (Macaulay2Doc), a copy of the
identity matrix A = B|I of the appropriate size. (Note that we abuse notation
here and write $x$ for both the vector of the given program and the vector that
includes the slack variables $y_j$.)

This equivalence does not change the objective function; we pad $c$ with a zero
for each slack variable introduced.

+-------------------------------+
|i1 : A = matrix{{1, 2}, {3, 4}}|
|                               |
|o1 = | 1 2 |                   |
|     | 3 4 |                   |
|                               |
|              2       2        |
|o1 : Matrix ZZ  <-- ZZ         |
+-------------------------------+
|i2 : c = matrix{{5}, {6}}      |
|                               |
|o2 = | 5 |                     |
|     | 6 |                     |
|                               |
|              2       1        |
|o2 : Matrix ZZ  <-- ZZ         |
+-------------------------------+
|i3 : toStandardForm(A, c)      |
|                               |
|o3 = (| 1 2 1 0 |, | 5 |)      |
|      | 3 4 0 1 |  | 6 |       |
|                   | 0 |       |
|                   | 0 |       |
|                               |
|o3 : Sequence                  |
+-------------------------------+

See also
========

  * adaptedMonomialOrder -- constructs a ring with
    monomial order adapted to an integer program
  * solveILP -- solve an integer linear program in standard
    form

Ways to use toStandardForm:
===========================

  * "toStandardForm(Matrix)"
  * "toStandardForm(Matrix,List)"
  * "toStandardForm(Matrix,Matrix)"

For the programmer
==================

The object toStandardForm, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

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

Field -- field over which to define polynomial rings
****************************************************

Description
===========

The field used for computations in adaptedMonomialOrder,
see isFeasiblePoint, solveILP,
default value QQ (Macaulay2Doc).

See also
========

  * adaptedMonomialOrder -- constructs a ring with
    monomial order adapted to an integer program
  * isFeasiblePoint -- whether a point is feasible to
    an integer linear program
  * solveILP -- solve an integer linear program in standard
    form

Functions with optional argument named Field:
=============================================

  * "adaptedMonomialOrder(...,Field=>...)"
  * "isFeasiblePoint(...,Field=>...)"
  * "solveILP(...,Field=>...)"

For the programmer
==================

The object Field, is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

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

IsInStandardForm -- specify whether the integer program is in standard form
***************************************************************************

Description
===========

An optional method for solveILP, to specify whether a program
is in standard form. The default value is true. If
IsInStandardForm=>false, we first convert to standard form,
before solving.

The following example is in [CLO, Chapter 8, Section 1]. Note that in contrast
to solveILP, with IsInStandardForm=>true, the output involves
only variables that are in the specified program, meaning that the slack
variables, that get introduced to convert to standard form, are omitted in the
following output.

+-----------------------------------------------+
|i1 : A = matrix{{4, 5}, {2, 3}}                |
|                                               |
|o1 = | 4 5 |                                   |
|     | 2 3 |                                   |
|                                               |
|              2       2                        |
|o1 : Matrix ZZ  <-- ZZ                         |
+-----------------------------------------------+
|i2 : b = matrix{{37}, {20}}                    |
|                                               |
|o2 = | 37 |                                    |
|     | 20 |                                    |
|                                               |
|              2       1                        |
|o2 : Matrix ZZ  <-- ZZ                         |
+-----------------------------------------------+
|i3 : c = matrix{{-11, -15}}                    |
|                                               |
|o3 = | -11 -15 |                               |
|                                               |
|              1       2                        |
|o3 : Matrix ZZ  <-- ZZ                         |
+-----------------------------------------------+
|i4 : solveILP(A, b, c, IsInStandardForm=>false)|
|                                               |
|o4 = | 4 |                                     |
|     | 4 |                                     |
|                                               |
|              2       1                        |
|o4 : Matrix ZZ  <-- ZZ                         |
+-----------------------------------------------+

See also
========

  * solveILP -- solve an integer linear program in standard
    form
  * toStandardForm -- converts an LP to standard form

Functions with optional argument named IsInStandardForm:
========================================================

  * "solveILP(...,IsInStandardForm=>...)"

For the programmer
==================

The object IsInStandardForm, is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

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