Content deleted Content added
m Open access bot: url-access updated in citation with #oabot. |
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 |
||
| (One intermediate revision by one other user not shown) | |||
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
== 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
* ''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.
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
First, they construct the [[dual linear program]] of the fractional LP:
| |||