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.

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
Field -- field over which to define polynomial rings
IsInStandardForm -- specify whether the integer program is in standard form

Author

Mike Cummings <[email protected]>

Version

This documentation describes version 0.1 of IntegerProgramming.

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. Version~0.1}},
  author = {Mike Cummings},
  howpublished = {A \emph{Macaulay2} package available at
    \url{https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages}}
}

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, defined in IntegerProgramming.m2.

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