Talk:Simplex algorithm

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Systems, which collaborates on articles about the idea of systems. If you would like to help, you can edit this article or visit the project page, where you can join the project and/or contribute to the discussion.
???	This article has not yet received a rating on the assessment scale. [FAQ]
???	This article has not yet received an importance rating within Systems.
Help with this template Please rate this article, and then leave comments here to explain the ratings and/or to identify the strengths and weaknesses of the article.

1 Too technical
2 Other article with example
3 Unusual wording
4 Associating to other method
5 Algorithmic content
6 Move "Nelder-Mead simplex method" to an own article?
7 Category
8 Transposes
9 Shapes
10 Misleading
11 Observation
12 Basic Feasible Solution
13 simplex-method

[edit] Too technical

Right - this is a confusing article.

The Simplex Method is covered in an entire book by Hiller and Lieberman, "Introduction to Mathematical Programming". There is also an appendix on it in the FORTH edition of Gilbert Strang's "Linear Algebra and its Applications".

The Wikipedia guidelines ask that articles start at a High School level, and advance from there. Yet the Simplex Method is so sophisticated that Strang didn't cover it until recently.

Here's a suggestion -- how about starting with a description of The Transportation Problem, as a way of introducing the issue to the reader. That might help justify why there is an issue. Can anyone think of an easy example to help explain why the Simplex Method needs to exist?

Pattern finder 19:59, 27 June 2007 (UTC)

This article may be too technical for a general audience.
Please help improve this article by providing more context and better explanations of technical details to make it more accessible, without removing technical details.

I'd disagree with saying that the simplex method is sophisticated outright. The Standard Simplex Method is quite easily taught at a High School Level [in the UK at least], however an efficient computational implementation is involved and even books dedicated to the subject only touch on the techniques required. The presentation in this article seems to be from a pure Maths perspective.

Jdh41 (talk) 18:24, 18 January 2008 (UTC)

This article is very poor indeed. I know what the algorithm is about and still can't understand it. More detail, please?

[edit] Other article with example

Please can somebody help me? What happened to the page "Simplex algorithm method" that used to be linked from this page (at least it was on 4/1/07). I can't seem to find it any more and it provided me with a very useful example!

[edit] Unusual wording

My apologies but me not understand

"while having no polynomial time worst-case complexity implementation"... (last-but-one paragraph).

Is it possible to enhance this sentence? Thanks. Pfortuny 09:22, 19 Apr 2004 (UTC)

Last paragraph also speaks about

"much better computational complexity"

which for me sounds weird. Pfortuny 09:27, 19 Apr 2004 (UTC)

[edit] Associating to other method

To the anonymous editor from IP-address 4.250.xxx.xxx: I don't understand why you want to associate Dantzig's method to mathematical optimization and the other simplex method, with which you have apparently some experience, with computer programming. Surely both methods are part of mathematical optimization, since they both solve optimization problems. Similarly, both methods are part of computer programming, since they can be programmed on a computer. -- Jitse Niesen 18:38, 10 Jan 2005 (UTC)

I associate "Dantzig's method to mathematical optimization" with "the other simplex method" because the documentation I read in order to fulfill the customer's request for implementing the simplex method optimization was derived by computation scientists (not me, I just implemented their algorithms in 6809 assembly code) from what appears to my eyes as what you descibe as "Dantzig's method to mathematical optimization". As I did this around 1985, I no longer recall the exact materials I read. In any case, I'll make no reverts to the current article. Cheers from user 4.250.xxx.xxx

[edit] Algorithmic content

This article speaks a lot "about the algorithm", but very little about how the algorithm actually works. I've therefore added an "algorithm" stub-section in which I'll try to add some content over the next week. "Terminology" and "running time" sections should probably also be added. --Fredrik Orderud 08:33, 19 August 2005 (UTC)

[edit] Move "Nelder-Mead simplex method" to an own article?

May I suggest moving the "Nelder-Mead simplex method" to an own article? Based on the fact that [1] claims that this method it "totally different". --Fredrik Orderud 18:44, 19 August 2005 (UTC)

Please do. The methods are indeed very different. -- Jitse Niesen (talk) 18:53, 19 August 2005 (UTC)

Ok, I will. What about naming the article "Nelder-Mead method", and of course add a link from the existing simplex article. --Fredrik Orderud 19:32, 19 August 2005 (UTC)

All "Nelder-Mead" content is now moved to Nelder-Mead method. Feel free to rename the article if you prefer another name:) --Fredrik Orderud 19:46, 19 August 2005 (UTC)

Excellent. I replaced the redirects at Nelder-Mead simplex method, downhill simplex method and downhill simplex to go to the new articles. In case you didn't know: You can find the redirects by clicking on the "What links here" link to the left. -- Jitse Niesen (talk) 20:34, 19 August 2005 (UTC)

Thanks a lot! I'll keep that in mind next time I create a new article. --Fredrik Orderud 20:56, 19 August 2005 (UTC)

[edit] Category

My reversion has been reverted by myself. I didn't realise that combinatorial optimization was a subcat of optimisation algorithms - the article didn't say anything about it, so it seemed like it was a move to a completely different part of mathematics which didn't make any sense. I apologise for any hurt to Mikkalai for the reversion of his edit. enochlau (talk) 06:02, 28 January 2006 (UTC)

[edit] Transposes

In the Problem Input section, shouldn`t it be the transpose of -c, and not -c? Perhaps I am missing something, in which case I apologize. --Tomas

[edit] Shapes

The article states "a simplex, which is a polytope of N + 1 vertices in N dimensions: a triangle on a line, a pyramid on a plane, a tetrahedron in three-dimensional space". I would think that in 1 dimension (on a line) the simplex would be a Line segment, on a plane it would be a triangle. I agree about the tetrahedron part in 3D space. Am I wrong? Odedee 17:33, 18 May 2007 (UTC)

You're absolutely right, thanks. I changed the description in the article. -- Jitse Niesen (talk) 08:41, 19 May 2007 (UTC)

[edit] Misleading

This article is not very accurate. When the author refers to "limited applications," that is at least misleading. Every method has limited application, so I can't argue with the literal accuracy. Also, linearity is often not a good approximation to some situations, but LP and modern variations of the simplex method have been used to solve problems in the "real world" for more than half a century. In fact, that was its original driving force.

Historically, the simplex method accounted for the second-most computer time, just after sorting. As we entered 2000, Computing in Science & Engineering, a publication of The Computer Society, named the simplex method of linear programming one of the top 10 algorithms of the millennium.

To say that the simplex method has limited applications is to misdirect the reader. Furthermore, the author would serve Wikipedia better with better references.

-- Harvey J. Greenberg

That was added recently (to avoid any misunderstanding, the article is not written by one person). I agree the article shouldn't say that. I have more issues with the added text, so I removed it. I also added the reference you mentioned. I would be very grateful indeed if you could add more to the article or rewrite parts; the article could certainly use the attention of somebody who knows about optimization. -- Jitse Niesen (talk) 19:58, 1 November 2007 (UTC)

[edit] Observation

Just a general observation: I was looking for a refresher on the algorithm and my head instantly started to hurt when I looked at this article. From a technical perspective it is very well written but from an educational perspective it has a very steep curve for somebody who has not been recently studying the subject matter and who is not already accustomed to these notational conventions. Ideally it should at least introduce the algorithm in a somewhat more accessible way. The texts I had in college introduced this starting with a simple system of equations and then gradually got into the more general but less intuitive mathematical formulations.

--Mcorazao (talk) 22:45, 12 December 2007 (UTC)

[edit] Basic Feasible Solution

According to my reading of [2], a basic feasible solution is one which has as many zeros as possible, but also is feasible (as otherwise it wouldn't lie on a boundary of the simplex). The initial basic feasible solution given in the article ( $\mathbf{x}_{s\,i} = \mathbf{b}_{i}$ ) fails the sign constraint on the $\mathbf{x}_{s\,i}$ if any of the $\mathbf{b}_{i}$ are negative, as would seem to be implied could happen by the text of the Linear_programming article.