Editing Integer programming (section)

==Algorithms==

The naive way to solve an ILP is to simply remove the constraint that '''x''' is integer, solve the corresponding LP (called the [[Linear programming relaxation|LP relaxation]] of the ILP), and then round the entries of the solution to the LP relaxation.  But, not only may this solution not be optimal, it may not even be feasible; that is, it may violate some constraint.

===Using total unimodularity===

While in general the solution to LP relaxation will not be guaranteed to be integral, if the ILP has the form <math>\max\mathbf{c}^\mathrm{T} \mathbf{x}</math> such that <math>A\mathbf{x} = \mathbf{b}</math> where <math>A</math> and <math>\mathbf{b}</math> have all integer entries and <math>A</math> is [[unimodular matrix#Total unimodularity|totally unimodular]], then every [[basic feasible solution]] is integral.  Consequently, the solution returned by the [[simplex algorithm]] is guaranteed to be integral.  To show that every basic feasible solution is integral, let <math>\mathbf{x}</math> be an arbitrary basic feasible solution . Since <math>\mathbf{x}</math> is feasible,
we know that <math>A\mathbf{x}=\mathbf{b}</math>. Let <math>\mathbf{x}_0=[x_{n_1},x_{n_2},\cdots,x_{n_j}]</math> be the elements corresponding to the basis columns for the basic solution <math>\mathbf{x}</math>. By definition of a basis, there is some square submatrix <math>B</math> of
<math>A</math> with linearly independent columns such that <math>B\mathbf{x}_0=\mathbf{b}</math>.

Since the columns of <math>B</math> are linearly independent and <math>B</math> is square, <math>B</math> is nonsingular,
and therefore by assumption, <math>B</math> is [[unimodular matrix|unimodular]] and so <math>\det(B)=\pm1</math>. Also, since <math>B</math> is nonsingular, it is invertible and therefore <math>\mathbf{x}_0=B^{-1}\mathbf{b}</math>. By definition, <math>B^{-1}=\frac{B^\mathrm{adj}}{\det(B)}=\pm B^\mathrm{adj}</math>. Here <math>B^\mathrm{adj}</math> denotes the [[Adjugate matrix|adjugate]] of <math>B</math> and is integral because <math>B</math> is integral.  Therefore,
<math display=block>
\begin{align}
&\Rightarrow B^{-1}=\pm B^\mathrm{adj} \text{ is integral.} \\
&\Rightarrow \mathbf{x}_0=B^{-1}b \text{ is integral.} \\
&\Rightarrow \text{Every basic feasible solution is integral.}
\end{align}
</math>
Thus, if the matrix <math>A</math> of an ILP is totally unimodular, rather than use an ILP algorithm, the simplex method can be used to solve the LP relaxation and the solution will be integer.

===Exact algorithms===
When the matrix <math>A</math> is not totally unimodular, there are a variety of algorithms that can be used to solve integer linear programs exactly.  One class of algorithms are [[Cutting-plane method|cutting plane methods]], which work by solving the LP relaxation and then adding linear constraints that drive the solution towards being integer without excluding any integer feasible points.

Another class of algorithms are variants of the [[branch and bound]] method.  For example, the [[branch and cut]] method that combines both branch and bound and cutting plane methods.  Branch and bound algorithms have a number of advantages over algorithms that only use cutting planes.  One advantage is that the algorithms can be terminated early and as long as at least one integral solution has been found, a feasible, although not necessarily optimal, solution can be returned.  Further, the solutions of the LP relaxations can be used to provide a worst-case estimate of how far from optimality the returned solution is.  Finally, branch and bound methods can be used to return multiple optimal solutions.

=== Exact algorithms for a small number of variables{{Anchor|Lenstra}} ===
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]] (FPT) in ''<math>n</math>'', but possibly [[Double exponential function|doubly exponential]] in <math>n</math>, with no dependence on <math>V</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| isbn = 9781470423216 }}</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:

* The original algorithm of Lenstra<ref name=":0" /> had run-time <math>2^{O(n^3)}\cdot (m\cdot \log V)^{O(1)}</math>.
* Kannan<ref>{{Cite journal|last=Kannan|first=Ravi|date=1987-08-01|title=Minkowski's Convex Body Theorem and Integer Programming|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.12.3.415|journal=Mathematics of Operations Research|volume=12|issue=3|pages=415–440|doi=10.1287/moor.12.3.415|s2cid=495512 |issn=0364-765X}}</ref>  presented an improved algorithm with run-time <math>n^{O(n)}\cdot (m\cdot \log V)^{O(1)}</math>.<ref>{{Cite journal|last1=Goemans|first1=Michel X.|author1link = Michel Goemans|last2=Rothvoss|first2=Thomas|date=2020-11-07|title=Polynomiality for Bin Packing with a Constant Number of Item Types|journal=[[Journal of the ACM]]|volume=67|issue=6|pages=38:1–38:21|doi=10.1145/3421750|hdl=1721.1/92865 |s2cid=227154747 |issn=0004-5411|doi-access=free|hdl-access=free}}</ref>
* Frank and Tardos<ref>{{Cite journal|last1=Frank|first1=András|last2=Tardos|first2=Éva|date=1987-03-01|title=An application of simultaneous diophantine approximation in combinatorial optimization|url=https://doi.org/10.1007/BF02579200|journal=Combinatorica|language=en|volume=7|issue=1|pages=49–65|doi=10.1007/BF02579200|s2cid=45585308|issn=1439-6912}}</ref> presented an improved algorithm with run-time  <math>n^{2.5 n} \cdot 2^{O(n)} \cdot (m\cdot \log V)^{O(1)}</math>.<ref>{{Cite journal|last1=Bliem|first1=Bernhard|last2=Bredereck|first2=Robert|last3=Niedermeier|first3=Rolf|author3-link=Rolf Niedermeier|date=2016-07-09|title=Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels|url=https://dl.acm.org/doi/abs/10.5555/3060621.3060636|journal=Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence|series=IJCAI'16|location=New York, New York, USA|publisher=AAAI Press|pages=102–108|isbn=978-1-57735-770-4}}</ref><ref>{{Cite book|last1=Bredereck|first1=Robert|last2=Kaczmarczyk|first2=Andrzej|last3=Knop|first3=Dušan|last4=Niedermeier|first4=Rolf|title=Proceedings of the 2019 ACM Conference on Economics and Computation |chapter=High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming |date=2019-06-17|chapter-url=https://doi.org/10.1145/3328526.3329649|series=EC '19|location=Phoenix, AZ, USA|publisher=Association for Computing Machinery|pages=505–523|doi=10.1145/3328526.3329649|isbn=978-1-4503-6792-9|s2cid=195298520}}</ref>{{Rp|Prop.8}}
* Dadush<ref>Dadush, Daniel (2012-06-14). [https://homepages.cwi.nl/~dadush/papers/dadush-thesis.pdf "Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation].</ref> presented an improved algorithm with run-time <math>n^n \cdot 2^{O(n)} \cdot (m \cdot \log V)^{O(1)}</math>.
* 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 be used 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===
Since integer linear programming is [[NP-hard]], many problem instances are intractable and so heuristic methods must be used instead.  For example, [[tabu search]] can be used to search for solutions to ILPs.<ref>{{cite journal|last=Glover|first=F.|author-link=Fred W. Glover|title=Tabu search-Part II|journal=ORSA Journal on Computing|year=1989|volume=1|issue=3|pages=4–32|doi= 10.1287/ijoc.2.1.4 |s2cid=207225435}}</ref>  To use tabu search to solve ILPs, moves can be defined as incrementing or decrementing an integer constrained variable of a feasible solution while keeping all other integer-constrained variables constant.  The unrestricted variables are then solved for. Short-term memory can consist of previously tried solutions while medium-term memory can consist of values for the integer constrained variables that have resulted in high objective values (assuming the ILP is a maximization problem). Finally, long-term memory can guide the search towards integer values that have not previously been tried.

Other heuristic methods that can be applied to ILPs include
*[[Hill climbing]]
*[[Simulated annealing]]
*Reactive search optimization
*[[Ant colony optimization algorithms|Ant colony optimization]]
*[[Hopfield network|Hopfield neural networks]]

There are also a variety of other problem-specific heuristics, such as the [[Travelling salesman problem#Iterative improvement|k-opt heuristic]] for the traveling salesman problem. A disadvantage of heuristic methods is that if they fail to find a solution, it cannot be determined whether it is because there is no feasible solution or whether the algorithm simply was unable to find one.  Further, it is usually impossible to quantify how close to optimal a solution returned by these methods are.