Talk:Simplex algorithm

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

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

Simplex overview verification

Resolved

I am not sure of this mathematical statement in the overview.

"It can also be shown that, if an extreme point is not a maximum point of the objective function, then there is an edge containing the point so that the objective function is strictly increasing on the edge moving away from the point."

Since degeneracy can cause a stalling effect, it is possible to find a descent direction where the objective value is not increased, but is still a valid direction. Thus, I doubt the term "strictly", and I don't know how it would need to be phrased since it is only an overview of the algorithm. On another note, do we say that the objective value is increased, or objective function? Raphaelbwiki (talk) 22:33, 26 January 2021 (UTC)

Response: I believe the statement you've quoted is technically true, with the geometric interpretation of "extreme point" and "edge". That is, an extreme point is a point that is the intersection of the feasible region with some supporting hyperplane, and an edge is a line segment that is the intersection of the feasible region with some supporting hyperplane. On the other hand, if one interprets "extreme point" as a "basic feasible solution" (which is what the Simplex algorithm works with, rather than points per se), then you are right that there might not be an edge (in the sense of an exchange of two variables leading to a neighboring basic feasible solution) that strictly increases the objective function, even if the basic feasible solution is not a maximum of the objective (because of the degeneracy that you mention, by which many basic feasible solutions may all represent the same extreme point. Nealeyoung (talk) 01:30, 29 April 2021 (UTC)

@Nealeyoung: You're right! Stalling does not affect the geometric point of view of the statement, thus it is correct. Marking this thread as resolved. Raphaelbwiki (talk) 13:43, 18 June 2021 (UTC)

Reference needed for statement about Baire Category

In this 2011 edit (https://en.wikipedia.org/w/index.php?title=Simplex_algorithm&type=revision&diff=420535791&oldid=420516031), user Kiefer.Wolfowitz ([1], not active as of April 2021) introduced the statement "Another approach to studying typical phenoma uses Baire category theory from general topology, and to show that (topologically) "most" matrices can be solved by the simplex algorithm in a polynomial number of steps." This statement has been questioned on cstheory.stackexchange.com here: https://cstheory.stackexchange.com/questions/48850/using-baire-category-to-analyze-the-efficiency-of-the-simplex-method , with no clarification as of April 2021. From a quick google scholar search, I don't find any research mentioning (much less explaining) anything about the Simplex algorithm and Baire Category theory (except a 2015 online article that appears to be plagiarized from the Wikipedia page). I suggest that either a suitable reference be found and added, or, if none can be found, that the statement be removed. Nealeyoung (talk) 01:36, 29 April 2021 (UTC)

Agreed. I am quite familiar with the literature on analysis of the simplex method, and nothing I have seen outside of this article makes any mention of Baire category theory. Shuiberts (talk) 11:43, 29 April 2021 (UTC)

Confusing example

The example of the pivot operation states:

"Columns 2, 3, and 4 can be selected as pivot columns, for this example column 4 is selected. The values of z resulting from the choice of rows 2 and 3 as pivot rows are 10/1 = 10 and 15/3 = 5 respectively. Of these the minimum is 5, so row 3 must be the pivot row."

The earlier statement on the pivot operation reads:

"The row containing this element is multiplied by its reciprocal to change this element to 1.."

But in the example after the pivot, the value at row 3, column 4 is 3, not 1.

Hyphz (talk) 19:15, 1 November 2021 (UTC)

It seems that all of the elements of the tableau have been scaled by three without saying. This appears to have been done to coerce it as a canonical form. The example could write a big ${\frac {1}{3}}$ to the left of the tableau and indicate this has been done. An alternative could be to put a denominator of 3 below all of the elements, but that wouldn't look great. I was quite confused by this example. As I am new to wikipedia and linear programming I don't feel confident making an edit until I'm absolutely sure of what I'm doing. Phebenet (talk) 23:47, 23 October 2023 (UTC)