The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Simplex Method Algorithm

Hi,

Can anyone here provide a reference to a link that would have a good description of source code or pseudo-code for the Simplex or revised Simplex method for solving optimization problems?

Thanks.
George H. Send private email
Monday, June 02, 2008
 
 
Surely it would have been quicker to type "Simplex algorithm" into Google than type out this post?

GIYF.
Odysseus Send private email
Monday, June 02, 2008
 
 
I have opened dozens of Google links to try to find this - without success. There are lots of links describing the Simplex method in terms of linear algebra; some even have code and code snippets, but I couldn't find one with pseudo code or even a well-commented code example.

I was hoping that perhaps somebody in this readership might know of something that Google, perhaps, does not.
George H. Send private email
Monday, June 02, 2008
 
 
MIT's web site might have something look under operations research.  Also Research and Education Associates had a book out called The Operations Research Problem Solver.  Excellent book to get some problems in that area and see them worked out step by step.

The difficult part for the Simplex method is formulating the constraints programatically.  Once you have the matrix set up the actual chugging through the steps isn't that difficult.  There are plenty of books and examples on doing matrix mathmatics.  I'm sure Knuth has something.  APL was great for this stuff, albeit difficult to read without a ton oc comments.

A friend of mine did write a system in Fortran using the Simplex method a couple of decades ago.  No, I don't have a copy of the code.  I'm not sure it would have done you much good since it was for a very specific application. (pricing and smoothing of 1 year renewable attained age term insurance)
Jim Send private email
Monday, June 02, 2008
 
 
One of the first links I found when STFW was:
http://lflemmer.wordpress.com/2007/04/07/a-c-implementation-of-the-nelder-mead-simplex-algorithm/
another was:
http://channel9.msdn.com/forums/Coffeehouse/260162-Spot-the-bug-C-Simplex-implementation/
I don't have time to determine how usable either is, and if I was going to use it for anything involving money, I'd probably have the company cough up for a serious math library.

The links on those posts are worth checking out.
Peter Send private email
Monday, June 02, 2008
 
 
Posting tip of the day: when you've searched google already, explain why the results were unsatisfactory so we can skip the "just search google you dumbass" posts and jump to the more helpful bits.

Monday, June 02, 2008
 
 
Thanks for the replies.

Jim,
The "The Operations Research Problem Solver" is an excellent book (I had already purchased it). It explains the math steps pretty well, but does not have any algorithms. I was hoping to find something already written before I tried writing from scratch. As you said, "formulating the constraints programatically" is a challenge. I'll check out Kunth and the MIT website to see if I can find anything there. I appreciate your helpful reply.

Peter,
Thanks for the links. While the first link isn't directly applicable, the Yahoo group it references might be. The other link is not that useful in that is buggy non-commented code. I'll post if I find something else down the line, so thank you.

No name,
This was my first post here. I would have guessed that people would have assumed that I had done a Google search before I asked the question here (which I had). I did not (still have not) found what I am looking for, although I appreciate the offered suggestions very much.

Google has not replaced domain expertise when it comes to extracting knowledge from information, and I think that is why groups like this are helpful. Perhaps it is just me, but I think that "GIYF", "STFW" and "just search google you dumbass" posts are basically condescending and disrespectful to people, such as myself, who are looking for a friendly place to ask questions and exchange ideas. I guess I have never believed in slapping someone's hand just because they raised it.

Again, perhaps it is just me.
George H. Send private email
Monday, June 02, 2008
 
 
I know this isn't much help, but I went through a similar search several years ago and didn't find anything. We even bought a white paper on developing solutions using the Simplex Algorithm but that was next to useless.

I ended up with my own optimisation algorithm that evolved over time. It's not perfect but then mine is less prone to local-minimum errors than the theoretical algorithm
Adrian
Tuesday, June 03, 2008
 
 
When you want high quality mathematics/numerical code, the first place to check is Netlib.

http://www.netlib.org/

Searching there found a number of simplex implementations.
Perl Solution
Tuesday, June 03, 2008
 
 
"Again, perhaps it is just me."

Yes, it's just you. Welcome to teh intarwebs.

Happens all the time, don't take it personally.
Herpes
Tuesday, June 03, 2008
 
 
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 29.3: The simplex algorithm, pp.790–804.

Tuesday, June 03, 2008
 
 
"and if I was going to use it for anything involving money, I'd probably have the company cough up for a serious math library."

You'd be surprised by how often "anything involving money" in numerics is coded very amateurishly.
quant dev Send private email
Thursday, June 05, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz