Integer programming: Difference between revisions

Content deleted Content added
Swmar (talk | contribs)
m Proof of NP-hardness: model can be further simplified, we don't need linear constraints in ILP
Line 163:
 
* Reis and Rothvoss<ref>Reis, Victor; Rothvoss, Thomas (2023-03-26). [https://arxiv.org/abs/2303.14605 "The Subspace Flatness Conjecture and Faster Integer Programming"]. </ref> presented an improved algorithm with run-time <math>(\log n)^{O(n)} \cdot (m\cdot \log V)^{O(1)}</math>.
These algorithms can also for '''mixed integer linear programs''' (MILP) - programs in which some variables are integer and some variables are real.<ref name=":1">{{Cite web |last=Hildebrand |first=Robert |date=2016-10-07 |title=FPT algorithm for mixed integer program |url=https://cstheory.stackexchange.com/a/36738/9453 |access-date=2024-05-21 |website=Theoretical Computer Science Stack Exchange |language=en}}</ref> The original algorithm of Lenstra<ref name=":0" />{{Rp|___location=Sec.5}} has run-time <math>2^{O(n^3)}\cdot poly(d,L)</math>, where n is the number of integer variables, d is the number of continuous variables, and ''L'' is the binary encoding size of the problem. Using techniques from later algorithms, the factor <math>2^{O(n^3)}</math> can be improved to <math>2^{O(n\log n)}</math> or to <math>n^n</math>.<ref name=":1" />
 
===Heuristic methods===