Generating integral solutions to a system of linear inequalities

asked 2019-07-08 15:25:27 +0100

updated 2019-07-08 23:00:28 +0100

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 flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2019-07-09 13:52:15 +0100

tmonteil
27413 ●31 ●204 ●517 http://wiki.sagemath.o...

updated 2019-07-09 13:56:33 +0100

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

edit flag offensive delete link

Comments

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.

Janoš Vidali ( 2019-07-10 15:04:14 +0100 )edit

add a comment

answered 2019-07-08 22:53:52 +0100

Emmanuel Charpentier
7744 ●6 ●50 ●153

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.

edit flag offensive delete link

Comments

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.

Janoš Vidali ( 2019-07-08 23:05:46 +0100 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Generating integral solutions to a system of linear inequalities

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Generating integral solutions to a system of linear inequalities edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Generating integral solutions to a system of linear inequalities