Content deleted Content added
Citation bot (talk | contribs) Alter: title, template type. Add: isbn, s2cid, chapter. Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine |
|||
Line 96:
* [[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|issn=0960-1481|hdl=10400.22/1585|hdl-access=free}}</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|issn=0301-4215}}</ref>
* [[Unmanned aerial vehicle|UAV]] [[Guidance system|guidance]]<ref>{{Cite
==Algorithms==
Line 144:
| 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.|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}}</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 journal|last1=Bredereck|first1=Robert|last2=Kaczmarczyk|first2=Andrzej|last3=Knop|first3=Dušan|last4=Niedermeier|first4=Rolf|date=2019-06-17|title=High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming|url=https://doi.org/10.1145/3328526.3329649|journal=Proceedings of the 2019 ACM Conference on Economics and Computation|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}}
|