Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #53448 > unrolled thread

Simplex Algorithm

Back to article view | Back to comp.lang.python

Contents

  Simplex Algorithm Tommy Vee <xxxxx@xxxxxx.xxx> - 2013-09-01 21:26 -0400
    Re: Simplex Algorithm Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-09-02 09:06 +0100
      Re: Simplex Algorithm Tommy Vee <xxxxx@xxxxxx.xxx> - 2013-09-02 10:42 -0400
      Re: Simplex Algorithm Tommy Vee <vitaletom1@gmail.com> - 2013-09-02 10:42 -0400
    Re: Simplex Algorithm Robert Kern <robert.kern@gmail.com> - 2013-09-02 10:45 +0100
    Re: Simplex Algorithm Robert Kern <robert.kern@gmail.com> - 2013-09-02 10:55 +0100
      Re: Simplex Algorithm Tommy Vee <xxxxx@xxxxxx.xxx> - 2013-09-02 11:06 -0400
        Re: Simplex Algorithm Robert Kern <robert.kern@gmail.com> - 2013-09-02 16:43 +0100
          Re: Simplex Algorithm Tommy Vee <xxxxx@xxxxxx.xxx> - 2013-09-02 14:59 -0400
          Re: Simplex Algorithm Tommy Vee <vitaletom1@gmail.com> - 2013-09-02 14:59 -0400
      Re: Simplex Algorithm Tommy Vee <vitaletom1@gmail.com> - 2013-09-02 11:06 -0400
    Re: Simplex Algorithm Tony the Tiger <tony@tiger.invalid> - 2013-09-16 13:47 -0500

#53448 — Simplex Algorithm

Anyone know where I can get an easy to use Python class or algorithm for 
the Simplex optimization algorithm?  I've tried the one in the link 
below, but I can't figure out if a) I'm using it properly, or b) where 
to get the solution.  BTW, I tried some test scenarios using MS Excel's 
"Solver" and just can't get this algorithm to match Excel's results 
(which is spot on).

http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python

BTW, if I can't something to work, I'm going to be forced to use the VBA 
programmatic Excel interface. That wouldn't be too bad, but the data 
comes from a DB and getting it properly positioned to use Excel's 
"Solver" is very painful.  A Python approach would be much cleaner.

Thanks,

TommyVee

[toc] | [next] | [standalone]

#53461

[Multipart message — attachments visible in raw view] — view raw

On Sep 2, 2013 2:31 AM, "Tommy Vee" <xxxxx@xxxxxx.xxx> wrote:
>
> Anyone know where I can get an easy to use Python class or algorithm for
the Simplex optimization algorithm?  I've tried the one in the link below,
but I can't figure out if a) I'm using it properly, or b) where to get the
solution.  BTW, I tried some test scenarios using MS Excel's "Solver" and
just can't get this algorithm to match Excel's results (which is spot on).
>
> http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>
> BTW, if I can't something to work, I'm going to be forced to use the VBA
programmatic Excel interface. That wouldn't be too bad, but the data comes
from a DB and getting it properly positioned to use Excel's "Solver" is
very painful.  A Python approach would be much cleaner.

Are you able to use scipy? It has the simplex algorithm (among many others)
in its optimize module:
http://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html

Oscar

[toc] | [prev] | [next] | [standalone]

#53485

On 9/2/2013 4:06 AM, Oscar Benjamin wrote:
>
> On Sep 2, 2013 2:31 AM, "Tommy Vee" <xxxxx@xxxxxx.xxx> wrote:
>  >
>  > Anyone know where I can get an easy to use Python class or algorithm
> for the Simplex optimization algorithm?  I've tried the one in the link
> below, but I can't figure out if a) I'm using it properly, or b) where
> to get the solution.  BTW, I tried some test scenarios using MS Excel's
> "Solver" and just can't get this algorithm to match Excel's results
> (which is spot on).
>  >
>  > http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>  >
>  > BTW, if I can't something to work, I'm going to be forced to use the
> VBA programmatic Excel interface. That wouldn't be too bad, but the data
> comes from a DB and getting it properly positioned to use Excel's
> "Solver" is very painful.  A Python approach would be much cleaner.
>
> Are you able to use scipy? It has the simplex algorithm (among many
> others) in its optimize module:
> http://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html
>
> Oscar
>
  scipy would be another possibility of last resort.  I will take a 
look. Thanks.

[toc] | [prev] | [next] | [standalone]

#53486

On 9/2/2013 4:06 AM, Oscar Benjamin wrote:
>
> On Sep 2, 2013 2:31 AM, "Tommy Vee" <xxxxx@xxxxxx.xxx> wrote:
>  >
>  > Anyone know where I can get an easy to use Python class or algorithm
> for the Simplex optimization algorithm?  I've tried the one in the link
> below, but I can't figure out if a) I'm using it properly, or b) where
> to get the solution.  BTW, I tried some test scenarios using MS Excel's
> "Solver" and just can't get this algorithm to match Excel's results
> (which is spot on).
>  >
>  > http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>  >
>  > BTW, if I can't something to work, I'm going to be forced to use the
> VBA programmatic Excel interface. That wouldn't be too bad, but the data
> comes from a DB and getting it properly positioned to use Excel's
> "Solver" is very painful.  A Python approach would be much cleaner.
>
> Are you able to use scipy? It has the simplex algorithm (among many
> others) in its optimize module:
> http://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html
>
> Oscar
>
  scipy would be another possibility of last resort.  I will take a 
look. Thanks.

[toc] | [prev] | [next] | [standalone]

#53465

On 2013-09-02 09:06, Oscar Benjamin wrote:
>
> On Sep 2, 2013 2:31 AM, "Tommy Vee" <xxxxx@xxxxxx.xxx> wrote:
>  >
>  > Anyone know where I can get an easy to use Python class or algorithm for the
> Simplex optimization algorithm?  I've tried the one in the link below, but I
> can't figure out if a) I'm using it properly, or b) where to get the solution.
>   BTW, I tried some test scenarios using MS Excel's "Solver" and just can't get
> this algorithm to match Excel's results (which is spot on).
>  >
>  > http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>  >
>  > BTW, if I can't something to work, I'm going to be forced to use the VBA
> programmatic Excel interface. That wouldn't be too bad, but the data comes from
> a DB and getting it properly positioned to use Excel's "Solver" is very painful.
>   A Python approach would be much cleaner.
>
> Are you able to use scipy? It has the simplex algorithm (among many others) in
> its optimize module:
> http://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html

Careful. Confusingly, there are two optimization algorithms known as "the 
simplex algorithm". The one the OP wants is for solving a linear programming 
problem (minimize a linear combination of variables subject to linear inequality 
constraints). The simplex algorithm that scipy implements is more properly 
termed "the Nelder-Mead simplex algorithm" for unconstrained local nonlinear 
minimization problems without derivative information.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco

[toc] | [prev] | [next] | [standalone]

#53468

On 2013-09-02 02:26, Tommy Vee wrote:
> Anyone know where I can get an easy to use Python class or algorithm for the
> Simplex optimization algorithm?  I've tried the one in the link below, but I
> can't figure out if a) I'm using it properly, or b) where to get the solution.
> BTW, I tried some test scenarios using MS Excel's "Solver" and just can't get
> this algorithm to match Excel's results (which is spot on).
>
> http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>
> BTW, if I can't something to work, I'm going to be forced to use the VBA
> programmatic Excel interface. That wouldn't be too bad, but the data comes from
> a DB and getting it properly positioned to use Excel's "Solver" is very
> painful.  A Python approach would be much cleaner.

Can you show some of the test scenarios that you tried? There are different 
conventions in how to represent a linear programming problem, and different 
solvers may choose different conventions. You may have to convert between 
representations.

You may have better luck with the PuLP interface:

   https://pypi.python.org/pypi/PuLP

PuLP itself is just a modelling language rather than a solver, but the sources 
do contain compiled binaries for the CoinMP solver so it will work out-of-box on 
popular platforms, like Windows.

   https://projects.coin-or.org/CoinMP

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco

[toc] | [prev] | [next] | [standalone]

#53493

On 9/2/2013 5:55 AM, Robert Kern wrote:
> On 2013-09-02 02:26, Tommy Vee wrote:
>> Anyone know where I can get an easy to use Python class or algorithm
>> for the
>> Simplex optimization algorithm?  I've tried the one in the link below,
>> but I
>> can't figure out if a) I'm using it properly, or b) where to get the
>> solution.
>> BTW, I tried some test scenarios using MS Excel's "Solver" and just
>> can't get
>> this algorithm to match Excel's results (which is spot on).
>>
>> http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>>
>> BTW, if I can't something to work, I'm going to be forced to use the VBA
>> programmatic Excel interface. That wouldn't be too bad, but the data
>> comes from
>> a DB and getting it properly positioned to use Excel's "Solver" is very
>> painful.  A Python approach would be much cleaner.
>
> Can you show some of the test scenarios that you tried? There are
> different conventions in how to represent a linear programming problem,
> and different solvers may choose different conventions. You may have to
> convert between representations.
>
> You may have better luck with the PuLP interface:
>
>    https://pypi.python.org/pypi/PuLP
>
> PuLP itself is just a modelling language rather than a solver, but the
> sources do contain compiled binaries for the CoinMP solver so it will
> work out-of-box on popular platforms, like Windows.
>
>    https://projects.coin-or.org/CoinMP
>

Thank you, I will definitely look at these and other options.  BTW, try 
the test scenario in the link I sent.  Very simple, only 3 variables.

Maximize:  2x+3y+2z

Constraints: 2x+y+z <=4, x+2y+z <=7, z <= 5

The algorithm displays the Tableau after each pivot, but where is the 
answer for x, y and z?

When I run this in Excel's Solver, I get x=0, y=3, z=1. which is indeed 
the maximized solution (11).

[toc] | [prev] | [next] | [standalone]

#53496

On 2013-09-02 16:06, Tommy Vee wrote:
> On 9/2/2013 5:55 AM, Robert Kern wrote:
>> On 2013-09-02 02:26, Tommy Vee wrote:
>>> Anyone know where I can get an easy to use Python class or algorithm
>>> for the
>>> Simplex optimization algorithm?  I've tried the one in the link below,
>>> but I
>>> can't figure out if a) I'm using it properly, or b) where to get the
>>> solution.
>>> BTW, I tried some test scenarios using MS Excel's "Solver" and just
>>> can't get
>>> this algorithm to match Excel's results (which is spot on).
>>>
>>> http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>>>
>>> BTW, if I can't something to work, I'm going to be forced to use the VBA
>>> programmatic Excel interface. That wouldn't be too bad, but the data
>>> comes from
>>> a DB and getting it properly positioned to use Excel's "Solver" is very
>>> painful.  A Python approach would be much cleaner.
>>
>> Can you show some of the test scenarios that you tried? There are
>> different conventions in how to represent a linear programming problem,
>> and different solvers may choose different conventions. You may have to
>> convert between representations.
>>
>> You may have better luck with the PuLP interface:
>>
>>    https://pypi.python.org/pypi/PuLP
>>
>> PuLP itself is just a modelling language rather than a solver, but the
>> sources do contain compiled binaries for the CoinMP solver so it will
>> work out-of-box on popular platforms, like Windows.
>>
>>    https://projects.coin-or.org/CoinMP
>>
>
> Thank you, I will definitely look at these and other options.  BTW, try the test
> scenario in the link I sent.  Very simple, only 3 variables.
>
> Maximize:  2x+3y+2z
>
> Constraints: 2x+y+z <=4, x+2y+z <=7, z <= 5
>
> The algorithm displays the Tableau after each pivot, but where is the answer for
> x, y and z?

You will have to read up on the Dantzig Simplex Algorithm to learn how to read 
off the results from the final tableau. My understanding is that you look at the 
columns representing the basic variables (in this case, the second, third, and 
fourth columns represent x, y, and z, respectively). If the column is all 0s 
except for a single 1, then the row with the 1 has the variable's value in the 
rightmost column. If the column has other values in it, then the variable's 
value is 0.

> When I run this in Excel's Solver, I get x=0, y=3, z=1. which is indeed the
> maximized solution (11).

The final tableau for this problem looks like this:

[[  1.   1.   0.   0.   1.   1.   0.  11.]
  [  0.   3.   0.   1.   2.  -1.   0.   1.]
  [  0.  -1.   1.   0.  -1.   1.   0.   3.]
  [  0.  -3.   0.   0.  -2.   1.   1.   4.]]

So, for x, we look in the second column and notice that it has a bunch of 
different values in it, so x=0.

For y, we look in the third column and see that it has its single 1 in the third 
row. Looking all the way on the right for that row, we get a 3.

For z, we look in the fourth column and see that it has its single 1 in the 
second row. Looking all the way on the right for that row, we get a 1.

So this solver does reproduce the result x=0, y=3, z=1. The maximized solution 
is in the upper-rightmost element of the tableau, 11.

Sound like a pain in the ass to code up that logic? It is. PuLP and other 
industrial grade solver interfaces won't make you go through this.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco

[toc] | [prev] | [next] | [standalone]

#53524

On 9/2/2013 11:43 AM, Robert Kern wrote:
> On 2013-09-02 16:06, Tommy Vee wrote:
>> On 9/2/2013 5:55 AM, Robert Kern wrote:
>>> On 2013-09-02 02:26, Tommy Vee wrote:
>>>> Anyone know where I can get an easy to use Python class or algorithm
>>>> for the
>>>> Simplex optimization algorithm?  I've tried the one in the link below,
>>>> but I
>>>> can't figure out if a) I'm using it properly, or b) where to get the
>>>> solution.
>>>> BTW, I tried some test scenarios using MS Excel's "Solver" and just
>>>> can't get
>>>> this algorithm to match Excel's results (which is spot on).
>>>>
>>>> http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>>>>
>>>> BTW, if I can't something to work, I'm going to be forced to use the
>>>> VBA
>>>> programmatic Excel interface. That wouldn't be too bad, but the data
>>>> comes from
>>>> a DB and getting it properly positioned to use Excel's "Solver" is very
>>>> painful.  A Python approach would be much cleaner.
>>>
>>> Can you show some of the test scenarios that you tried? There are
>>> different conventions in how to represent a linear programming problem,
>>> and different solvers may choose different conventions. You may have to
>>> convert between representations.
>>>
>>> You may have better luck with the PuLP interface:
>>>
>>>    https://pypi.python.org/pypi/PuLP
>>>
>>> PuLP itself is just a modelling language rather than a solver, but the
>>> sources do contain compiled binaries for the CoinMP solver so it will
>>> work out-of-box on popular platforms, like Windows.
>>>
>>>    https://projects.coin-or.org/CoinMP
>>>
>>
>> Thank you, I will definitely look at these and other options.  BTW,
>> try the test
>> scenario in the link I sent.  Very simple, only 3 variables.
>>
>> Maximize:  2x+3y+2z
>>
>> Constraints: 2x+y+z <=4, x+2y+z <=7, z <= 5
>>
>> The algorithm displays the Tableau after each pivot, but where is the
>> answer for
>> x, y and z?
>
> You will have to read up on the Dantzig Simplex Algorithm to learn how
> to read off the results from the final tableau. My understanding is that
> you look at the columns representing the basic variables (in this case,
> the second, third, and fourth columns represent x, y, and z,
> respectively). If the column is all 0s except for a single 1, then the
> row with the 1 has the variable's value in the rightmost column. If the
> column has other values in it, then the variable's value is 0.
>
>> When I run this in Excel's Solver, I get x=0, y=3, z=1. which is
>> indeed the
>> maximized solution (11).
>
> The final tableau for this problem looks like this:
>
> [[  1.   1.   0.   0.   1.   1.   0.  11.]
>   [  0.   3.   0.   1.   2.  -1.   0.   1.]
>   [  0.  -1.   1.   0.  -1.   1.   0.   3.]
>   [  0.  -3.   0.   0.  -2.   1.   1.   4.]]
>
> So, for x, we look in the second column and notice that it has a bunch
> of different values in it, so x=0.
>
> For y, we look in the third column and see that it has its single 1 in
> the third row. Looking all the way on the right for that row, we get a 3.
>
> For z, we look in the fourth column and see that it has its single 1 in
> the second row. Looking all the way on the right for that row, we get a 1.
>
> So this solver does reproduce the result x=0, y=3, z=1. The maximized
> solution is in the upper-rightmost element of the tableau, 11.
>
> Sound like a pain in the ass to code up that logic? It is. PuLP and
> other industrial grade solver interfaces won't make you go through this.
>
You nailed it.  Thanks for help.  And you're right.  This is too 
painful, I just read the PuLP doc and it may be a lot easier.

[toc] | [prev] | [next] | [standalone]

#53525

On 9/2/2013 11:43 AM, Robert Kern wrote:
> On 2013-09-02 16:06, Tommy Vee wrote:
>> On 9/2/2013 5:55 AM, Robert Kern wrote:
>>> On 2013-09-02 02:26, Tommy Vee wrote:
>>>> Anyone know where I can get an easy to use Python class or algorithm
>>>> for the
>>>> Simplex optimization algorithm?  I've tried the one in the link below,
>>>> but I
>>>> can't figure out if a) I'm using it properly, or b) where to get the
>>>> solution.
>>>> BTW, I tried some test scenarios using MS Excel's "Solver" and just
>>>> can't get
>>>> this algorithm to match Excel's results (which is spot on).
>>>>
>>>> http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>>>>
>>>> BTW, if I can't something to work, I'm going to be forced to use the
>>>> VBA
>>>> programmatic Excel interface. That wouldn't be too bad, but the data
>>>> comes from
>>>> a DB and getting it properly positioned to use Excel's "Solver" is very
>>>> painful.  A Python approach would be much cleaner.
>>>
>>> Can you show some of the test scenarios that you tried? There are
>>> different conventions in how to represent a linear programming problem,
>>> and different solvers may choose different conventions. You may have to
>>> convert between representations.
>>>
>>> You may have better luck with the PuLP interface:
>>>
>>>    https://pypi.python.org/pypi/PuLP
>>>
>>> PuLP itself is just a modelling language rather than a solver, but the
>>> sources do contain compiled binaries for the CoinMP solver so it will
>>> work out-of-box on popular platforms, like Windows.
>>>
>>>    https://projects.coin-or.org/CoinMP
>>>
>>
>> Thank you, I will definitely look at these and other options.  BTW,
>> try the test
>> scenario in the link I sent.  Very simple, only 3 variables.
>>
>> Maximize:  2x+3y+2z
>>
>> Constraints: 2x+y+z <=4, x+2y+z <=7, z <= 5
>>
>> The algorithm displays the Tableau after each pivot, but where is the
>> answer for
>> x, y and z?
>
> You will have to read up on the Dantzig Simplex Algorithm to learn how
> to read off the results from the final tableau. My understanding is that
> you look at the columns representing the basic variables (in this case,
> the second, third, and fourth columns represent x, y, and z,
> respectively). If the column is all 0s except for a single 1, then the
> row with the 1 has the variable's value in the rightmost column. If the
> column has other values in it, then the variable's value is 0.
>
>> When I run this in Excel's Solver, I get x=0, y=3, z=1. which is
>> indeed the
>> maximized solution (11).
>
> The final tableau for this problem looks like this:
>
> [[  1.   1.   0.   0.   1.   1.   0.  11.]
>   [  0.   3.   0.   1.   2.  -1.   0.   1.]
>   [  0.  -1.   1.   0.  -1.   1.   0.   3.]
>   [  0.  -3.   0.   0.  -2.   1.   1.   4.]]
>
> So, for x, we look in the second column and notice that it has a bunch
> of different values in it, so x=0.
>
> For y, we look in the third column and see that it has its single 1 in
> the third row. Looking all the way on the right for that row, we get a 3.
>
> For z, we look in the fourth column and see that it has its single 1 in
> the second row. Looking all the way on the right for that row, we get a 1.
>
> So this solver does reproduce the result x=0, y=3, z=1. The maximized
> solution is in the upper-rightmost element of the tableau, 11.
>
> Sound like a pain in the ass to code up that logic? It is. PuLP and
> other industrial grade solver interfaces won't make you go through this.
>
You nailed it.  Thanks for help.  And you're right.  This is too 
painful, I just read the PuLP doc and it may be a lot easier.

[toc] | [prev] | [next] | [standalone]

#53494

On 9/2/2013 5:55 AM, Robert Kern wrote:
> On 2013-09-02 02:26, Tommy Vee wrote:
>> Anyone know where I can get an easy to use Python class or algorithm
>> for the
>> Simplex optimization algorithm?  I've tried the one in the link below,
>> but I
>> can't figure out if a) I'm using it properly, or b) where to get the
>> solution.
>> BTW, I tried some test scenarios using MS Excel's "Solver" and just
>> can't get
>> this algorithm to match Excel's results (which is spot on).
>>
>> http://taw9.hubpages.com/hub/Simplex-Algorithm-in-Python
>>
>> BTW, if I can't something to work, I'm going to be forced to use the VBA
>> programmatic Excel interface. That wouldn't be too bad, but the data
>> comes from
>> a DB and getting it properly positioned to use Excel's "Solver" is very
>> painful.  A Python approach would be much cleaner.
>
> Can you show some of the test scenarios that you tried? There are
> different conventions in how to represent a linear programming problem,
> and different solvers may choose different conventions. You may have to
> convert between representations.
>
> You may have better luck with the PuLP interface:
>
>    https://pypi.python.org/pypi/PuLP
>
> PuLP itself is just a modelling language rather than a solver, but the
> sources do contain compiled binaries for the CoinMP solver so it will
> work out-of-box on popular platforms, like Windows.
>
>    https://projects.coin-or.org/CoinMP
>

Thank you, I will definitely look at these and other options.  BTW, try 
the test scenario in the link I sent.  Very simple, only 3 variables.

Maximize:  2x+3y+2z

Constraints: 2x+y+z <=4, x+2y+z <=7, z <= 5

The algorithm displays the Tableau after each pivot, but where is the 
answer for x, y and z?

When I run this in Excel's Solver, I get x=0, y=3, z=1. which is indeed 
the maximized solution (11).

[toc] | [prev] | [next] | [standalone]

#54241

On Sun, 01 Sep 2013 21:26:16 -0400, Tommy Vee wrote:

> comes from a DB and getting it properly positioned to use Excel's
> "Solver" is very painful.  A Python approach would be much cleaner.

Well, I dunno, download some open source spreadsheet thingy that gets it 
right (according to your definition). Then investigate its code. Or ask 
Bill for his. Though, I'm pretty sure I know what the answer will be.


 /Grrr
-- 
          ___                  ___
 (\_--_/)  | _ ._    _|_|_  _   |o _  _ ._
 ( 9  9 )  |(_)| |\/  |_| |(/_  ||(_|(/_|
 stripes are forever - as overripe ferrets

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web