Content deleted Content added
→Exact algorithms for a small number of variables{{Anchor|Lenstra}}: but doubly exponential |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (45 intermediate revisions by 26 users not shown) | |||
Line 1:
{{Short description|
An '''integer programming''' problem is a [[mathematical optimization]] or [[Constraint satisfaction problem|feasibility]] program in which some or all of the variables are restricted to be [[integer]]s. In many settings the term refers to '''integer [[linear programming]]''' (ILP), in which the [[objective function]] and the constraints (other than the integer constraints) are [[Linear function (calculus)|linear]].
Integer programming is [[NP-complete]]
| first = Richard M. |last = Karp
|chapter = Reducibility among Combinatorial Problems
| author-link = Richard M. Karp
| chapter-url = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
| title = Complexity of Computer Computations
| editor = R. E. Miller |editor2=J. W. Thatcher |editor3=J.D. Bohlinger
| publisher = New York: Plenum
| pages = 85–103
| year = 1972
| doi = 10.1007/978-1-4684-2001-2_9
| isbn = 978-1-4684-2003-6
}}</ref>
If some decision variables are not discrete, the problem is known as a '''mixed-integer programming''' problem.<ref>{{cite web |url=http://macc.mcmaster.ca/maccfiles/chachuatnotes/07-MILP-I_handout.pdf |title=Mixed-Integer Linear Programming (MILP): Model Formulation |access-date=16 April 2018}}</ref>
Line 11 ⟶ 23:
:<math> \begin{align}
& \underset{\mathbf{x} \in \mathbb{Z}^n}{\text{maximize}} && \mathbf{c}^\mathrm{T} \mathbf{x}\\
& \text{subject to} && A \mathbf{x} \le \mathbf{b}, \\
& && \mathbf{x} \ge \mathbf{0}
\end{align} </math>
Line 20 ⟶ 31:
:<math> \begin{align}
& \underset{\mathbf{x} \in \mathbb{Z}^n}{\text{maximize}} && \mathbf{c}^\mathrm{T} \mathbf{x}\\
& \text{subject to} && A \mathbf{x} + \mathbf{s} = \mathbf{b}, \\
& && \mathbf{s} \ge \mathbf{0}, \\
& && \mathbf{x} \ge \mathbf{0},
\end{align} </math>
where <math>\mathbf{c}\in \mathbb{R}^n, \mathbf{b} \in \mathbb{R}^m</math> are vectors and <math>A \in \mathbb{R}^{m \times n}</math> is a matrix. As with linear programs, ILPs not in standard form can be [[simplex algorithm#Standard form|converted to standard form]] by eliminating inequalities, introducing slack variables (<math>\mathbf{s}</math>) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables.
Line 31 ⟶ 41:
[[File:IP polytope with LP relaxation.svg|350px|thumb|IP polytope with LP relaxation]]
The plot on the right shows the following problem.
\begin{align}▼
\max & \text{ } y \\▼
-x +y & \leq 1 \\▼
3x +2y & \leq 12 \\▼
\end{align}▼
The feasible integer points are shown in red, and the red dashed lines indicate their convex hull, which is the smallest convex polyhedron that contains all of these points. The blue lines together with the coordinate axes define the polyhedron of the LP relaxation, which is given by the inequalities without the integrality constraint. The goal of the optimization is to move the black dashed line as far upward while still touching the polyhedron. The optimal solutions of the integer problem are the points <math>(1,2)</math> and <math>(2,2)</math> which both have an objective value of 2. The unique optimum of the relaxation is <math>(1.8,2.8)</math> with objective value of 2.8. If the solution of the relaxation is rounded to the nearest integers, it is not feasible for the ILP.▼
\underset{x,y \in \mathbb{Z}}{\text{maximize}} \quad & y \\
\text{subject to} \quad &-x +y \leq 1 \\
▲The feasible integer points are shown in red, and the red dashed lines indicate their [[convex hull]], which is the smallest convex polyhedron that contains all of these points. The blue lines together with the coordinate axes define the polyhedron of the LP relaxation, which is given by the inequalities without the integrality constraint. The goal of the optimization is to move the black dashed line as far upward while still touching the polyhedron. The optimal solutions of the integer problem are the points <math>(1,2)</math> and <math>(2,2)</math>
==Proof of NP-hardness==
Line 52 ⟶ 60:
:<math> \begin{align}
\min \sum_{v \in V} y_v \\
y_v + y_u & \ge 1 && \forall
y_v & \
\end{align}</math>
Line 62 ⟶ 69:
'''Mixed-integer linear programming''' ('''MILP''') involves problems in which only some of the variables, <math>x_i</math>, are constrained to be integers, while other variables are allowed to be non-integers.
'''
:<math display=block>
x = x_1+2x_2+4x_3+\cdots+2^{\lfloor \log_2U\rfloor}x_{\lfloor \log_2U\rfloor+1}.
Line 75 ⟶ 82:
===Production planning===
Mixed-integer programming has many applications in industrial productions, including job-shop modelling. One important example happens in agricultural [[production planning]] and involves determining production yield for several crops that can share resources (e.g.
===Scheduling===
These problems involve service and vehicle scheduling in transportation networks. For example, a problem may involve assigning buses or subways to individual routes so that a timetable can be met, and also to equip them with drivers. Here binary decision variables indicate whether a bus or subway is assigned to a route and whether a driver is assigned to a particular train or subway. The
===Territorial partitioning===
Territorial partitioning or districting
===Telecommunications networks===
The goal of these problems is to design a network of lines to install so that a predefined set of communication requirements are met and the total cost of the network is minimal.<ref>{{cite web|last1=Borndörfer|first1=R.|last2=Grötschel|first2=M.|author2-link= Martin Grötschel |title=Designing telecommunication networks by integer programming|url=http://www.zib.de/groetschel/teaching/SS2012/120503Vorlesung-DesigningTelcomNetworks-reduced.pdf|year=2012}}</ref> This requires optimizing both the topology of the network along with
===Cellular networks===
Line 95 ⟶ 102:
* [[Cashflow matching|Cash flow matching]]
* [[Energy system]] optimization<ref>{{Cite journal|last1=Morais|first1=Hugo|last2=Kádár|first2=Péter|last3=Faria|first3=Pedro|last4=Vale|first4=Zita A.|last5=Khodr|first5=H. M.|date=2010-01-01|title=Optimal scheduling of a renewable micro-grid in an isolated load area using mixed-integer linear programming|url=http://www.sciencedirect.com/science/article/pii/S0960148109001001|journal=Renewable Energy|language=en|volume=35|issue=1|pages=151–156|doi=10.1016/j.renene.2009.02.031|bibcode=2010REne...35..151M |issn=0960-1481|hdl=10400.22/1585|hdl-access=free|url-access=subscription}}</ref><ref>{{Cite journal|last1=Omu|first1=Akomeno|last2=Choudhary|first2=Ruchi|last3=Boies|first3=Adam|date=2013-10-01|title=Distributed energy resource system optimisation using mixed integer linear programming|url=http://www.sciencedirect.com/science/article/pii/S0301421513003418|journal=Energy Policy|language=en|volume=61|pages=249–266|doi=10.1016/j.enpol.2013.05.009|bibcode=2013EnPol..61..249O |s2cid=29369795 |issn=0301-4215|url-access=subscription}}</ref>
* [[Unmanned aerial vehicle|UAV]] [[Guidance system|guidance]]<ref>{{Cite
* [[Transit map]] [[Graph drawing|layouting]]<ref>{{cite arXiv |last1=Bast |first1=Hannah |last2=Brosi |first2=Patrick |last3=Storandt |first3=Sabine |date=2017-10-05 |title=Efficient Generation of Geographically Accurate Transit Maps |class=cs.CG |eprint=1710.02226 }}</ref>
==Algorithms==
Line 104 ⟶ 112:
===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>.
Line 120 ⟶ 128:
===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.
Line 127 ⟶ 135:
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|url-access=subscription}}</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]]
| last1 = Amenta | first1 = Nina | author1-link = Nina Amenta
| last2 = De Loera | first2 = Jesús A. | author2-link = Jesús A. De Loera
Line 144 ⟶ 152:
| 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|arxiv=1307.5108}}</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|url-access=subscription}}</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
* 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"].
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" />
▲* 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>.
===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
Other heuristic methods that can be applied to ILPs include
Line 169 ⟶ 176:
== Sparse integer programming ==
It is often the case that the matrix <math>A</math>
| last1 = Koutecký | first1 = Martin
| last2 = Levin | first2 = Asaf
| last3 = Onn | first3 = Shmuel
| editor1-last = Chatzigiannakis | editor1-first = Ioannis
| editor2-last = Kaklamanis | editor2-first = Christos
| editor3-last = Marx | editor3-first = Dániel
| editor4-last = Sannella | editor4-first = Donald
| arxiv = 1802.05859
| contribution = A parameterized strongly polynomial algorithm for block structured integer programs
| doi = 10.4230/LIPICS.ICALP.2018.85
| pages = 85:1–85:14
| publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
| series = LIPIcs
| title = 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9–13, 2018, Prague, Czech Republic
| volume = 107
| year = 2018| doi-access = free
}}</ref> that integer programming can be solved in [[strongly polynomial]] and [[fixed-parameter tractable]] time parameterized by <math>a</math> and <math>d</math>. That is, for some computable function <math>f</math> and some constant <math>k</math>, integer programming can be solved in time <math>f(a,d)n^k</math>. In particular, the time is independent of the right-hand side <math>b</math> and objective function <math>c</math>. Moreover, in contrast to the classical result of Lenstra, where the number <math>n</math> of variables is a parameter, here the number <math>n</math> of variables is a variable part of the input.
==See also==
* [[Constrained least squares]]
* {{annotated link|Diophantine equation}}
==References==
Line 187 ⟶ 212:
* {{cite book|author1=Der-San Chen|author2=Robert G. Batson|author3=Yu Dang|title=Applied Integer Programming: Modeling and Solution|year=2010|publisher=John Wiley and Sons|isbn=978-0-470-37306-4}}
* {{cite book|author1=Gerard Sierksma|author2=Yori Zwols|title=Linear and Integer Optimization: Theory and Practice|year=2015|publisher=CRC Press|isbn=978-1-498-71016-9}}
* {{cite journal|author1=François Clautiaux|author2=Ivana Ljubić|title=Last fifty years of integer linear programming: a focus on recent practical advances|year=2024|publisher=[[INRIA]]|url=https://inria.hal.science/hal-04776866|doi=10.1016/j.ejor.2024.11.018|journal=[[European Journal of Operational Research]]}} Overview article.
==External links==
Line 195 ⟶ 221:
[[Category:Combinatorial optimization]]
[[Category:NP-complete problems]]
| |||