9
$\begingroup$

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

Graph

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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for that observation. I am not familiar with the topics you mentioned, but upon short inspection, I believe they are a good starting point for learning more. Unfortunately, my reputation is too low to upvote you. $\endgroup$
    – resyst
    Aug 27, 2016 at 1:24
  • 7
    $\begingroup$ Huh. That's surprising. Checking whether there exists any integer point within a convex polytope (whether the number of such points is 0 or $>0$) is equivalent to checking feasibility of an integer linear programming (ILP) instance. ILP is NP-hard. So I would have inferred that it's NP-hard even to check whether a polytope contains one integral point, let alone count the number of them. How do we reconcile these two facts? Where have I gone wrong? $\endgroup$
    – D.W. ♦
    Aug 27, 2016 at 16:54
  • 2
    $\begingroup$ The catch is probably that Barvinok's algorithm is polynomial for a fixed dimension. If the number of variables is fixed, the algorithm scales polynomially as you add constraints. The typical cases where you want to enumerate lattice points are things like the solutions to linear Diophantine equations, and there the dimension tends to be low. $\endgroup$
    – Pseudonym ♦
    Aug 28, 2016 at 8:47
2
$\begingroup$

Land and Doig (1960) proposed a method for solving discrete programming problems. You may be able to modify his algorithm so that instead of solving an optimization problem you are enumerating every possible feasible integer solution.

Reference

A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems". Econometrica. 28 (3). pp. 497–520. doi:10.2307/1910129.

Improve this answer
$\endgroup$
0
$\begingroup$

read this paper: Computing convex hulls and counting integer points with polymake. I think polymake can do it for you.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.