Configuration linear program: Difference between revisions

Revision as of 03:29, 13 February 2023

Revision as of 22:10, 14 May 2023

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 arXiv|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 ==