Content deleted Content added
m →Solving the fractional LP: fix another blockquote causing linebreak in inline math |
m Open access bot: url-access updated in citation with #oabot. |
||
Line 1:
{{Short description|Linear programming for Combinatorial optimization}}
The '''configuration linear program''' ('''configuration-LP''') is a [[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|url-access=subscription}}</ref><ref name="Gilmore61">{{cite journal | jstor=167051 | title=A Linear Programming Approach to the Cutting-Stock Problem | last1=Gilmore | first1=P. C. | last2=Gomory | first2=R. E. | journal=Operations Research | date=1961 | volume=9 | issue=6 | pages=849–859 | doi=10.1287/opre.9.6.849 | s2cid=8079477 }}</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|url-access=subscription}}</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|arxiv=1011.4957}}</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 ==
Line 41:
=== Solving the fractional LP ===
A linear program with no integrality constraints can be solved in time polynomial in the number of variables and constraints. The problem is that the number of variables in the fractional configuration LP is equal to the number of possible configurations, which might be huge. Karmarkar and Karp<ref name=":12">{{cite journal|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|date=November 1982|title=An efficient approximation scheme for the one-dimensional bin-packing problem|url=https://ieeexplore.ieee.org/document/4568405/references#references|journal=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908|url-access=subscription}}</ref> present an algorithm that overcomes this problem.
First, they construct the [[dual linear program]] of the fractional LP:
| |||