Content deleted Content added
Sunbergzach (talk | contribs) →Scheduling: Removed redundant and grammatically ill-formed sentences at end |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (5 intermediate revisions by 4 users not shown) | |||
Line 50:
\end{align} </math>
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> that 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. [[Simplex#Projection onto the standard simplex|See projection into simplex]]
==Proof of NP-hardness==
Line 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 book|last1=Schouwenaars|first1=T.|last2=Valenti|first2=M.|last3=Feron|first3=E.|last4=How|first4=J.|title=2005 IEEE Aerospace Conference |chapter=Implementation and Flight Test Results of MILP-based UAV Guidance |date=2005|pages=1–13|doi=10.1109/AERO.2005.1559600|isbn=0-7803-8870-4|s2cid=13447718}}</ref><ref>{{Cite journal|last1=Radmanesh|first1=Mohammadreza|last2=Kumar|first2=Manish|date=2016-03-01|title=Flight formation of UAVs in presence of moving obstacles using fast-dynamic mixed integer linear programming|journal=Aerospace Science and Technology|language=en|volume=50|pages=149–160|doi=10.1016/j.ast.2015.12.021|issn=1270-9638|doi-access=free|bibcode=2016AeST...50..149R }}</ref>
* [[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>
Line 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 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]] 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
Line 157:
* 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 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>.
Line 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==
| |||