Linear Inequality Simplifier

[אוריאל מליחי‎]

Hello everyone!

As part of my final project in my computer science degree I would like to develop a class for linear inequalities simplifying. The class's main algorithm is that for given a set of linear inequalities in m variables, it returns a simplified set. "Simplified" may mean an equivalent set with a smallest number of inequalities. As an example, given the inequalities:

x+y≥1

x+y≤0

the algorithm should return the empty set. Given the inequalities:

x+y≥1

2x+2y≥3

the algorithm should return e.g.

2x+2y≥3

The class will also implement operator overloading for + (adding one set to another) and – (removing a subset from original set) and more.

For this project to work I need to fully understand the implemented inequality classes in SymPy which are in sympy.core.relational, so I would know how to manipulate SymPy's inequalities.

The problem is that when I am trying to go through the code of those classes I get lost. There are so many subclasses there and every subclass is inheriting from some other base class.

Is there a way to see a class diagram of those classes so it would be more clear what the purpose of each class is?  Does anyone have another idea for understanding those classes?

[Oscar Benjamin]

‪On Sun, 27 Dec 2020 at 10:46, ‫אוריאל מליחי‬‎ <orielm...@gmail.com> wrote:‬
>
> Hello everyone!

Hi,

> As part of my final project in my computer science degree I would like to develop a class for linear inequalities simplifying.

That sounds like an excellent project. To be clear, are you intending
for this to be incorporated as part of sympy?

Handling systems of inequalities is a feature that is currently
missing from sympy but the most useful way to add it would really be
as a function or several functions rather than a class (although the
function could use a class internally).

> The class's main algorithm is that for given a set of linear inequalities in m variables, it returns a simplified set. "Simplified" may mean an equivalent set with a smallest number of inequalities. As an example, given the inequalities:
>
> x+y≥1
>
> x+y≤0
>
> the algorithm should return the empty set. Given the inequalities:
>
> x+y≥1
>
> 2x+2y≥3
>
> the algorithm should return e.g.
>
> 2x+2y≥3

Or perhaps:

x+y >= 3/2

It would be useful to have a function for making a subset of the
symbols in an inequality become the subject. There already is a
function for this but it doesn't work for systems of inequalities with
multiple unknowns:

In [1]: from sympy.solvers.inequalities import reduce_inequalities

In [2]: ineq = x + y > 2

In [3]: reduce_inequalities(ineq, [x])
Out[3]: x > 2 - y

In [4]: reduce_inequalities(ineq, [y])
Out[4]: y > 2 - x

In [5]: reduce_inequalities([x+y > 2, x < 1], [x, y])
---------------------------------------------------------------------------
NotImplementedError
inequality has more than one symbol of interest.

> The class will also implement operator overloading for + (adding one set to another) and – (removing a subset from original set) and more.

This is already handled by Python's built in set class so it isn't
really necessary to make a class for this. We can just put the
inequalities in a set.

> For this project to work I need to fully understand the implemented inequality classes in SymPy which are in sympy.core.relational, so I would know how to manipulate SymPy's inequalities.
>
> The problem is that when I am trying to go through the code of those classes I get lost. There are so many subclasses there and every subclass is inheriting from some other base class.
>
> Is there a way to see a class diagram of those classes so it would be more clear what the purpose of each class is? Does anyone have another idea for understanding those classes?

The codebase for sympy is large which means it takes time to
understand. You can see the inheritance scheme for these classes with
mro:

In [6]: LessThan.mro()
Out[6]:
[sympy.core.relational.LessThan,
sympy.core.relational._Less,
sympy.core.relational._Inequality,
sympy.core.relational.Relational,
sympy.logic.boolalg.Boolean,
sympy.core.basic.Basic,
sympy.printing.defaults.Printable,
sympy.core.evalf.EvalfMixin,
object]

Here Printable and EvalfMixin are mixins that provide printing support
and make it possible to use .evalf() e.g.:

In [7]: x < pi
Out[7]: x < π

In [8]: _.evalf()
Out[8]: x < 3.14159265358979

Basic is a fundamental class in sympy. Most sympy objects are
instances of Basic. Basic is used to represent mathematical objects as
trees and to implement operations like subs working over those trees.
You can see an explanation of that here:
https://docs.sympy.org/latest/tutorial/manipulation.html
(Surprisingly that page doesn't actually mention Basic!)

Boolean is a subclass of Basic for objects representing boolean
True/False. The Boolean class provides operations like `&` and `|`
representing "and" and "or" (as well as many other operations):

In [9]: (x < pi) & (y < 3)
Out[9]: x < π ∧ y < 3

Relational is a subclass of Boolean and is the common superclass for
LessThan, StrictLessThan, Equality, Unequality, GreaterThan and
StrictGreaterThan representing the 6 types of relation in sympy (`<=,
<, ==, !=, >=, >`).

The classes `_Inequality` and `_Less` are used for sharing/dividing
code between the different inequality classes.

--
Oscar

[samuel....@gmail.com]

2020-12-27 10:46:27 UTC:

>
> As part of my final project in my computer science degree I would like

> to develop a class for linear inequalities simplifying. The class's main

> algorithm is that for given a set of linear inequalities in m variables,

> it returns a simplified set. "Simplified" may mean an equivalent set with

> a smallest number of inequalities. As an example, given the inequalities:

>
> x+y≥1
> x+y≤0
>
> the algorithm should return the empty set.

I guess in this case it should rather return the set containing

the single condition 0 > 1 (or 0 == 1) since there is no solution,

while an empty set of constraints allows all values of x and y.

> Given the inequalities:
>
> x+y≥1
> 2x+2y≥3
>
> the algorithm should return e.g.
>
> 2x+2y≥3
>
> The class will also implement operator overloading for +

> (adding one set to another) and – (removing a subset

> from original set) and more.

Note that the solutions to a set of linear inequalities form a polytope;

each inequality describes a half-space; taking the union of two sets

of constraints corresponds to taking the intersection of the polytopes

they describe.

[אוריאל מליחי‎]

Thank you all for your advices.

and Oscar, for your question- yes, i do intend
for this to be incorporated as part of sympy if it is possible.

[Oscar Benjamin]

Okay, well if you want this to be included in sympy I suggest to begin
by making some specific proposals either here or in github issues. We
should agree the basic ideas before too much work is done. Of course
you don't have to implement all the proposals but we should agree what
makes sense as part of sympy even if your project is only a part of
what we would want.

Where possible it is best to improve the implementation of existing
API functions rather than introduce new ones but there certainly are
reasons for wanting some new functions for working with inequalities:
exactly what those new functions would be is the part that needs to be
agreed if this is to be included in sympy.

I would say that eliminating one or more variables from a system of
inequalities is very useful and there is e.g. Fourier-Motzkin
elimination
https://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination
as well as linear programming:
https://en.wikipedia.org/wiki/Linear_programming

Actually one of the most useful things at least for internal use in
sympy would be being able to ask whether an inequality is implied by a
collection of inequalities. A simple example is that x > 0 implies
that x > 1 but we would like to pose more complicated questions like:

Given that x > y, y > 0, x + y > z is it the case that 2*x > 0

The possible answers to a problem like this are "yes", "no" or "maybe".

The reason that we want to be able to answer this sort of question is
because handling inequalities like this is a key feature that is
wanted in the new assumptions system. A function that can take a
system of inequalities and determine their satisfiability is
sufficient to implement this because if (A and not B) is not
satisfiable then we must have (B or not A) which is the same as (A
implies B).

Oscar

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/c00aa378-2b27-4b79-a94b-d6c540f76fb9n%40googlegroups.com.

[אוריאל מליחי‎]

> Okay, well if you want this to be included in sympy I suggest to begin.

> by making some specific proposals either here or in github issues. We
> should agree the basic ideas before too much work is done. Of course
> you don't have to implement all the proposals but we should agree what
> makes sense as part of sympy even if your project is only a part of
> what we would want.

> Where possible it is best to improve the implementation of existing
> API functions rather than introduce new ones but there certainly are
> reasons for wanting some new functions for working with inequalities:
> exactly what those new functions would be is the part that needs to be
> agreed if this is to be included in sympy.

> I would say that eliminating one or more variables from a system of
> inequalities is very useful and there is e.g. Fourier-Motzkin
> elimination
> https://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination
> as well as linear programming:
> https://en.wikipedia.org/wiki/Linear_programming

> Actually one of the most useful things at least for internal use in
> sympy would be being able to ask whether an inequality is implied by a
> collection of inequalities. A simple example is that x > 0 implies
> that x > 1

I think you meant that x > 1 implies that x > 0, but I get the point.

> but we would like to pose more complicated questions like:

> Given that x > y, y > 0, x + y > z is it the case that 2*x > 0

> The possible answers to a problem like this are "yes", "no" or "maybe".

I see. Well I believe I can implement this function using the Linear Programing technique. 

if that is okay with you, I would like to start working on it right after my semester exams (in 3 weeks). 

Is there anything more I need to know/do before I start coding?   

> The reason that we want to be able to answer this sort of question is
> because handling inequalities like this is a key feature that is
> wanted in the new assumptions system. A function that can take a
> system of inequalities and determine their satisfiability is
> sufficient to implement this because if (A and not B) is not
> satisfiable then we must have (B or not A) which is the same as (A
> implies B).

Oscar

[Oscar Benjamin]

I think the main thing is that if you are looking to contribute this
to sympy then you should specify whether you are hoping to change
existing public functions (which functions and how would they change?)
or whether you are introducing new public API and if so what that API
would be. It's not possible for me to say on behalf of sympy that any
work would likely be included in sympy without knowing what the
expected output is.

The other thing I would say is that it's important to consider the
symbolic case in sympy. Algorithms in the symbolic case are different
from algorithms intended for an explicit numeric representation. As an
example of what I mean the wikipedia article describes Fourier-Motzkin
elimination as something that generates an exponentially growing
number of cases and therefore is computationally awkward. That isn't
true in sympy though because we can represent limits symbolically
using something like `Max(a, b)` where `a` and `b` are symbols and
that is a useful representation in situations where it isn't known
which symbol is greater. It isn't clear to me how easily the linear
programming techniques can apply in a situation where the coefficients
in the inequalities are symbolic.

Oscar

[S.Y. Lee]

I have a full implementation of linear programming in https://github.com/sympy/sympy/issues/20391
Although if you may or may not want the code, I hope it can reduce any duplicate efforts if you were intending to implement the same method.

[אוריאל מליחי‎]

Hey Oscar,

sorry for the late reply, I was overloaded with exams.

For your first question, I intend to create a new function that when given a set of linear inequalities and a target inequality it would output True if the target is implied by this set, False if it is not, and Unknown otherwise. I wrote doctests to make it all more clear.

You can see it here –

https://github.com/orielmalihi/Final-Project/blob/main/iset%20tests.py

(the main function there is called 'is_implied_by')

For your second question, I intended to use Scipy LP solver, but as far as I can tell it only works with floats. I could convert every coefficient to float using the 'evalf()' function but then we would get 99.9% accurate results and not 100%.

Other option is to use the LP solver suggested by Lee (above), but it is unclear for me how it works, since it has no documentation of input/output. Moreover, I ran the example mentioned there with Scipy LP solver and got different results somehow. (if I understood right, Matric A is the lhs of the constraints, matric B is the rhs, matric c is the objective, and D is the lower bounds. if I am wrong I would be happy if you could tell me why)

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/udUZ_U-mAh4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/a69bc5a0-abf6-401a-9004-7c7eedbfdf8dn%40googlegroups.com.

[S.Y. Lee]

SciPy's implementation is to minimize c^{T} x while my implementation is to maximize  c^{T} x
I verified that it gives same result result with scipy when I changed the problem to minimize -c^{T} x

I have given a brief documentation about how to use in the comment, but not in the docstring, because the project is totally skeletal.
# Maximize Cx + D constrained with Ax <= B and x >= 0
# Minimize y^{T}B constrained with y^{T}A >= C^{T} and y >= 0
I haven't studied the simplex algorithm for a while, but at least I don't think that that there was a discovered flaw in the algorithm.

[אוריאל מליחי‎]

Thank you Lee for your quick reply.

I will recheck it.

בתאריך יום ג׳, 16 בפבר׳ 2021, 19:36, מאת S.Y. Lee ‏<syle...@gmail.com>:

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/311732de-ed2f-4d62-9a3e-5efd757b1d1en%40googlegroups.com.

[Oscar Benjamin]

‪On Tue, 16 Feb 2021 at 17:01, ‫אוריאל מליחי‬‎ <orielm...@gmail.com> wrote:‬
>
> For your first question, I intend to create a new function that when given a set of linear inequalities and a target inequality it would output True if the target is implied by this set, False if it is not, and Unknown otherwise. I wrote doctests to make it all more clear.
>
> You can see it here –
>
> https://github.com/orielmalihi/Final-Project/blob/main/iset%20tests.py

That would be useful in sympy.

> For your second question, I intended to use Scipy LP solver, but as far as I can tell it only works with floats. I could convert every coefficient to float using the 'evalf()' function but then we would get 99.9% accurate results and not 100%.

We can't use scipy as part of sympy because sympy does not "depend" on
scipy. In sympy we want to handle the symbolic case. The *minimum* we
would want for an implementation in sympy is something that handles
systems with rational coefficients without *any* rounding error. The
more interesting cases would be irrational coefficients like sqrt(2)
or the symbolic case where the coefficients are something like a
symbol x. If the implementation just uses scipy then there's no reason
to include it in sympy because users could just use it directly from
scipy.


Oscar

[אוריאל מליחי‎]

I understand. 

So I would use the LP solver implemented by Lee which should work with symbolic coefficients.

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/udUZ_U-mAh4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+un...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAHVvXxQb4TEb7tPov6df5Vv2P-d4XYSKpi3xqUHY5w%2BuTCx2pQ%40mail.gmail.com.

[Oscar Gustafsson]

After currently using Mathematica for similar things, I would just like to encourage you to provide some nice method to simplify constraints of piecewise functions using your simplifier, including additional constraints on the range of variables (as SymPy doesn't have a way to put ranges on variables). That doesn't really exist in Mathematica (Assuming[..., Simplify[piecewise]) doesn't always seems to simplify as far as possible).

Something like

simplify_piecewise_range(piecewisefunction, common_constraints)

That adds the common_constraints to each region constraint and applies your method. (Possibly, optionally, removing the common_constraints from the final regions if feasible.)

This would be really useful in some situations and a place where Mathematica (at least with my level of knowledge) can be improved, so with this SymPy would in fact be more powerful than Mathematica.

Btw, the corresponding Mathematica-function is called Reduce https://reference.wolfram.com/language/ref/Reduce.html

There is an old PR which may be useful to revive in relation to this: https://github.com/sympy/sympy/pull/17443 although sort of independent.

It will also be useful to have a function that can replace Min/Max expressions with linear inequalities (and possibly back again). Right now there is some logic to convert from linear inequalites to Min/Max, but not back. As far as I recall. (There may be a PR doing the Min/Max to linear as well, but not really sure.)

BR Oscar

‪Den tors 18 feb. 2021 kl 11:57 skrev ‫אוריאל מליחי‬‎ <orielm...@gmail.com>:‬

You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAMEnX6gOMEDJ1qf8ga1sQG8ggTBpG6spP1jRfywsDtWZRcvWKA%40mail.gmail.com.

[Oscar Benjamin]

On Thu, 18 Feb 2021 at 11:32, Oscar Gustafsson
<oscar.gu...@gmail.com> wrote:
>
> After currently using Mathematica for similar things, I would just like to encourage you to provide some nice method to simplify constraints of piecewise functions using your simplifier, including additional constraints on the range of variables (as SymPy doesn't have a way to put ranges on variables). That doesn't really exist in Mathematica (Assuming[..., Simplify[piecewise]) doesn't always seems to simplify as far as possible).
>
> Something like
> simplify_piecewise_range(piecewisefunction, common_constraints)
> That adds the common_constraints to each region constraint and applies your method. (Possibly, optionally, removing the common_constraints from the final regions if feasible.)

I imagined that this would be something that the new assumptions could
handle in refine. Something like:

p = Piecewise((x, x < 1), (x**2, True))
p = refine(p, abs(x) < 1)

The idea would then be that e.g. when you have Integral(f, (x, a, b))
then the integration routine can do

f = refine(f, (a < x) & (x < b))

> Btw, the corresponding Mathematica-function is called Reduce https://reference.wolfram.com/language/ref/Reduce.html

That does look nice. It seems to use many primitives that sympy
doesn't have yet though... I think quantifiers are still some way off
in sympy.

> There is an old PR which may be useful to revive in relation to this: https://github.com/sympy/sympy/pull/17443 although sort of independent.
>
> It will also be useful to have a function that can replace Min/Max expressions with linear inequalities (and possibly back again). Right now there is some logic to convert from linear inequalites to Min/Max, but not back. As far as I recall. (There may be a PR doing the Min/Max to linear as well, but not really sure.)

Is this what you mean?

In [1]: Min(x, y).rewrite(Piecewise)
Out[1]:
⎧x for x ≤ y
⎨
⎩y otherwise

Perhaps there could be a rewrite(Max) for Piecewise.


Oscar

[Oscar Gustafsson]

Den tors 18 feb. 2021 kl 14:36 skrev Oscar Benjamin <oscar.j....@gmail.com>:

On Thu, 18 Feb 2021 at 11:32, Oscar Gustafsson
<oscar.gu...@gmail.com> wrote:
>
> After currently using Mathematica for similar things, I would just like to encourage you to provide some nice method to simplify constraints of piecewise functions using your simplifier, including additional constraints on the range of variables (as SymPy doesn't have a way to put ranges on variables). That doesn't really exist in Mathematica (Assuming[..., Simplify[piecewise]) doesn't always seems to simplify as far as possible).
>
> Something like
> simplify_piecewise_range(piecewisefunction, common_constraints)
> That adds the common_constraints to each region constraint and applies your method. (Possibly, optionally, removing the common_constraints from the final regions if feasible.)

I imagined that this would be something that the new assumptions could
handle in refine. Something like:

p = Piecewise((x, x < 1), (x**2, True))
p = refine(p, abs(x) < 1)

The idea would then be that e.g. when you have Integral(f, (x, a, b))
then the integration routine can do

f = refine(f, (a < x) & (x < b))

Yes, a different assumption system will also do the trick. But until that is in place, this would be a useful short-cut for a specific use case.

> There is an old PR which may be useful to revive in relation to this: https://github.com/sympy/sympy/pull/17443 although sort of independent.
>
> It will also be useful to have a function that can replace Min/Max expressions with linear inequalities (and possibly back again). Right now there is some logic to convert from linear inequalites to Min/Max, but not back. As far as I recall. (There may be a PR doing the Min/Max to linear as well, but not really sure.)

Is this what you mean?

In [1]: Min(x, y).rewrite(Piecewise)
Out[1]:
⎧x  for x ≤ y
⎨
⎩y  otherwise

Perhaps there could be a rewrite(Max) for Piecewise.

I seem to recall that I did something that rewrote/simplified, probably as part of the pattern based logic simplification,

And(x <= y, x <= z)

to

x <= Min(y, z) 

At some later stage I realized it was sometimes a bad idea (as the logic simplification sometimes worked better without the Min/Max, do not recall exactly) and I sort of regretted introducing that rewrite, but cannot recall if the reverse operation was ever introduced. Piecewise may work though, but I believe that for the linear inequality simplifier it may be better to rewrite x <= Min(y, z)  back to  And(x <= y, x <= z) .

BR Oscar

[אוריאל מליחי‎]

Hello everyone!

I finally completed implementing these functions.

Quick reminder:
The main function is called is_implied_by and it gets a set of linear inequalities and a target linear inequality and return whether the target is implied by the set or not.

Two other functions are find_values_interval and simplify_linear_inequalities.

 find_values_interval gets a set of linear inequalities and a target expression (expr) and returns an interval of [min possible value for expr, max possible value for expr].

simplify_linear_inequalities gets a set of linear inequalities and returns a simplified set (redundant inequalities are removed).

Now I would like to know what are the next steps for me to do in order to get my implementation into sympy. This is my first time contributing so detailed explanation would be really helpful.

[Oscar Benjamin]

That's great. I suggest not trying to add everything at once. Probably some changes will need to be made and there are other steps like tests and so on that would need to be added if there aren't already tests in the right format.

Is your code publicly viewable already? For example if you put it in a github repo/gist then you can send a link here.

Oscar

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/07668755-217b-4487-805d-1faefd70191bn%40googlegroups.com.

[אוריאל מליחי‎]

Yes, my code is viewable in here-

https://github.com/orielmalihi/Final-Project/blob/main/my%20functions/inequalities%20functions.py

[Oscar Benjamin]

Okay, that code looks good. It will also need docs and tests.

I suggest first trying to add the smallest part of this to sympy. Then
other parts can be added one step at a time.

The question is what is the smallest part that is useful on its own.
Is that the simplex function?

If you open a pull request to add that to sympy then you can get some
feedback on it and make further changes until it is ready. Once that
part is merged you will have a better idea how to prepare the other
parts for inclusion into sympy.

Another question is performance. I expect that in practice the most
important part of the performance of this method is being able to
handle large sparse systems of mostly unrelated inequalities so being
able to separate a system using sparse techniques to reduce the size
of the problem will make the method much faster in common usage.

Oscar

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/6ae5a93d-5976-479d-ad87-017a0c82b603n%40googlegroups.com.

[אוריאל מליחי‎]

ok. 

I made a pull request for the linear programing solver and I did not add the inequalities functions in the commit for now.

The pull request number is  #21673

waiting for your aproval/corrections.

thank you!

[Oscar Benjamin]

Great! There seems to have been some kind of git problem so that the
changes in the PR are not as intended though...

I left a comment at the PR:
https://github.com/sympy/sympy/pull/21673

Let's continue the discussion there.

Oscar

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/50937a32-8764-4380-b941-efb5fb1864ben%40googlegroups.com.