Talk:Simplex algorithm

Smoothed anaylsis

It's nice to mention smoothed analysis in this article, but it needs to be related back to the Simplex algorithm. What results are there for this algorithm under smoothed analysis? Why is it mentioned at all? Danadocus (talk) 19:59, 9 November 2009 (UTC)

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) {{Technical}}

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?

Amazing. This is a very nicely written article. The tag is completely unjustified. There is no reason to start with the transportation problem. This article's purpose is to explain the simplex algorithm, not justify the field of linear programming. --C S (talk) 06:32, 14 August 2008 (UTC)

I have absolutely no idea what the article tries to convey. Therefore, it is not a good introductory explanation of the simplex algorithm. With that, the tag is justified. 84.82.170.167 (talk) 23:28, 9 February 2009 (UTC)

We certainly cannot say a technical tag is justified base on you not being able to understand it. By that reasoning, we should add technical tags to almost all math articles on Wikipedia, as most of my students cannot understand them. Also by that reasoning, I'm justified in adding tags to Ring (computer security), a subject you apparently know about, because I can't make heads or tails of it. Now if you were to explain what your background is and why you aren't able to understand the article, then we might have something.

As for your tagging, you apparently can't be bothered to read the instructions. Technical tags go on the talk page, not the article itself. Context tags are also for articles with insufficient context, which there is here in the first several sentences, regardless of whether you can understand the rest of the article. Frivolous tagging such as this only adds to the workload of people trying to improve the articles. We certainly don't need to spend all our time turning one article like this into a masterpiece of exposition for people who don't even know basic linear algebra or linear programming (if this is the case with you). Those people are better off reading the linear algebra article first, and then the article on linear programming. --C S (talk) 00:13, 10 February 2009 (UTC)

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! — Preceding unsigned comment added by 171.159.33.4 (talk • contribs) 4. jun 2007, 16:02‎

Is this still relevant? Anyway - the old page Simplex algorithm method has been merged into the Simplex algorithm article. An old revision of the former can be reached here. --mgarde (talk) 20:25, 4 December 2011 (UTC)

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)

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

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)

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)

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)

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

Simplexes

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)

The article states "The region is either empty, unbounded, or a convex polytope, also known as a simplex," and later continues to refer to general polytopes as simplexes. But a simplex is only a very special case of a convex polytope. Unless I'm missing something, this needs correction. And if so, it raises the question of why the method is called the Simplex Method rather than the Polytope Method. --Roy W. Wright (talk) 16:13, 28 December 2008 (UTC)

Roy: You're completely correct. While a simplex is a convex polytope, a convex polytope is not necessarily a simplex. It's called the simplex method because it acts on simplexes, not on general convex polytopes. --User: Jon Kleid

Okay, Jitse has addressed my concerns about the article itself in his edit. As for the name, am I correct to think that it comes from the fact that during each iteration in solving an $n$-dimensional problem, the algorithm chooses between $n+1$ corner-point feasible solutions? --Roy W. Wright (talk) 16:42, 16 January 2009 (UTC)

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)

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)

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.

-- 67.171.65.20 (talk) 03:24, 13 March 2008 (UTC)

Your writing shows a misunderstanding, which may be due to the article you mention---I didn't check it. In general, basic feasible solutions can have different numbers of zeros; maximizing the number of nonzeros would be a difficult combinatorial problem, I believe. Kiefer.Wolfowitz (talk) 17:26, 29 December 2009 (UTC)

The problem of minimizing the number of non-zero entries has unfortunately become known as the so-called $\ell _{0}$-minimization problem, despite this terminology being used for the F-space of sequences with F–norm $(x_{n})\mapsto \sum _{n}{2^{-n}x_{n}/(1+x_{n})}$, which is discussed by Stefan Rolewicz in Metric Linear Spaces, etc. Kiefer.Wolfowitz (talk) 02:39, 21 November 2010 (UTC)

simplex-method

Simplex-method is mistaken.78.36.176.198 (talk) 19:03, 8 May 2008 (UTC)Shlovikov Vadim.

Inconsistent use of terms "basic variable" and "non-basic variables"

I'm referring to the itemisation block after "The simplex algorithm goeas as follows" in the "Algorithm" section.

In the first item, the author defines the term non-basic variables to be the n variables of the n+p variables in (x, x_s) that are zero at a vertex. In the next item he talks of n basic variables which should be p in my opinion. The third item speaks of "increasing the value of one of the basic variables, while keeping all n-1 others to zero". It should be non-basic variables there, I think.

Summarising, I think this whole section needs revision, if I am correct with my critics.

Tobiaslangner (talk) 10:28, 15 October 2009 (UTC)

These are errors. The phrasing "zero at a vertex" is confusing imho. Indeed, a basic variable may be zero; non-basic variables must be zero. Kiefer.Wolfowitz (talk) 18:25, 29 December 2009 (UTC)

I think I've fixed the errors. Could someone look it over? Inframaut (talk) 01:45, 18 February 2010 (UTC)

Picture

Would somebody donate a better graphic image? (The present graph looks 2-dimensional. I suppose it represents a 3-dimensional polytope. However, in 2-dimensions, the simplex-path doesn't look compatible with any one cost-vector.) Thanks, Kiefer.Wolfowitz (talk) 12:03, 20 June 2010 (UTC)

Simplex geometry of Dantzig

Dantzig's first textbook has a discussion of the third (simplicial) geometry of the Simplex algorithm. This simplicial geometry is also discussed in the following article by Craig Tovey and Richard E. Stone:

• Stone, Richard E.; Tovey, Craig A. The simplex and projective scaling algorithms as iteratively reweighted least squares methods. SIAM Rev. 33 (1991), no. 2, 220–237. MR1124362
• Stone, Richard E.; Tovey, Craig A. Erratum: "The simplex and projective scaling algorithms as iteratively reweighted least squares methods. SIAM Rev. 33 (1991), no. 3, 461. MR1124362

Thanks, Kiefer.Wolfowitz (talk) 02:29, 21 November 2010 (UTC)

References

This article should identify the paper in which Dantzig introduced the simplex method. —Preceding unsigned comment added by Jfgrcar (talk • contribs) 19:47, 5 December 2010 (UTC)

Problem in Overview section

The Overview section seems to imply, though not in so many words, that a linear function on an intersection of hyperplanes has its maximum value on a vertex if it has one at all. But it's easy to construct examples of intersections of half planes with vertices at all with objective functions that have maximum values. The assumption that the LP is in standard form puts conditions on the feasible region which guarantee the existence of vertices and without this the simplex method could not be applied. If there are no objections, I'd like to reword the overview so that the standard form assumption is in at the beginning since without it the algorithm wouldn't work.--RDBury (talk) 23:13, 15 December 2010 (UTC)

You said "The assumption that the LP is in standard form puts conditions on the feasible region which guarantee the existence of vertices", which is not strictly true. An inconsistent system is still possible here, and would have no vertex. Regardless, starting with standard form seems good pedagogically. 24.220.188.43 (talk) 07:51, 1 May 2011 (UTC)

The feasible region is a convex polyhedral set, perhaps empty. A nonempty feasible set has a Steinitz decomposition as the Minkowski sum of a convex polytope and a convex polyhedral cone.

In Papadimitriou and Steiglitz, a number-theoretic algorithm is given for imposing a bound on the algebraic size (height) of integer/rational solutions of some feasible solutions, despite the unboundedness of any polyhedra, which allows a simplification of exposition (i.e., we may assume that we are working with (bounded) convex polytopes) when the data are rational.  Kiefer.Wolfowitz 09:43, 1 May 2011 (UTC)

When solving Phase1 problem you are not allowed to pivot the 2nd row

The Phase I problem example does not emphasize that you are not allowed choose the 2nd row, because it would corrupt the original objective function. The minimum ratio test for the 2nd row is always 0.

85.66.106.222 (talk) 18:05, 2 June 2011 (UTC) Calmarius

row vectors independent, not column vectors

Please check the paragraph that says " ... is an extreme point if and only if the column vectors $\scriptstyle A_{i}$, where $\scriptstyle x_{i}\,\neq \,0$, are linearly independent...".

It is obvious that it should be the "row vectors" that should be linearly independent, not the "column vectors" per the conventions used in this article. — Preceding unsigned comment added by 147.8.182.107 (talk) 12:15, 4 January 2012 (UTC)

I added the paragraph and I just double checked it and it seems ok. It's not saying all columns are l.i., just the ones for x_i>0 at the vertices of the polytope. For example, take A=(1 2) and b=1, so the polytope is the line segment x+2y=1, x,y≥0. For interior points the two columns are (1) and (2) which are l.d. and for an endpoint there is a single column (1) or (2) which is l.i. by itself. It's a bit non-intuitive but it's also elegant.--RDBury (talk) 15:03, 4 January 2012 (UTC)

non-negativity of $\mathbf {b}$

I think the article assumes that $\mathbf {b}$ is non-negative throughout the text. But this assumption is not made explicit. I have attempted to amend this by adding a few formulas, saying that $\scriptstyle b_{j}\geq 0\;\forall j$. 147.8.182.48 (talk) 12:25, 6 January 2012 (UTC)