Network simplex algorithm - Revision history

DancingOwl: reference about performance

2024-11-16T19:52:09Z

reference about performance

← Previous revision		Revision as of 19:52, 16 November 2024
Line 1:		Line 1:
	In [[mathematical optimization]], the '''network simplex algorithm''' is a [[graph theory\|graph theoretic]] specialization of the [[simplex algorithm]]. The algorithm is usually formulated in terms of a [[minimum-cost flow problem]]. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.{{~~citation~~ ~~needed~~\|~~date~~=~~May~~ ~~2015~~}}		In [[mathematical optimization]], the '''network simplex algorithm''' is a [[graph theory\|graph theoretic]] specialization of the [[simplex algorithm]]. The algorithm is usually formulated in terms of a [[minimum-cost flow problem]]. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.<ref>{{Cite book \| last1=Bazaraa \| first1=Mokhtar S. \| last2=Jarvis \| first2=John J. \| last3=Sherali \| first3=Hanif D. \| year=2010 \| title=Linear Programming and Network Flows \| edition=4th \| publisher=Wiley \| page=453}}</ref>

	== History ==		== History ==

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:57:23Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:57, 12 October 2024
Line 39:		Line 39:
	[[Category:Network theory]]		[[Category:Network theory]]
	[[Category:Polynomial-time problems]]		[[Category:Polynomial-time problems]]
	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]
	[[Category:Computational problems in graph theory]]		[[Category:Computational problems in graph theory]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:24:36Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:24, 12 October 2024
Line 39:		Line 39:
	[[Category:Network theory]]		[[Category:Network theory]]
	[[Category:Polynomial-time problems]]		[[Category:Polynomial-time problems]]
	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]
	[[Category:Computational problems in graph theory]]		[[Category:Computational problems in graph theory]]

Citation bot: Alter: chapter-url. URLs might have been anonymized. Add: s2cid. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 129/2200

2021-12-03T13:45:50Z

Alter: chapter-url. URLs might have been anonymized. Add: s2cid. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 129/2200

← Previous revision		Revision as of 13:45, 3 December 2021
Line 2:		Line 2:

	== History ==		== History ==
	For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available. In 1995 [[James B. Orlin\|Orlin]] provided the first polynomial algorithm with runtime of <math>O(V^2 E \log(VC))</math> where <math>C</math> is maximum cost of any edges.<ref>{{Cite journal\|title = A polynomial time primal network simplex algorithm for minimum cost flows\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 109–129\|volume = 78\|issue = 2\|doi = 10.1007/BF02614365\|first = James B.\|last = Orlin\|hdl = 1721.1/2584\|hdl-access = free}}</ref> Later [[Robert Tarjan\|Tarjan]] improved this to <math>O(VE \log V \log(VC))</math> using [[dynamic trees]] in 1997.<ref>{{Cite journal\|title = Dynamic trees as search trees via euler tours, applied to the network simplex algorithm\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 169–177\|volume = 78\|issue = 2\|doi = 10.1007/BF02614369\|first = Robert E.\|last = Tarjan}}</ref> Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.<ref>{{citation		For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available. In 1995 [[James B. Orlin\|Orlin]] provided the first polynomial algorithm with runtime of <math>O(V^2 E \log(VC))</math> where <math>C</math> is maximum cost of any edges.<ref>{{Cite journal\|title = A polynomial time primal network simplex algorithm for minimum cost flows\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 109–129\|volume = 78\|issue = 2\|doi = 10.1007/BF02614365\|first = James B.\|last = Orlin\|hdl = 1721.1/2584\|s2cid = 3107792\|hdl-access = free}}</ref> Later [[Robert Tarjan\|Tarjan]] improved this to <math>O(VE \log V \log(VC))</math> using [[dynamic trees]] in 1997.<ref>{{Cite journal\|title = Dynamic trees as search trees via euler tours, applied to the network simplex algorithm\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 169–177\|volume = 78\|issue = 2\|doi = 10.1007/BF02614369\|first = Robert E.\|last = Tarjan\|s2cid = 18977577}}</ref> Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.<ref>{{citation
	\| last1 = Orlin \| first1 = James B. \| author1-link = James B. Orlin		\| last1 = Orlin \| first1 = James B. \| author1-link = James B. Orlin
	\| last2 = Plotkin \| first2 = Serge A.		\| last2 = Plotkin \| first2 = Serge A.
Line 12:		Line 12:
	\| pages = 255–276		\| pages = 255–276
	\| title = Polynomial dual network simplex algorithms		\| title = Polynomial dual network simplex algorithms
	\| volume = 60\| citeseerx = 10.1.1.297.5730 }}</ref>		\| volume = 60\| citeseerx = 10.1.1.297.5730 \| s2cid = 5838223 }}</ref>

	== Overview ==		== Overview ==
Line 18:		Line 18:

	== Applications ==		== Applications ==
	The network simplex algorithm can be used to solve many practical problems including,<ref>{{Cite book\|title = Linear Programming\|last = Chvatal\|first = Vasek\|publisher = Macmillan\|year = 1983\|isbn = 9780716715870\|pages = [https://archive.org/details/linearprogrammin00chv/page/320 320–351]\|chapter = 20\|chapter-url = https://books.google.com/books?id=DN20_tW_BV0C~~&lpg=PA320&ots=4eHDEubUhH~~&dq=network%20simplex%20applications&pg=PA320~~#v=onepage&q&f=false~~\|url = https://archive.org/details/linearprogrammin00chv/page/320}}</ref>		The network simplex algorithm can be used to solve many practical problems including,<ref>{{Cite book\|title = Linear Programming\|last = Chvatal\|first = Vasek\|publisher = Macmillan\|year = 1983\|isbn = 9780716715870\|pages = [https://archive.org/details/linearprogrammin00chv/page/320 320–351]\|chapter = 20\|chapter-url = https://books.google.com/books?id=DN20_tW_BV0C&dq=network%20simplex%20applications&pg=PA320\|url = https://archive.org/details/linearprogrammin00chv/page/320}}</ref>
	* [[Transshipment problem]]		* [[Transshipment problem]]
	* [[Transportation theory (mathematics)\|Hitchcock transportation problem]]		* [[Transportation theory (mathematics)\|Hitchcock transportation problem]]

Monkbot: Task 18 (cosmetic): eval 4 templates: del empty params (1×);

2020-12-31T03:49:27Z

Task 18 (cosmetic): eval 4 templates: del empty params (1×);

← Previous revision		Revision as of 03:49, 31 December 2020
Line 18:		Line 18:

	== Applications ==		== Applications ==
	The network simplex algorithm can be used to solve many practical problems including,<ref>{{Cite book\|title = Linear Programming\|last = Chvatal\|first = Vasek\|publisher = Macmillan\|year = 1983\|isbn = 9780716715870~~\|location =~~ \|pages = [https://archive.org/details/linearprogrammin00chv/page/320 320–351]\|chapter = 20\|chapter-url = https://books.google.com/books?id=DN20_tW_BV0C&lpg=PA320&ots=4eHDEubUhH&dq=network%20simplex%20applications&pg=PA320#v=onepage&q&f=false\|url = https://archive.org/details/linearprogrammin00chv/page/320}}</ref>		The network simplex algorithm can be used to solve many practical problems including,<ref>{{Cite book\|title = Linear Programming\|last = Chvatal\|first = Vasek\|publisher = Macmillan\|year = 1983\|isbn = 9780716715870\|pages = [https://archive.org/details/linearprogrammin00chv/page/320 320–351]\|chapter = 20\|chapter-url = https://books.google.com/books?id=DN20_tW_BV0C&lpg=PA320&ots=4eHDEubUhH&dq=network%20simplex%20applications&pg=PA320#v=onepage&q&f=false\|url = https://archive.org/details/linearprogrammin00chv/page/320}}</ref>
	* [[Transshipment problem]]		* [[Transshipment problem]]
	* [[Transportation theory (mathematics)\|Hitchcock transportation problem]]		* [[Transportation theory (mathematics)\|Hitchcock transportation problem]]

Svendcs: Removed claim that the network simplex algorithm has polynomial time complexity

2020-06-19T12:42:03Z

Removed claim that the network simplex algorithm has polynomial time complexity

← Previous revision		Revision as of 12:42, 19 June 2020
Line 1:		Line 1:
	In [[mathematical optimization]], the '''network simplex algorithm''' is a [[graph theory\|graph theoretic]] specialization of the [[simplex algorithm]]. The algorithm is usually formulated in terms of a [[minimum-cost flow problem]] ~~and can be efficiently solved in polynomial time~~. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.{{citation needed\|date=May 2015}}		In [[mathematical optimization]], the '''network simplex algorithm''' is a [[graph theory\|graph theoretic]] specialization of the [[simplex algorithm]]. The algorithm is usually formulated in terms of a [[minimum-cost flow problem]]. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.{{citation needed\|date=May 2015}}

	== History ==		== History ==

OAbot: Open access bot: hdl added to citation with #oabot.

2020-04-15T09:20:01Z

Open access bot: hdl added to citation with #oabot.

← Previous revision		Revision as of 09:20, 15 April 2020
Line 2:		Line 2:

	== History ==		== History ==
	For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available. In 1995 [[James B. Orlin\|Orlin]] provided the first polynomial algorithm with runtime of <math>O(V^2 E \log(VC))</math> where <math>C</math> is maximum cost of any edges.<ref>{{Cite journal\|title = A polynomial time primal network simplex algorithm for minimum cost flows\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 109–129\|volume = 78\|issue = 2\|doi = 10.1007/BF02614365\|first = James B.\|last = Orlin\|hdl = 1721.1/2584}}</ref> Later [[Robert Tarjan\|Tarjan]] improved this to <math>O(VE \log V \log(VC))</math> using [[dynamic trees]] in 1997.<ref>{{Cite journal\|title = Dynamic trees as search trees via euler tours, applied to the network simplex algorithm\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 169–177\|volume = 78\|issue = 2\|doi = 10.1007/BF02614369\|first = Robert E.\|last = Tarjan}}</ref> Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.<ref>{{citation		For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available. In 1995 [[James B. Orlin\|Orlin]] provided the first polynomial algorithm with runtime of <math>O(V^2 E \log(VC))</math> where <math>C</math> is maximum cost of any edges.<ref>{{Cite journal\|title = A polynomial time primal network simplex algorithm for minimum cost flows\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 109–129\|volume = 78\|issue = 2\|doi = 10.1007/BF02614365\|first = James B.\|last = Orlin\|hdl = 1721.1/2584\|hdl-access = free}}</ref> Later [[Robert Tarjan\|Tarjan]] improved this to <math>O(VE \log V \log(VC))</math> using [[dynamic trees]] in 1997.<ref>{{Cite journal\|title = Dynamic trees as search trees via euler tours, applied to the network simplex algorithm\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 169–177\|volume = 78\|issue = 2\|doi = 10.1007/BF02614369\|first = Robert E.\|last = Tarjan}}</ref> Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.<ref>{{citation
	\| last1 = Orlin \| first1 = James B. \| author1-link = James B. Orlin		\| last1 = Orlin \| first1 = James B. \| author1-link = James B. Orlin
	\| last2 = Plotkin \| first2 = Serge A.		\| last2 = Plotkin \| first2 = Serge A.

InternetArchiveBot: Bluelinking 1 books for verifiability.) #IABot (v2.1alpha3

2019-12-18T20:20:44Z

Bluelinking 1 books for verifiability.) #IABot (v2.1alpha3

← Previous revision		Revision as of 20:20, 18 December 2019
Line 18:		Line 18:

	== Applications ==		== Applications ==
	The network simplex algorithm can be used to solve many practical problems including,<ref>{{Cite book\|title = Linear Programming\|last = Chvatal\|first = Vasek\|publisher = Macmillan\|year = 1983\|isbn = 9780716715870\|location = \|pages = 320–351\|chapter = 20\|chapter-url = https://books.google.com/books?id=DN20_tW_BV0C&lpg=PA320&ots=4eHDEubUhH&dq=network%20simplex%20applications&pg=PA320#v=onepage&q&f=false}}</ref>		The network simplex algorithm can be used to solve many practical problems including,<ref>{{Cite book\|title = Linear Programming\|last = Chvatal\|first = Vasek\|publisher = Macmillan\|year = 1983\|isbn = 9780716715870\|location = \|pages = [https://archive.org/details/linearprogrammin00chv/page/320 320–351]\|chapter = 20\|chapter-url = https://books.google.com/books?id=DN20_tW_BV0C&lpg=PA320&ots=4eHDEubUhH&dq=network%20simplex%20applications&pg=PA320#v=onepage&q&f=false\|url = https://archive.org/details/linearprogrammin00chv/page/320}}</ref>
	* [[Transshipment problem]]		* [[Transshipment problem]]
	* [[Transportation theory (mathematics)\|Hitchcock transportation problem]]		* [[Transportation theory (mathematics)\|Hitchcock transportation problem]]

Pjrule: Remove confusing and unnecessary phrase

2019-08-19T16:12:29Z

Remove confusing and unnecessary phrase

← Previous revision		Revision as of 16:12, 19 August 2019
Line 1:		Line 1:
	In [[mathematical optimization]], the '''network simplex algorithm''' is a [[graph theory\|graph theoretic]] specialization of the [[simplex algorithm]]. The algorithm is usually formulated in terms of a ~~standard problem,~~ [[minimum-cost flow problem]] and can be efficiently solved in polynomial time. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.{{citation needed\|date=May 2015}}		In [[mathematical optimization]], the '''network simplex algorithm''' is a [[graph theory\|graph theoretic]] specialization of the [[simplex algorithm]]. The algorithm is usually formulated in terms of a [[minimum-cost flow problem]] and can be efficiently solved in polynomial time. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.{{citation needed\|date=May 2015}}

	== History ==		== History ==

152.172.195.150: Undid revision 906862097 by 152.172.195.150 (talk)

2019-07-18T19:41:16Z

Undid revision 906862097 by 152.172.195.150 (talk)

← Previous revision		Revision as of 19:41, 18 July 2019
Line 2:		Line 2:

	== History ==		== History ==
	For a long time, the existence of a ~~probably~~ efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available. In 1995 [[James B. Orlin\|Orlin]] provided the first polynomial algorithm with runtime of <math>O(V^2 E \log(VC))</math> where <math>C</math> is maximum cost of any edges.<ref>{{Cite journal\|title = A polynomial time primal network simplex algorithm for minimum cost flows\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 109–129\|volume = 78\|issue = 2\|doi = 10.1007/BF02614365\|first = James B.\|last = Orlin\|hdl = 1721.1/2584}}</ref> Later [[Robert Tarjan\|Tarjan]] improved this to <math>O(VE \log V \log(VC))</math> using [[dynamic trees]] in 1997.<ref>{{Cite journal\|title = Dynamic trees as search trees via euler tours, applied to the network simplex algorithm\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 169–177\|volume = 78\|issue = 2\|doi = 10.1007/BF02614369\|first = Robert E.\|last = Tarjan}}</ref> Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.<ref>{{citation		For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available. In 1995 [[James B. Orlin\|Orlin]] provided the first polynomial algorithm with runtime of <math>O(V^2 E \log(VC))</math> where <math>C</math> is maximum cost of any edges.<ref>{{Cite journal\|title = A polynomial time primal network simplex algorithm for minimum cost flows\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 109–129\|volume = 78\|issue = 2\|doi = 10.1007/BF02614365\|first = James B.\|last = Orlin\|hdl = 1721.1/2584}}</ref> Later [[Robert Tarjan\|Tarjan]] improved this to <math>O(VE \log V \log(VC))</math> using [[dynamic trees]] in 1997.<ref>{{Cite journal\|title = Dynamic trees as search trees via euler tours, applied to the network simplex algorithm\|journal = Mathematical Programming\|date = 1997-08-01\|issn = 0025-5610\|pages = 169–177\|volume = 78\|issue = 2\|doi = 10.1007/BF02614369\|first = Robert E.\|last = Tarjan}}</ref> Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.<ref>{{citation
	\| last1 = Orlin \| first1 = James B. \| author1-link = James B. Orlin		\| last1 = Orlin \| first1 = James B. \| author1-link = James B. Orlin
	\| last2 = Plotkin \| first2 = Serge A.		\| last2 = Plotkin \| first2 = Serge A.