General Linear Programming: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
n: number of variables | $n$: number of variables | ||
m: number of constraints | $m$: number of constraints | ||
L: length of input, in bits | $L$: length of input, in bits | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 26: | Line 26: | ||
|- | |- | ||
| [[Fourier–Motzkin elimination ( Linear Programming)|Fourier–Motzkin elimination]] || 1940 || $O((m/{4})$^{({2}^n)}) || $O((m/{4})$ | | [[Fourier–Motzkin elimination ( Linear Programming)|Fourier–Motzkin elimination]] || 1940 || $O((m/{4})$^{({2}^n)}) || $O((m/{4})$^{({2}^n)}) || Exact || Deterministic || | ||
|- | |- | ||
| [[Khachiyan Ellipsoid algorithm ( Linear Programming)|Khachiyan Ellipsoid algorithm ]] || 1979 || $O(n^{6} * L^{2} | | [[Khachiyan Ellipsoid algorithm ( Linear Programming)|Khachiyan Ellipsoid algorithm ]] || 1979 || $O(n^{6} * L^{2} \log L \log\log L)$ || $O(nmL)$ || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/abs/pii/0041555380900610 Time] | ||
|- | |- | ||
| [[Karmarkar's algorithm ( Linear Programming)|Karmarkar's algorithm]] || 1984 || $O(n^{3.5} L^{2} logL loglogL)$ || $O(nmL)$ || Exact || Deterministic || [https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf Time] | | [[Karmarkar's algorithm ( Linear Programming)|Karmarkar's algorithm]] || 1984 || $O(n^{3.5} L^{2} logL loglogL)$ || $O(nmL)$ || Exact || Deterministic || [https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf Time] | ||
|- | |- | ||
| [[Simplex Algorithm ( Linear Programming)|Simplex Algorithm]] || 1947 || $O({2}^n*poly(n, m))$ | | [[Simplex Algorithm ( Linear Programming)|Simplex Algorithm]] || 1947 || $O({2}^n*poly(n, m))$ || $O(nm)$ || Exact || Deterministic || | ||
|- | |- | ||
| [[Terlaky's Criss-cross algorithm ( Linear Programming)|Terlaky's Criss-cross algorithm]] || 1985 || $O({2}^n*poly(n, m))$ | | [[Terlaky's Criss-cross algorithm ( Linear Programming)|Terlaky's Criss-cross algorithm]] || 1985 || $O({2}^n*poly(n, m))$ || $O(nm)$ || Exact || Deterministic || | ||
|- | |- | ||
| [[Affine scaling ( Linear Programming)|Affine scaling]] || 1967 || ? (originally $O(n^{3.5} L)$ but seems unclear) || $O(nm+m^{2})$? || Exact || Deterministic || | | [[Affine scaling ( Linear Programming)|Affine scaling]] || 1967 || ? (originally $O(n^{3.5} L)$ but seems unclear) || $O(nm+m^{2})$? || Exact || Deterministic || | ||
Latest revision as of 08:18, 10 April 2023
Description
Linear programming (LP; also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization).
Related Problems
Subproblem: Linear Programming with Reals
Related: Integer Linear Programming, 0-1 Linear Programming
Parameters
$n$: number of variables
$m$: number of constraints
$L$: length of input, in bits
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Fourier–Motzkin elimination | 1940 | $O((m/{4})$^{({2}^n)}) | $O((m/{4})$^{({2}^n)}) | Exact | Deterministic | |
| Khachiyan Ellipsoid algorithm | 1979 | $O(n^{6} * L^{2} \log L \log\log L)$ | $O(nmL)$ | Exact | Deterministic | Time |
| Karmarkar's algorithm | 1984 | $O(n^{3.5} L^{2} logL loglogL)$ | $O(nmL)$ | Exact | Deterministic | Time |
| Simplex Algorithm | 1947 | $O({2}^n*poly(n, m))$ | $O(nm)$ | Exact | Deterministic | |
| Terlaky's Criss-cross algorithm | 1985 | $O({2}^n*poly(n, m))$ | $O(nm)$ | Exact | Deterministic | |
| Affine scaling | 1967 | ? (originally $O(n^{3.5} L)$ but seems unclear) | $O(nm+m^{2})$? | Exact | Deterministic | |
| Cohen; Lee and Song | 2018 | $O(n^{max(omega, {2.5}-alpha/{2}, {13}/{6})}*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication;
currently $O(n^{2.37285956})$ || $O(nm+n^{2})$? || Exact || Deterministic || Time | ||||
| Lee and Sidford | 2015 | $O((nnz(A) + n^{2}) n^{0.5})$ | $O(nm+n^{2})$?? | Exact | Deterministic | Time |
| Vaidya | 1987 | $O(((m+n)$n^{2}+(m+n)^{1.5}*n)L^{2} logL loglogL) | $O((nm+n^{2})$L)? | Exact | Deterministic | Time |
| Vaidya | 1989 | $O((m+n)$^{1.5}*n*L^{2} logL loglogL) | $O((nm+n^{2})$L)? | Exact | Deterministic | Time |
| Jiang, Song, Weinstein and Zhang | 2020 | $O(n^(max(omega, {2.5}-alpha/{2}, {37}/{18}))*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication;
currently $O(n^{2.37285956})$ || || Exact || Deterministic || Time |