ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 10 Jul 2019 15:04:14 +0200Generating integral solutions to a system of linear inequalitieshttps://ask.sagemath.org/question/47099/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`](https://github.com/jaanos/sage-drg/) package:
https://github.com/jaanos/sage-drg/blob/master/drg/find.py
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.Mon, 08 Jul 2019 15:25:27 +0200https://ask.sagemath.org/question/47099/generating-integral-solutions-to-a-system-of-linear-inequalities/Answer by Emmanuel Charpentier for <p>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.</p>
<p>I have programmed such a solver myself for the <a href="https://github.com/jaanos/sage-drg/"><code>sage-drg</code></a> package:</p>
<p><a href="https://github.com/jaanos/sage-drg/blob/master/drg/find.py">https://github.com/jaanos/sage-drg/bl...</a></p>
<p>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.</p>
<p>I was thinking that it would be a nice addition to Sage (Mathematica has <code>FindInstance</code>, 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.</p>
https://ask.sagemath.org/question/47099/generating-integral-solutions-to-a-system-of-linear-inequalities/?answer=47106#post-id-47106I'm not well versed in this kind of problems, but I thing that chapter 17 of [this book](http://sagebook.gforge.inria.fr/english.html) should give you a head start.Mon, 08 Jul 2019 22:53:52 +0200https://ask.sagemath.org/question/47099/generating-integral-solutions-to-a-system-of-linear-inequalities/?answer=47106#post-id-47106Comment by Janoš Vidali for <p>I'm not well versed in this kind of problems, but I thing that chapter 17 of <a href="http://sagebook.gforge.inria.fr/english.html">this book</a> should give you a head start.</p>
https://ask.sagemath.org/question/47099/generating-integral-solutions-to-a-system-of-linear-inequalities/?comment=47107#post-id-47107Yes, 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.Mon, 08 Jul 2019 23:05:46 +0200https://ask.sagemath.org/question/47099/generating-integral-solutions-to-a-system-of-linear-inequalities/?comment=47107#post-id-47107Answer by tmonteil for <p>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.</p>
<p>I have programmed such a solver myself for the <a href="https://github.com/jaanos/sage-drg/"><code>sage-drg</code></a> package:</p>
<p><a href="https://github.com/jaanos/sage-drg/blob/master/drg/find.py">https://github.com/jaanos/sage-drg/bl...</a></p>
<p>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.</p>
<p>I was thinking that it would be a nice addition to Sage (Mathematica has <code>FindInstance</code>, 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.</p>
https://ask.sagemath.org/question/47099/generating-integral-solutions-to-a-system-of-linear-inequalities/?answer=47110#post-id-47110Since 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
Tue, 09 Jul 2019 13:52:15 +0200https://ask.sagemath.org/question/47099/generating-integral-solutions-to-a-system-of-linear-inequalities/?answer=47110#post-id-47110Comment by Janoš Vidali for <p>Since you already know about <code>MILP</code>, here are 2 possibities.</p>
<p>If <code>p</code> is your <code>MixedIntegerLinearProgram</code>, you can construct its polytope and ask for its integer points:</p>
<pre><code>sage: P = p.polyhedron()
sage: P.integral_points()
</code></pre>
<p>This works for "fat" polytopes of low dimension.</p>
<p>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:</p>
<ul>
<li>pick a random linear form to maximize</li>
<li>solve the linear integer problem and yield the returned solution</li>
<li>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)</li>
<li>loop</li>
</ul>
https://ask.sagemath.org/question/47099/generating-integral-solutions-to-a-system-of-linear-inequalities/?comment=47114#post-id-47114What 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.Wed, 10 Jul 2019 15:04:14 +0200https://ask.sagemath.org/question/47099/generating-integral-solutions-to-a-system-of-linear-inequalities/?comment=47114#post-id-47114