Configuration linear program: Difference between revisions

Revision as of 19:25, 11 July 2023

Revision as of 23:00, 21 July 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/|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 journalbook|last1=Bansal|first1=Nikhil|last2=Caprara|first2=Alberto|last3=Sviridenko|first3=Maxim|datetitle=2006-10-01 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) |titlechapter=Improved approximation algorithms for multidimensional bin packing problems |date=2006-10-01|chapter-url=https://ieeexplore.ieee.org/abstract/document/4031404|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 ==

Line 24:

=== 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 journalbook|last=Rothvoß|first=T.|datetitle=2013-10-01 IEEE 54th Annual Symposium on Foundations of Computer Science |titlechapter=Approximating Bin Packing within O(log OPT *· Log Log OPT) Bins |date=2013-10-01|chapter-url=https://ieeexplore.ieee.org/document/6686137|journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science|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.