Configuration linear program: Difference between revisions

Content deleted Content added
Altered template type. Add: chapter-url-access, chapter-url, chapter, title. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget
Citation bot (talk | contribs)
Removed URL that duplicated identifier. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 505/1032
 
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 book|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|title=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) |chapter=An efficient approximation scheme for the one-dimensional bin-packing problem |date=1982-11-01 |chapter-url=https://ieeexplore.ieee.org/document/4568405 |pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908|chapter-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 30:
 
=== The fractional LP ===
The '''fractional configuration LP of bin-packing''' It is the [[linear programming relaxation]] of the above ILP. It replaces the last constraint <math>x_c\in\{0,\ldots,n\}</math> with the constraint <math>x_c \geq 0</math>. In other words, each configuration can be used a fractional number of times. The relaxation was first presented by Gilmore and Gomory,<ref name="Gilmore61" /> and it is often called the '''Gilmore-Gomory linear program'''.<ref name=":22">{{Cite book|last=Rothvoß|first=T.|title=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |chapter=Approximating Bin Packing within O(log OPT · Log Log OPT) Bins |date=2013-10-01|chapter-url=https://ieeexplore.ieee.org/document/6686137|volume=|pages=20–29|arxiv=1301.4010|doi=10.1109/FOCS.2013.11|isbn=978-0-7695-5135-7|via=|s2cid=15905063}}</ref>
 
* ''Example'': suppose there are 31 items of size 3 and 7 items of size 4, and the bin-size is 10. The configurations are: 4, 44, 34, 334, 3, 33, 333. The constraints are [0,0,1,2,1,2,3]*'''x'''=31 and [1,2,1,1,0,0,0]*'''x'''=7. An optimal solution to the fractional LP is [0,0,0,7,0,0,17/3] That is: there are 7 bins of configuration 334 and 17/3 bins of configuration 333. Note that only two different configurations are needed.