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.
On Wednesday, February 17, 2021 at 2:01:36 AM UTC+9 [email protected]
wrote:
> 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)
>
> On Thu, 31 Dec 2020 at 23:38, S.Y. Lee <[email protected]> wrote:
>
>> 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.
>>
>> On Thursday, December 31, 2020 at 5:58:55 AM UTC+9 Oscar wrote:
>>
>>> On Wed, 30 Dec 2020 at 19:47, אוריאל מליחי <[email protected]>
>>> wrote:
>>> >
>>> > > 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?
>>>
>>> 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
>>>
>> --
>> 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
>> [email protected].
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/sympy/a69bc5a0-abf6-401a-9004-7c7eedbfdf8dn%40googlegroups.com
>>
>> <https://groups.google.com/d/msgid/sympy/a69bc5a0-abf6-401a-9004-7c7eedbfdf8dn%40googlegroups.com?utm_medium=email&utm_source=footer>
>> .
>>
>
--
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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/sympy/311732de-ed2f-4d62-9a3e-5efd757b1d1en%40googlegroups.com.
