patternMinor
Finding all solutions to an integer linear programming (ILP) problem
Viewed 0 times
problemlinearilpallprogrammingsolutionsfindinginteger
Problem
My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this problem near the end, but I'm interested in knowing if there is a proper and efficient algorithm or method for solving this kind of problem.
There is no objective function, but the constraints for this ILP are
$$
\begin{equation}
0 \leq -2x -y \leq 8 \\
0 \leq 1-x+3y \leq 5 \\
0 \leq 2+x-y \leq 2 \\
x,y \in \mathbb{Z}
\end{equation}
$$
Since this ILP has two variables, I can visually inspect the solution region by graphing the lines formed by the constraints, which are
$$
\begin{align}
y &\leq -2x \\
y &\geq -2x-8 \\
y &\geq \frac{1}{3}x - \frac{1}{3} \\
y &\leq \frac{1}{3}x + \frac{4}{3} \\
y &\leq x + 2 \\
y &\geq x
\end{align}
$$
By inspection, there are 6 integer solutions for $(x, y)$: $\{ (0,0), (-1,1), (-1,0), (-2,0), (-2,-1), (-3,-1) \}$.
However, my current method is to use linear programming with non-negativity relaxed and integers from branch-and-cut. I've tried using a set of four objective functions: minimize $x$, maximize $x$, minimize $y$, and maximize $y$. These give a smaller search area as
$$
\begin{equation}
-3 \leq x \leq 0 \\
-1 \leq y \leq 1
\end{equation}
$$
I then iterate over all valid integer tuples in that smaller area and filter it for tuples that satisfy the original constraints. The tuples that remain are all valid integer solutions.
There is no objective function, but the constraints for this ILP are
$$
\begin{equation}
0 \leq -2x -y \leq 8 \\
0 \leq 1-x+3y \leq 5 \\
0 \leq 2+x-y \leq 2 \\
x,y \in \mathbb{Z}
\end{equation}
$$
Since this ILP has two variables, I can visually inspect the solution region by graphing the lines formed by the constraints, which are
$$
\begin{align}
y &\leq -2x \\
y &\geq -2x-8 \\
y &\geq \frac{1}{3}x - \frac{1}{3} \\
y &\leq \frac{1}{3}x + \frac{4}{3} \\
y &\leq x + 2 \\
y &\geq x
\end{align}
$$
By inspection, there are 6 integer solutions for $(x, y)$: $\{ (0,0), (-1,1), (-1,0), (-2,0), (-2,-1), (-3,-1) \}$.
However, my current method is to use linear programming with non-negativity relaxed and integers from branch-and-cut. I've tried using a set of four objective functions: minimize $x$, maximize $x$, minimize $y$, and maximize $y$. These give a smaller search area as
$$
\begin{equation}
-3 \leq x \leq 0 \\
-1 \leq y \leq 1
\end{equation}
$$
I then iterate over all valid integer tuples in that smaller area and filter it for tuples that satisfy the original constraints. The tuples that remain are all valid integer solutions.
Solution
"Linear programming" is an optimisation problem. The problem that you are trying to solve is to count lattice points inside a finite convex rational polytope.
This problem has a polynomial-time algorithm, the general case for which discovered by Alexander Barvinok in 1994. It appears that all modern algorithms are broadly based on this method. Barvinok & Pommershein's 1999 paper, An Algorithmic Theory of Lattice Points in Polyhedra, is probably the best introduction to the theory. (Actually, it appears that Barvinok has subsequently written a book or monograph; that might be even better.)
There are probably more recent developments than I'm aware of, but this will give you a starting point for chasing citations.
This problem has a polynomial-time algorithm, the general case for which discovered by Alexander Barvinok in 1994. It appears that all modern algorithms are broadly based on this method. Barvinok & Pommershein's 1999 paper, An Algorithmic Theory of Lattice Points in Polyhedra, is probably the best introduction to the theory. (Actually, it appears that Barvinok has subsequently written a book or monograph; that might be even better.)
There are probably more recent developments than I'm aware of, but this will give you a starting point for chasing citations.
Context
StackExchange Computer Science Q#62926, answer score: 9
Revisions (0)
No revisions yet.