Integer Linear Programming (Linear Programming)

From Algorithm Wiki
(Redirected from ILP)
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