Talk:Simplex algorithm/Archive 1

Archive 1

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)

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)

simplex-method

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

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)

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)

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)

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

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)

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)

b is only assumed to be nonnegative after the problem is put into standard form; part of the method consists of turning a general problem into an equivalent problem in standard form. When it does need to be stated the usual practice is to write b≥0.--RDBury (talk) 15:13, 6 January 2012 (UTC)

History

I think that this page lacks a 'History' section. For instance, I could not find the year in which this algorithm is invented. — Preceding unsigned comment added by 130.161.210.93 (talk) 10:20, 15 February 2012 (UTC)

This article in New Scientist would be a useful reference. Drop a note on my talk page and I can send you a pdf. SmartSE (talk) 19:36, 15 August 2012 (UTC)

For me, it's unclear why the algorithm is called "Dantzig's" and "suggested by T. S. Motzkin" at the same time. And Kantorovich's contribution is not described at all (while he got Nobel prize for works in this area). Maxal (talk) 18:14, 17 December 2012 (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)

By the definition of standard form constraints, we must have all $b_{i}\geq 0$, so all basic variables will be non-negative. The article forgot to include a step in the conversion to standard form that negates all rows with negative $b$ entries - it should probably be updated in my opinion. Once we begin with standard form constraints, the algorithm ensures that the $b$ entries will never go negative (see the part on the choice of pivot row).Vinzklorthos (talk) 17:27, 15 February 2014 (UTC)

Why the initial column in the tableau?

I'm talking about the 1 followed by the 0s. This column seems unnecessary. It never changes, and seems to have no effect on the outcome of the algorithm. For instance, pivoting never occurs there. Are there any negative consequences of leaving that column out?Vinzklorthos (talk) 02:22, 16 February 2014 (UTC)

Its purpose is more or less expositional. One example of its use is that when you have separated the basic variables from the nonbasic variables as in

${\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{N}^{T}&0\\&\mathbf {B} &\mathbf {N} &\mathbf {b} \end{bmatrix}}{\text{,}}$

the pricing out operation mentioned in #Canonical tableaux is simply premultiplying the tableau with

${\begin{bmatrix}1&-\mathbf {c} _{B}^{T}\\&\mathbf {B} \end{bmatrix}}^{-1}{\text{.}}$

This is a more compact description than the current text. Kxx (talk | contribs) 18:11, 6 March 2014 (UTC)

Inaccuracy in the intro?

The intro reads: "There is a simple characterization of the extreme points or vertices of this polytope, namely x = (x_1,\, \dots,\, x_n) is an extreme point if and only if the subset of column vectors A_i corresponding to the nonzero entries of x (x_i \ne 0) are linearly independent."

I think this only applies once we brought the problem to standard form, not for the form given in the intro. — Preceding unsigned comment added by 89.133.136.242 (talk) 15:59, 7 October 2015 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Simplex algorithm/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Two important, missing pieces of information: first, this article doesn't mention the idea of a degenerate basis at all. (It does link to Bland's rule, but only at the end, and with no mention of the word degeneracy, so it would be hard for a reader to figure out what Bland's rule is good for.) Second, there have been some recent nice results using smoothed analysis to analyze the complexity of simplex: http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf http://www-math.mit.edu/~spielman/simplex/ http://math.mit.edu/~spielman/SmoothedAnalysis/index.html The first link above (Kelner & Spielman) shows that there is a randomized version of simplex which runs in (randomized) polynomial time, answering a long-standing open question. Finally, another important open question is whether there are any strongly polynomial algorithms for solving LPs; it might be worth mentioning this question too.

Last edited at 15:30, 20 March 2009 (UTC). Substituted at 06:14, 30 April 2016 (UTC)

Standard form section doesn't conclude with matching standard form previous section

It's disappointing that the Standard Form section ends with $\mathbf {A} \mathbf {x} =\mathbf {b} ,\mathbf {x} \geq \mathbf {0}$ while the previous section writes that standard form is $\mathbf {A} \mathbf {x} \geq \mathbf {b} ,\mathbf {x} \geq \mathbf {0} ,\mathbf {b} \geq \mathbf {0}$ Mangledorf (talk) 22:47, 6 April 2015 (UTC)

Reading through the article, it looks to me as though the two instances of $\mathbf {A} \mathbf {x} \leq \mathbf {b} ,x_{i}\geq \mathbf {0}$ in the first section could be changed to $\mathbf {A} \mathbf {x} =\mathbf {b} ,x_{i}\geq \mathbf {0}$ without causing issues elsewhere. This would also fix the problem raised in the Talk section "Inaccuracy in the intro?".

Does anyone see a problem with this change? Bowmannat (talk) 16:36, 1 December 2016 (UTC)

Switching between maximization and minimization

The Overview section is written as though the algorithm is for maximization, but the Algorithm and "Finding an initial canonical tableau" work with minimization. There is a brief mention in the Algorithm section that maximization and minimization are easily converted to one another, but it still seems like a possible source of confusion.

An easy fix would be to replace references to maximization with minimization in the Overview. To be consistent with other sources, though, it is probably better to leave the maximization as-is and change the examples also to use maximization, but that would be more difficult. — Preceding unsigned comment added by Bowmannat (talk • contribs) 16:54, 1 December 2016 (UTC)

Definition basic feasible solution

This definition doesn't make sense to me:

$x=(x_{1},\,\dots ,\,x_{n})$ is an extreme point if and only if the subset of column vectors $A_{i}$ corresponding to the nonzero entries of x $(x_{i}\neq 0)$ are linearly independent.

That means if $x$ is a solution, so would be ${\frac {x}{2}}$. For a solution to be an extreme point, wouldn't it also be necessary that $Ax=b$? 77.180.179.6 (talk) 22:01, 18 March 2017 (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)

History section should be moved.

It should be moved above and made the first section after the lead for a more logical flow of the article. Hmanburg (talk) 14:00, 18 September 2020 (UTC)

I've decided to move it, do let me know incase it isn't appropriate. Hmanburg (talk) 14:00, 18 September 2020 (UTC)