Ask Your Question
3

Generating integral solutions to a system of linear inequalities

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

Janoš Vidali gravatar image

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

2 Answers

Sort by » oldest newest most voted
1

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

tmonteil gravatar image

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 more

Comments

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.

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

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

Emmanuel Charpentier gravatar image

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 more

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 gravatar imageJanoš Vidali ( 2019-07-08 23:05:46 +0100 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

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

Seen: 494 times

Last updated: Jul 09 '19