Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) No edit summary |
||
Line 9:
* ''Example'':<ref name=":2" /> 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.
Denote by ''S'' the set of different sizes (and their number). Denote by ''C'' the set of different configurations (and their number). For each size ''s'' in ''S'' and configuration ''c'' in ''C'', denote:
* ''n<sub>s</sub>'' - the number of items of size ''s''.
Line 15:
* ''x<sub>c</sub>'' - a variable denoting the number of bins with configuration ''c''.
Then, the '''configuration LP of bin-packing''' is: <blockquote><math>\text{minimize}~~~\sum_{c\in C}x_c~~~\text{subject to}</math>
<math>\sum_{c\in C}a_{s,c}x_c \geq n_s</math> for
<math>x_c\in\{0,\ldots,n\}</math> for all ''c'' in ''C'' (- there are at most ''n''
However, this ILP serves as a basis for several approximation algorithms. The main idea of these algorithms is to reduce the original instance into a new instance in which ''S'' is small and ''e'' is large, so ''C'' is relatively small. Then, the ILP can be solved either by complete search (if ''S'', ''C'' are sufficiently small), or by relaxing it into a ''fractional'' LP.
* Separate the items to "small" (smaller than ''eB'', for some fraction e in (0,1)) and "large" (at least ''eB'').▼
* Handle the large items first:▼
** Round the item sizes in some way, such that the number of different sizes is at most some constant ''S.''▼
** Write the integer LP for the rounded instance. Since the number of sizes is ''S'' and there are at most 1/''e'' items in each bin, the total number of configurations is at most ''S''<sup>1/''e''</sup>. ▼
** Solve the integer LP. ▼
* Allocate the small items greedily, e.g. with [[next-fit bin packing]]. If no new bins are created, then we are done. If new bins are created, this means that all bins (except maybe the last one) are full up to at least (1-''e'')''B''. Therefore, the number of bins is at most OPT/(1-''e'')+1 ≤ (1+2''e'')OPT+1.▼
=== The fractional LP ===
The algorithms differ in how they round the instance and in how the solve the integer LP.▼
=== Rounding the large-items instance ===▼
Lueker and de-la-Vega and <ref>{{cite journal|last1=Fernandez de la Vega|first1=W.|last2=Lueker|first2=G. S.|date=1981|title=Bin packing can be solved within 1 + ε in linear time|journal=Combinatorica|language=en|volume=1|issue=4|pages=349–355|doi=10.1007/BF02579456|issn=1439-6912|s2cid=10519631}}</ref> invented the idea of ''adaptive input rounding''. Order the items by their size, and group them into 1/''e''<sup>2</sup> groups of cardinality ''ne''<sup>2</sup>. In each group, round the sizes upwards to the maximum size in the group. Now, there are only 1/''e''<sup>2</sup> different sizes. The solution of the rounded instance is feasible for the original instance too, but the number of bins may be larger than necessary. To quantify the loss, consider the instance rounded ''down'' to the maximum size in the ''previous'' group (the first group is rounded down to 0). The rounded-down instance ''D'' is almost equal to the rounded-up instance ''U'', except that in ''D'' there are some ''ne''<sup>2</sup> zeros while in ''U'' there are some ''ne''<sup>2</sup> large items instead; but their size is at most ''B''. Therefore, U requires at most ''ne''<sup>2</sup> more bins than ''D''. Since ''D'' requires fewer bins than the optimum, we get that Bins(''U'') ≤ OPT + ''ne''<sup>2</sup>, that is, we have an additive error that can be made as small as we like by choosing ''e''. ▼
If all items are large (of size at least ''eB''), then each bin in OPT contains at most 1/''e'' items (of size at least ''eB''), so OPT must be at least ''en''. Therefore, Bins(''U'') ≤ (1+''e'')OPT.▼
Karmarkar and Karp<ref name=":12" /> present a more efficient rounding method which they call ''geometric rounding'' (in contrast to the linear rounding of de-la-Vega and Lueker).▼
=== Solving the integer LP for the rounded instance ===▼
A simple way to solve the integer LP is by exhaustive search. Since there are at most ''S<sup>1/e</sup>'' configurations, and for each configuration there are at most ''n'' possible values, there are at most <math> n^{S^{1/e}}</math> combinations to check. For each combination, we have to check ''S'' constraints, so the run-time is <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n'' when ''S, e'' are constant.<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> ▼
▲A more efficient way is to use the '''fractional configuration LP'''. 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.
* ''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.
In short, the fractional LP can be written as follows:<blockquote><math>\text{minimize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\geq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0</math></blockquote>Where '''1''' is the vector (1,...,1) of size ''C'', '''A''' is an ''S''-by-''C'' matrix in which each column represents a single configuration, and '''n''' is the vector (''s''<sub>1</sub>,...,''s<sub>S</sub>'').
Let FOPT(I) be the optimal solution of the fractional LP for instance I, and OPT(I) the optimal solution of the integral LP. Let AVG be the sum of all sizes divided by ''B''. The following relations are obvious:
* AVG(I) ≤ FOPT(I), since AVG(I) is the (possibly fractional) number of bins when all bins are completely filled with items or fractions of items. Clearly, no solution can be more efficient.
* FOPT(I) ≤ OPT(I), since FOPT(I) is a solution to a minimization problem with fewer constraints.
* OPT(I) < 2*AVG(I), since in any packing with at least 2*AVG(I) bins, the sum of the two least-full bins is at most ''B'', so they can be combined into a single bin.
=== Rounding the fractional LP
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}}</ref> presented an algorithm for ''rounding'' an optimal solution for the fractional LP into a solution for the integral ILP, proving that OPT(I) ≤ FOPT(I) + S/2:
* Let '''x''' be an optimal [[basic feasible solution]] of the fractional LP. By definition, the value of '''x''' is FOPT(I). Since the fractional LP has ''S'' constraints, '''x''' has at most ''S'' nonzero variables, that is, at most ''S'' different configurations are used. We construct from '''x''' an integral packing consisting of a ''principal part'' and a ''residual part''.
* The principal part contains floor(''x<sub>c</sub>'') bins of each configuration ''c'' for which ''x<sub>c</sub>'' > 0.
* For the residual part (denoted by ''R''), we construct two candidate packings:
Line 59 ⟶ 45:
* Adding to this the rounded-down bins of the principal part yields FOPT(I) + S/2.
* The execution time of this conversion algorithm is O(''n'' log ''n'').
=== The dual LP ===
The [[dual linear program]] of the fractional LP is:<blockquote><math>\text{maximize}~~\mathbf{n}\cdot \mathbf{y}~~~\text{s.t.}~~ \mathbf{y}^T A \leq \mathbf{1}~~~\text{and}~~ \mathbf{y}\geq 0</math>.</blockquote>It has ''S'' variables ''y''<sub>1</sub>,...,''y<sub>S</sub>'', and ''C'' constraints - one for each configuration. It has the following economic interpretation.<ref name=":12" /> For each size ''s'', we should determine a nonnegative price ''y<sub>s</sub>''. Our profit is the total price of all items. We want to maximize the profit '''n''' '''y''' subject to the constraints that the total price of items in each configuration is at most 1.
=== Solving the fractional LP ===
Line 69 ⟶ 58:
<math>O\left(S^7 \log{S} \log^2(\frac{S n}{a h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{a h}) \right)</math>.
=== Approximation algorithms ===
Based on these innovations, they present an algorithm with run-time polynomial in <math>n</math> and <math>1/\varepsilon</math>. Their algorithm finds a solution with size at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(OPT))</math>.▼
The general scheme of these algorithms is:
▲* Separate the items to "small" (smaller than ''eB'', for some fraction e in (0,1)) and "large" (at least ''eB'').
▲* Handle the large items first:
▲** Round the item sizes in some way, such that the number of different sizes is at most some constant ''S.''
▲** Write the integer LP for the rounded instance. Since the number of sizes is ''S'' and there are at most 1/''e'' items in each bin, the total number of configurations is at most ''S''<sup>1/''e''</sup>.
▲** Solve the integer LP.
▲* Allocate the small items greedily, e.g. with [[next-fit bin packing]]. If no new bins are created, then we are done. If new bins are created, this means that all bins (except maybe the last one) are full up to at least (1-''e'')''B''. Therefore, the number of bins is at most OPT/(1-''e'')+1 ≤ (1+2''e'')OPT+1.
▲The algorithms differ in how they round the instance and in how the solve the integer LP.
▲=== Rounding the large-items instance ===
▲Lueker and de-la-Vega and <ref>{{cite journal|last1=Fernandez de la Vega|first1=W.|last2=Lueker|first2=G. S.|date=1981|title=Bin packing can be solved within 1 + ε in linear time|journal=Combinatorica|language=en|volume=1|issue=4|pages=349–355|doi=10.1007/BF02579456|issn=1439-6912|s2cid=10519631}}</ref> invented the idea of ''adaptive input rounding''. Order the items by their size, and group them into 1/''e''<sup>2</sup> groups of cardinality ''ne''<sup>2</sup>. In each group, round the sizes upwards to the maximum size in the group. Now, there are only 1/''e''<sup>2</sup> different sizes. The solution of the rounded instance is feasible for the original instance too, but the number of bins may be larger than necessary. To quantify the loss, consider the instance rounded ''down'' to the maximum size in the ''previous'' group (the first group is rounded down to 0). The rounded-down instance ''D'' is almost equal to the rounded-up instance ''U'', except that in ''D'' there are some ''ne''<sup>2</sup> zeros while in ''U'' there are some ''ne''<sup>2</sup> large items instead; but their size is at most ''B''. Therefore, U requires at most ''ne''<sup>2</sup> more bins than ''D''. Since ''D'' requires fewer bins than the optimum, we get that Bins(''U'') ≤ OPT + ''ne''<sup>2</sup>, that is, we have an additive error that can be made as small as we like by choosing ''e''.
▲If all items are large (of size at least ''eB''), then each bin in OPT contains at most 1/''e'' items (of size at least ''eB''), so OPT must be at least ''en''. Therefore, Bins(''U'') ≤ (1+''e'')OPT.
▲Karmarkar and Karp<ref name=":12" /> present a more efficient rounding method which they call ''geometric rounding'' (in contrast to the linear rounding of de-la-Vega and Lueker).
▲=== Solving the integer LP for the rounded instance ===
▲A simple way to solve the integer LP is by exhaustive search. Since there are at most ''S<sup>1/e</sup>'' configurations, and for each configuration there are at most ''n'' possible values, there are at most <math> n^{S^{1/e}}</math> combinations to check. For each combination, we have to check ''S'' constraints, so the run-time is <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n'' when ''S, e'' are constant.<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>
▲Based on these innovations, they present an algorithm with run-time polynomial in <math>n</math> and <math>1/\varepsilon</math>. Their algorithm finds a solution with size at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(OPT))</math>.
=== Improvements ===
| |||