GSoC 2022:Simplex method for linear programming.

[Mayank Raj]

Hello all,

My name is Mayank Raj and i am currently a 3rd year undergraduate at IIT Patna(CSE). I have  been making  contributions since last year and would like to implement simplex method for linear programming as a GSoC 2022 project.

Looking forward for your responses.

[Qijia Liu]

SciPy has simplex method implemented. Do we need to re-implement it in SymPy?

[Oscar Gustafsson]

There are two (I think, at least one) PRs that are not merged that does this. So it would be better to sort one of those out. Iirc there is limiterd work left, like documentation and testing.

BR Oscar 

Den tors 14 apr. 2022 19:54Qijia Liu <liu...@pku.edu.cn> skrev:

SciPy has simplex method implemented. Do we need to re-implement it in SymPy?

--
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/057e821d-03be-40bd-9c20-2f44875a1f55n%40googlegroups.com.

[Oscar Benjamin]

On Thu, 14 Apr 2022 at 18:54, Qijia Liu <liu...@pku.edu.cn> wrote:
>
> SciPy has simplex method implemented. Do we need to re-implement it in SymPy?

The SciPy implementation only works for floats. It should be possible
to solve linear programming problems at least using exact rational
numbers. Something like this is needed to be able to solve systems of
linear inequalities. That in turn is needed to be able to answer
assumptions queries involving linear inequalities.

--
Oscar

[Oscar Benjamin]

> Den tors 14 apr. 2022 19:54Qijia Liu <liu...@pku.edu.cn> skrev:
>>
>> SciPy has simplex method implemented. Do we need to re-implement it in SymPy?
>>

On Fri, 15 Apr 2022 at 07:37, Oscar Gustafsson
<oscar.gu...@gmail.com> wrote:
>
> There are two (I think, at least one) PRs that are not merged that does this. So it would be better to sort one of those out. Iirc there is limiterd work left, like documentation and testing.

The two PRs are here:

https://github.com/sympy/sympy/pull/22389
https://github.com/sympy/sympy/pull/21687

The first PR adds Fourier-Motzkin elimination which is potentially
more powerful than linear programming because you could use it to do
some reductions in a system of inequalities that is not entirely
linear i.e. you could use it to eliminate a few symbols that appear
linearly even if others appear nonlinearly. It has extremely bad
asymptotic complexity for large systems of linear inequalities though
(and in the PR only linear inequalities can be handled).

The other PR adds linear programming based on a simplex method. It
seems to be reasonably efficient but can be optimised. A suggestion I
made there makes it about 30x faster for large inputs and I think it
could be faster still if implemented at the DomainMatrix level. I'd
like to see that PR finished but it looks as if the author
underestimated how much more work is needed beyond getting together a
basic working implementation.

--
Oscar