Integer Linear Programming (Linear Programming)

From Algorithm Wiki
Jump to navigation Jump to search

Description

In this case, we require all of the variables to be integers.

Related Problems

Generalizations: Linear Programming with Reals

Subproblem: 0-1 Linear Programming

Related: General 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