{{Short description|Linear programming for Combinatorial optimization}}
The '''configuration linear program''' ('''configuration-LP''') is a particular [[linear programming]] technique 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 the [[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/document/4568405|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 book|last1=Bansal|first1=Nikhil|last2=Caprara|first2=Alberto|last3=Sviridenko|first3=Maxim|title=2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) |chapter=Improved approximation algorithms for multidimensional bin packing problems |date=2006-10-01|chapter-url=https://ieeexplore.ieee.org/document/4031404|pages=697–708|doi=10.1109/FOCS.2006.38|isbn=0-7695-2720-5|s2cid=7690347}}</ref> and [[Optimal job scheduling|job scheduling]] problems.<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.
