Configuration linear program: Difference between revisions

Revision as of 22:50, 16 January 2022

Revision as of 23:16, 16 January 2022

Line 5:

=== The integral LP ===

In the [[bin packing|bin packing problem]], there are ''n'' items with different sizes. The goal is to pack the items into a minimum number of bins, ofwhere sizeeach bin can contain at most ''B''. A ''feasible configuration'' is a set of sizes with a sum of at most ''B''.

* ''Example'':<ref name=":2">{{Cite web|last=Claire Mathieu|title=Approximation Algorithms Part I, Week 3: bin packing|url=https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3|url-status=live|website=Coursera}}</ref> suppose the item sizes are 3,3,3,3,3,4,4,4,4,4, and ''B''=12. Then the possible configurations are: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. If we had only three items of size 3, then we could not use the 3333 configuration.

Line 48:

=== Rounding the fractional LP ===

Karmarkar and Karp further developed a way to round the fractional LP into an approximate solution to the integral LP; see [[Karmarkar-Karp bin packing algorithms]]. Their proof shows that the additive [[integrality gap]] of this LP is in O(log²(''n'')). Later, Hoberg and Rothvoss<ref name=":3">{{Citation|last1=Hoberg|first1=Rebecca|title=A Logarithmic Additive Integrality Gap for Bin Packing|date=2017-01-01|url=https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.172|work=Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms|pages=2616–2625|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611974782.172|isbn=978-1-61197-478-2|access-date=2021-02-10|last2=Rothvoss|first2=Thomas|s2cid=1647463}}</ref> improved their result and proved that the integrality gap is in O(log(''n'')). The best known lower bound on the integrality gap is a constant Ω(1). Finding the exact integrality gap is an open problem.

== In bin covering ==

In the [[bin packing|bin covering problem]], there are ''n'' items with different sizes. The goal is to pack the items into a ''maximum'' number of bins, where each bin should contain ''at least'' ''B''. A natural configuration LP for this problem could be:<blockquote><math>\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\leq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0</math></blockquote>where '''''A''''' represents all configurations of items with sum ''at least'' ''B'' (one can take only the inclusion-minimal configurations). The problem with this LP is that, in the bin-covering problem, handling small items is problematic, since small items may be essential for the optimal solution. With small items allowed, the number of configurations may be too large even for the technique of Karmarkar and Karp.

Csirik, Johnson and Kenyon<ref name=":24">{{Cite journal|last=Csirik|first=Janos|last2=Johnson|first2=David S.|last3=Kenyon|first3=Claire|date=2001-01-09|title=Better approximation algorithms for bin covering|url=https://dl.acm.org/doi/abs/10.5555/365411.365533|journal=Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms|series=SODA '01|___location=Washington, D.C., USA|publisher=Society for Industrial and Applied Mathematics|pages=557–566|isbn=978-0-89871-490-6}}</ref>'''<ref name=":32">{{Cite journal|last=Jansen|first=Klaus|last2=Solis-Oba|first2=Roberto|date=2002-11-21|title=An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering|url=https://dl.acm.org/doi/abs/10.5555/646345.689912|journal=Proceedings of the 13th International Symposium on Algorithms and Computation|series=ISAAC '02|___location=Berlin, Heidelberg|publisher=Springer-Verlag|pages=175–186|isbn=978-3-540-00142-3}}</ref>''' present an alternative LP. First, they define a set of items that are called ''small''. Let ''T'' be the total size of all small items. Then, they construct a matrix '''A''' representing all configurations with sum < 2. Then, they consider the above LP with one additional constraint:<math display="block">\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~\text{s.t.}</math><math display="block">A \mathbf{x}\leq \mathbf{n}</math><math display="block">\sum_{c\in C: sum(c)<B} (B-sum(c))\cdot x_c \leq T</math><math display="block">\mathbf{x}\geq 0</math>The additional constraint guarantees that the "vacant space" in the bins can be filled by the small items.

== In machine scheduling ==

ConsiderIn the problem of [[unrelated-machines scheduling]]. In this problem, there are some ''m'' different machines that should process some ''n'' different jobs. When machine ''i'' processes job ''j'', it takes time ''p_i''_,''j''. The goal is to partition the jobs among the machines such that maximum completion time of a machine is as small as possible. The decision version of this problem is: given time ''T'', is there a partition in which the completion time of all machines is at most ''T''?

For each machine ''i'', there are finitely many subsets of jobs that can be processed by machine ''i'' in time at most ''T''. Each such subset is called a ''configuration'' for machine ''i''. Denote by ''C_i''(''T'') the set of all configurations for machine ''i'', given time ''T''. For each machine ''i'' and configuration ''c'' in ''C_i''(''T''), define a variable <math>x_{i,c}</math> which equals 1 iff the actual configuration used in machine ''i'' is ''c'', and 0 otherwise. Then, the LP constraints are:

Line 64 ⟶ 69:

* [[High-multiplicity bin packing]]

*[[Karmarkar-Karp bin packing algorithms]]

== References ==