Configuration linear program: Difference between revisions

Revision as of 23:30, 16 January 2022

Revision as of 14:31, 29 January 2022

Line 1:

{{Short description|Linear programming for Combinatorial optimization}}

The '''configuration linear program''' ('''configuration-LP''') is a particular [[linear programming]] used for solving [[combinatorial optimization]] problems. It was introduced in the context of the [[cutting stock problem]].<ref>{{Cite journal|last=Eisemann|first=Kurt|date=1957-04-01|title=The Trim Problem|url=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.3.3.279|journal=Management Science|volume=3|issue=3|pages=279–284|doi=10.1287/mnsc.3.3.279|issn=0025-1909}}</ref><ref name="Gilmore61">Gilmore P. C., R. E. Gomory (1961). ''[https://web.archive.org/web/20190219020906/http://pdfs.semanticscholar.org/1417/64b5e86dc6c2647dfce48098794c79d5a38b.pdf A linear programming approach to the cutting-stock problem]''. Operations Research 9: 849-859</ref> Later, it has been applied to [[bin packing]]<ref name=":1">{{Cite journal|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|date=1982-11-01|title=An efficient approximation scheme for the one-dimensional bin-packing problem|url=https://ieeexplore.ieee.org/abstract/document/4568405/?casa_token=9mn-Ej2IsAQAAAAA:F6ppNaGyr23r55exi3PezsKFWbcKOoTH-GOZ6JQre9FYdTZGAFxsnn6SnazQs7GYvm3KjuJx-yw|journal=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908}}</ref><ref>{{Cite journal|last1=Bansal|first1=Nikhil|last2=Caprara|first2=Alberto|last3=Sviridenko|first3=Maxim|date=2006-10-01|title=Improved approximation algorithms for multidimensional bin packing problems|url=https://ieeexplore.ieee.org/abstract/document/4031404?casa_token=1lyd-glredEAAAAA:wrrFIGkFxkirjYvEfDXcxnzz2U-wfCznKYsRUbEnUpNtDN0l7_BErBWVQ9LgWYzgDJ_JNupgUFU|journal=2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)|pages=697–708|doi=10.1109/FOCS.2006.38|isbn=0-7695-2720-5|s2cid=7690347}}</ref> and [[Optimal job scheduling|job scheduling]].<ref name=":0">{{Cite journal|last1=Verschae|first1=José|last2=Wiese|first2=Andreas|date=2014-08-01|title=On the configuration-LP for scheduling on unrelated machines|url=https://doi.org/10.1007/s10951-013-0359-4|journal=Journal of Scheduling|language=en|volume=17|issue=4|pages=371–383|doi=10.1007/s10951-013-0359-4|s2cid=34229676|issn=1099-1425}}</ref><ref>{{cite arxivarXiv|last1=Knop|first1=Dušan|last2=Koutecký|first2=Martin|date=2020-03-04|title=Scheduling Kernels via Configuration LP|class=cs.DS|eprint=2003.02187}}</ref> In the configuration-LP, there is a variable for each possible ''configuration'' - each possible multiset of items that can fit in a single bin (these configurations are also known as ''patterns'') . Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.

== In bin packing ==

Line 50:

== In bin covering ==

In the [[bin packing|bin covering problem]], there are ''n'' items with different sizes. The goal is to pack the items into a ''maximum'' number of bins, where each bin should contain ''at least'' ''B''. A natural configuration LP for this problem could be:<blockquote><math>\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\leq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0</math></blockquote>where '''''A''''' represents all configurations of items with sum ''at least'' ''B'' (one can take only the inclusion-minimal configurations). The problem with this LP is that, in the bin-covering problem, handling small items is problematic, since small items may be essential for the optimal solution. With small items allowed, the number of configurations may be too large even for the technique of Karmarkar and Karp. Csirik, Johnson and Kenyon<ref name=":24">{{Cite journal|lastlast1=Csirik|firstfirst1=Janos|last2=Johnson|first2=David S.|last3=Kenyon|first3=Claire|date=2001-01-09|title=Better approximation algorithms for bin covering|url=https://dl.acm.org/doi/abs/10.5555/365411.365533|journal=Proceedings of the twelfthTwelfth annualAnnual ACM-SIAM symposiumSymposium on Discrete algorithmsAlgorithms|series=SODA '01|___location=Washington, D.C., USA|publisher=Society for Industrial and Applied Mathematics|pages=557–566|isbn=978-0-89871-490-6}}</ref> present an alternative LP. First, they define a set of items that are called ''small''. Let ''T'' be the total size of all small items. Then, they construct a matrix '''A''' representing all configurations with sum < 2. Then, they consider the above LP with one additional constraint:<math display="block">\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~\text{s.t.}</math><math display="block">A \mathbf{x}\leq \mathbf{n}</math><math display="block">\sum_{c\in C: sum(c)<B} (B-sum(c))\cdot x_c \leq T</math><math display="block">\mathbf{x}\geq 0</math>The additional constraint guarantees that the "vacant space" in the bins can be filled by the small items. The dual of this LP is more complex and cannot be solved by a simple knapsack-problem separation oracle. Csirik, Johnson and Kenyon<ref name=":24" /> present a different method to solve it approximately in time exponential in 1/epsilon. Jansen and Solis-Oba'''<ref name=":32">{{Cite journal|lastlast1=Jansen|firstfirst1=Klaus|last2=Solis-Oba|first2=Roberto|date=2002-11-21|title=An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering|url=https://dl.acm.org/doi/abs/10.5555/646345.689912|journal=Proceedings of the 13th International Symposium on Algorithms and Computation|series=ISAAC '02|volume=2518|___location=Berlin, Heidelberg|publisher=Springer-Verlag|pages=175–186|doi=10.1007/3-540-36136-7_16|isbn=978-3-540-00142-3}}</ref>''' present an improved method to solve it approximately in time exponential in 1/epsilon.

== In machine scheduling ==