Content deleted Content added
No edit summary |
|||
Line 127:
Suppose <math>A</math> is an ''m''-by-''n'' integer matrix and <math>\mathbf{b}</math> is an ''m''-by-1 integer vector. We focus on the feasibility problem, which is to decide whether there exists an ''n''-by-1 vector <math>\mathbf{x}</math> satisfying <math> A \mathbf{x} \le \mathbf{b} </math>.
Let ''V'' be the maximum absolute value of the coefficients in <math>A</math> and <math>\mathbf{b}</math>. If ''n'' (the number of variables) is a fixed constant, then the feasibility problem can be solved in time polynomial in ''m'' and log ''V''. This is trivial for the case ''n''=1. The case ''n''=2 was solved in 1981 by [[Herbert Scarf]].<ref>{{Cite journal|last=Scarf|first=Herbert E.|date=1981|title=Production Sets with Indivisibilities, Part I: Generalities|url=https://www.jstor.org/stable/1911124|journal=Econometrica|volume=49|issue=1|pages=1–32|doi=10.2307/1911124|jstor=1911124|issn=0012-9682}}</ref> The general case was solved in 1983 by [[Hendrik Lenstra]], combining ideas by [[László Lovász]] and [[Peter van Emde Boas]].<ref name=":0">{{Cite journal|last=Lenstra|first=H. W.|date=1983-11-01|title=Integer Programming with a Fixed Number of Variables|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.8.4.538|journal=Mathematics of Operations Research|volume=8|issue=4|pages=538–548|doi=10.1287/moor.8.4.538|issn=0364-765X|citeseerx=10.1.1.431.5444}}</ref> [[Doignon's theorem]] asserts that an integer program is feasible whenever every subset of <math>2^n</math> constraints is feasible; a method combining this result with algorithms for [[LP-type problem]]s can be used to solve integer programs in time that is linear in <math>m</math> and [[fixed-parameter tractable]] in <math>n</math>.<ref>{{cite conference
| last1 = Amenta | first1 = Nina | author1-link = Nina Amenta
| last2 = De Loera | first2 = Jesús A. | author2-link = Jesús A. De Loera
| last3 = Soberón | first3 = Pablo
| editor1-last = Harrington | editor1-first = Heather A. | editor1-link = Heather Harrington
| editor2-last = Omar | editor2-first = Mohamed
| editor3-last = Wright | editor3-first = Matthew
| arxiv = 1508.07606
| contribution = Helly's theorem: new variations and applications
| doi = 10.1090/conm/685
| ___location = Providence, Rhode Island
| mr = 3625571
| pages = 55–95
| publisher = American Mathematical Society
| series = Contemporary Mathematics
| title = Proceedings of the AMS Special Session on Algebraic and Geometric Methods in Applied Discrete Mathematics held in San Antonio, TX, January 11, 2015
| volume = 685
| year = 2017}}</ref>
In the special case of 0-1 ILP, Lenstra's algorithm is equivalent to complete enumeration: the number of all possible solutions is fixed (2''<sup>n</sup>''), and checking the feasibility of each solution can be done in time poly(''m'', log ''V''). In the general case, where each variable can be an arbitrary integer, complete enumeration is impossible. Here, Lenstra's algorithm uses ideas from [[Geometry of numbers]]. It transforms the original problem into an equivalent one with the following property: either the existence of a solution <math>\mathbf{x}</math> is obvious, or the value of <math>x_n</math> (the ''n''-th variable) belongs to an interval whose length is bounded by a function of ''n''. In the latter case, the problem is reduced to a bounded number of lower-dimensional problems. The run-time complexity of the algorithm has been improved in several steps:
| |||