Gomory's cutting method (ILP;MILPs Convex Optimization (Non-linear))

Time Complexity

$O({2}^n*poly(n, m)$)? (previously $O(n^{3})$)

Space Complexity

$O(nm+m^{2})$ words

(See simplex algorithm, but also O(m) variables and constraints are introduced)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word/Real RAM

Year

1953

Reference

https://www.cs.uleth.ca/~benkoczi/OR/read/cutting-stock-LP.pdf