Content deleted Content added
then -> than |
External links: add Archive.org link to simplex-m |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 2:
{{about|the linear programming algorithm|the non-linear optimization heuristic|Nelder–Mead method}}
<!-- {{Context|date=March 2012}} -->
In [[optimization (mathematics)|mathematical optimization]], [[George Dantzig|Dantzig]]'s '''simplex algorithm''' (or '''simplex method''') is a popular [[algorithm]] for [[linear programming]].<ref name="Murty">{{cite book |last=Murty |first=Katta G. |author-link=Katta G. Murty |year=2000 |title=Linear programming |publisher=John Wiley & Sons |url=http://www.computer.org/csdl/mags/cs/2000/01/c1022.html}}</ref>{{failed verification|date=June 2025|reason=Could not locate reference.}}
The name of the algorithm is derived from the concept of a [[simplex]] and was suggested by [[Theodore Motzkin|T. S. Motzkin]].<ref name="Murty22" >{{harvtxt|Murty|1983|loc=Comment 2.2}}</ref> Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial ''[[cone (geometry)|cone]]s'', and these become proper simplices with an additional constraint.<ref name="Murty39">{{harvtxt|Murty|1983|loc=Note 3.9}}</ref><ref name="StoneTovey">{{cite journal|last1=Stone|first1=Richard E.|last2=Tovey|first2=Craig A.|title=The simplex and projective scaling algorithms as iteratively reweighted least squares methods|journal=SIAM Review|volume=33|year=1991|issue=2|pages=220–237
Line 293:
</ref>
In 2014, it was proved{{citation-needed|date=January 2024}} that a particular variant of the simplex method is [[NP-mighty]], i.e., it can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm's execution. Moreover, deciding whether a given variable ever enters the basis during the algorithm's execution on a given input, and determining the number of iterations needed for solving a given problem, are both [[NP-hardness|NP-hard]] problems.<ref>{{Cite journal|last1=Disser|first1=Yann|last2=Skutella|first2=Martin|date=2018-11-01|title=The Simplex Algorithm Is NP-Mighty|journal=ACM Trans. Algorithms|volume=15|issue=1|pages=5:1–5:19|doi=10.1145/3280847|issn=1549-6325|arxiv=1311.5935|s2cid=54445546}}</ref> At about the same time it was shown that there exists an artificial pivot rule for which computing its output is [[PSPACE-complete]].<ref>{{Citation | last1 = Adler | first1 = Ilan|author1-link=Ilan Adler | last2 = Christos | first2 = Papadimitriou | author2-link = Christos Papadimitriou | last3 = Rubinstein | first3 = Aviad | title = Integer Programming and Combinatorial Optimization | chapter = On Simplex Pivoting Rules and Complexity Theory | volume = 17 | pages = 13–24 | year = 2014 | arxiv = 1404.3320 | doi = 10.1007/978-3-319-07557-0_2| series = Lecture Notes in Computer Science | isbn = 978-3-319-07556-3 | s2cid = 891022 }}</ref> In 2015, this was strengthened to show that computing the output of Dantzig's pivot rule is [[PSPACE-complete]].<ref>{{Citation | last1 = Fearnly | first1 = John | last2 = Savani | first2 = Rahul | title = Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | chapter = The Complexity of the Simplex Method | pages = 201–208 | year = 2015 | arxiv = 1404.0605 | doi = 10.1145/2746539.2746558| isbn = 9781450335362 | s2cid = 2116116 }}</ref>
===Efficiency in practice===
Line 343:
* [http://math.uww.edu/~mcfarlat/s-prob.htm Example of Simplex Procedure for a Standard Linear Programming Problem] by Thomas McFarland of the University of Wisconsin-Whitewater.
* [http://www.phpsimplex.com/simplex/simplex.htm?l=en PHPSimplex: online tool to solve Linear Programming Problems] by Daniel Izquierdo and Juan José Ruiz of the University of Málaga (UMA, Spain)
* [
{{Optimization algorithms|convex}}
| |||