Wolfram Library Archive

All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Integer Programming with Groebner Bases

Devendra Kapadia
Organization: Wolfram Research, Inc.
Department: Kernel Technology

Our aim in this notebook is to define a Mathematica function for solving problems in Integer Programming by the Groebner Basis method [Conti and Traverso, AAECC`9, Lecture Notes in Computer Science, Vol. 539, 130-139, Springer Verlag, 1991]. The general Integer Programming problem can be reduced to that of minimizing a cost vector c.w subject to the conditions A.w = b, where the components of the optimal solution w are required to be non-negative integers.

The algorithm is divided into three steps:

1. The coefficients of the matrix A are used to form the exponents in a certain binomial ideal.

2. The Groebner basis of the binomial ideal with respect to a monomial order given by the vector c is found using the kernel function GroebnerBasis.

3. The optimal solution is found by reading off the exponents in the answer obtained by reducing a certain monomial formed from the components of b, with respect to the Groebner basis and the same monomial order. The kernel function PolynomialReduce is used for this step.

In contrast to Linear Programming, the problem of Integer Programming is NP-complete. Hence, there will be an "expensive step" in any algorithm for the problem. In our case, the expensive step is that of finding the Groebner basis. We will define the function IntegerProgramming below and give several examples of problems which can be solved using it. At present, we assume that either all the components of A and b are non-negative or that the same condition holds for the components of c, although this restriction may be easy to remove in future.

*Applied Mathematics > Optimization
*Mathematics > Algebra > Linear Algebra

IntegerProgramming, GroebnerBasis
Downloads Download Wolfram CDF Player

IntegerProgramming2.nb (18.7 KB) - Mathematica Notebook