# Generating integral solutions to a system of linear inequalities

I was wondering whether there was a straightforward way in Sage to generate all integral solutions of a system of linear inequalities. I have talked to Nicolas Thiéry here at FPSAC/Sage days 103, and he showed me the interface to PALP, but said I should ask here.

I have programmed such a solver myself for the sage-drg package:

https://github.com/jaanos/sage-drg/bl...

It is a solution generator (as opposed to a function returning all solutions) which uses Sage's integer linear programming facilities. It also supports adding conditions on-the-fly and making a copy of the generator.

I was thinking that it would be a nice addition to Sage (Mathematica has FindInstance, which does something similar) - unless something like this already exists. Of course, the interface should be made more user-friendly. I would also like to know if there is a better way of doing such a thing.

edit retag close merge delete

Sort by » oldest newest most voted

Since you already know about MILP, here are 2 possibities.

If p is your MixedIntegerLinearProgram, you can construct its polytope and ask for its integer points:

sage: P = p.polyhedron()
sage: P.integral_points()


This works for "fat" polytopes of low dimension.

Another possiblity, to be used when it is hard to find even a single point, is to use the power of MILP solvers as follows:

• pick a random linear form to maximize
• solve the linear integer problem and yield the returned solution
• add a linear constraint that removes only that solution to the system (because of the linear form, the provious solution is an extremal point of the convex hull of the set of the integer solutions)
• loop
more

1

What I'm working with is systems of equations with (in most cases) 3^3, 4^3 or 5^3 variables, so this is definitely not low dimension. I've tried with a system for which my method quickly finds all 7 integral solutions, but finding (or even counting) the integral points of the polytope was not feasible.

The second possibility you give is kind of what I'm currently doing - except I'm using recursion (constraining one integral expression in each level), as it is easier to constrain the expressions that are required to be integral than some random linear form which might need to be decreased in very small intervals to eliminate one solution at a time.

I'm not well versed in this kind of problems, but I thing that chapter 17 of this book should give you a head start.

more

Yes, as I said, I have used MILP in my own solution. I was just interested in whether this is the way to go, or maybe using PALP or cddlib or something else would be more efficient.