Configuration linear program: Difference between revisions

Revision as of 21:18, 25 November 2021

Revision as of 21:41, 25 November 2021

Line 7:

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 of size ''B''. A ''feasible configuration'' is a set of sizes with a sum of at most ''B''.

* ''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.

For each size ''s'' and configuration ''c'', denote:

Line 19:

<math>\sum_{c\in C}a_{s,c}x_c \geq n_s</math> for every size ''s'' (- all ''n_s'' items of size ''s'' are packed).

<math>x_c\in\{0,\ldots,n\}</math> for all ''c'' in ''C'' (- there are at most ''n'' configurations of each type). </blockquote>The configuration LP is an [[integer linear program]], so in general it is NP-hard. However, it serves as a basis for several approximation algorithms. 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'').

=== Solution ===

* Handle the large items first:

The configuration LP is an [[integer linear program]], so in general it is NP-hard. But in the special-special case in which the number of sizes is some constant ''S'', and each size is at least ''eB'' (for some constant fraction ''e''<1), there are at most 1/''e'' items in each bin, so the total number of configurations is at most ''S''^1/''e''. Therefore, the configuration LP has at most ''S''^1/''e'' variables and ''S'' constraints, and it can be solved by exhaustive search in time <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n''.<ref>{{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>

** 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'' there are at most 1/''e'' items in each bin, the total number of configurations is at most ''S''^1/''e''.

** Solve the integer LP.

Finally,* considerAllocate the general case in which there are also some small items, of size less than ''eB''. These items can be added greedily into the bins with the large items using, e.g. [[Nextnext-fit bin packing]]. If no new bins are created, then thewe numberare of bins is still at most (1+''e'')OPTdone. 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, which is (1+O(''e''))OPT+1.

The algorithms differ in how they round the instance and in how the solve the integer LP.

Consider now a less-special case in which the number of sizes is general, but each size is still at least ''eB''. Fernandez de la Vega and Lueker<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''² groups of cardinality ''ne''². In each group, round the sizes upwards to the maximum size in the group. Now, there are only 1/''e''² different sizes, so the problem can be solved exactly in time <math>(1/e^2)\cdot n^{(1/e^2)^{1/e}}</math>, which is polynomial in ''n'' when ''e'' is constant. The resulting solution is feasible for the original instance too, but the number of bins may be larger than necessary. To analyze the approximation factor, 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''² zeros while in ''U'' there are some ''ne''² large items instead; but their size is at most ''B''. Therefore, U requires at most ''ne''² more bins than ''D''. Since ''D'' requires less bins than the optimum, we get that Bins(''U'') ≤ OPT + ''ne''², that is, we have an additive error that can be made as small as we like by choosing ''e''. Moreover, since each bin in OPT can contain at most 1/''e'' items (of size at least ''eB''), OPT must be at least ''en''. Therefore, Bins(''U'') ≤ (1+''e'')OPT.

=== Rounding the large-items instance ===

Finally, consider the general case in which there are also some small items, of size less than ''eB''. These items can be added greedily into the bins with the large items using e.g. [[Next-fit bin packing]]. If no new bins are created, then the number of bins is still at most (1+''e'')OPT. 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, which is (1+O(''e''))OPT+1.

Consider now a less-special case in whichSuppose the number of sizes is general, but each size is still at least ''eB''. Fernandez de la Vega and Lueker<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''² groups of cardinality ''ne''². In each group, round the sizes upwards to the maximum size in the group. Now, there are only 1/''e''² different sizes, so the problem can be solved exactly in time <math>(1/e^2)\cdot n^{(1/e^2)^{1/e}}</math>, which is polynomial in ''n'' when ''e'' is constant. The resulting solution is feasible for the original instance too, but the number of bins may be larger than necessary. To analyze the approximation factor, 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''² zeros while in ''U'' there are some ''ne''² large items instead; but their size is at most ''B''. Therefore, U requires at most ''ne''² more bins than ''D''. Since ''D'' requires less bins than the optimum, we get that Bins(''U'') ≤ OPT + ''ne''², that is, we have an additive error that can be made as small as we like by choosing ''e''. Moreover, since each bin in OPT can contain at most 1/''e'' items (of size at least ''eB''), OPT must be at least ''en''. Therefore, Bins(''U'') ≤ (1+''e'')OPT.

=== TheSolving fractionalthe integer LP for the rounded instance ===

TheA configurationsimple LPway isto ansolve the [[integer linearLP program]],is soby inexhaustive general it is NP-hardsearch. ButSince inthere theare special-specialat case in which the number of sizes is some constantmost ''S'' configurations, and each size is at least ''eB'' (for someeach constant fraction ''e''<1),configuration there are at most 1/''en'' items in eachpossible binvalues, so the total number of configurationsrun-time is at most ''S''^1/''e''. Therefore, the configuration LP has at most ''S''^1/''e'' variables and ''S'' constraints, and it can be solved by exhaustive search in time <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>

The ''fractional configuration LP'' of bin-packing 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.

TheA more efficient way is to use the '''fractional configuration LP'''. of bin-packingIt 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.

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'' (this would be the number of bins if we could cut items).

It is obvious that AVG(I) ≤ FOPT(I) ≤ OPT(I): AVG(I) is the number of bins when all bins are completely full - no solution can be better than this. FOPT(I) is the solution to the LP, which is less constrained than the ILP, so it is at least as good as OPT(I). 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> prove the following inequalities for any instance I:<blockquote><math>OPT(I) \leq 2\cdot AVG(I) + 1</math>.

<math>OPT(I) \leq FOPT(I)+(S+1)/2</math>.</blockquote>The inequality OPT(I) ≤ FOPT(I)+(S+1)/2 is proved constructively as follows.

It is obvious that AVG(I) ≤ FOPT(I) ≤ OPT(I): AVG(I) is the number of bins when all bins are completely full - no solution can be better than this. FOPT(I) is the solution to the LP, which is less constrained than the ILP, so it is at least as good as OPT(I). 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> prove the following inequalities for any instance I:<blockquote><math>OPT(I) \leq 2\cdot AVG(I) + 1</math>.

* <math>OPT(I) \leq 2\cdot AVG(I) + 1</math>.

* <math>OPT(I) \leq FOPT(I)+(S+1)/2</math>.

<math>OPT(I) \leq FOPT(I)+(S+1)/2</math>.</blockquote>The inequality OPT(I) ≤ FOPT(I)+(S+1)/2 is proved constructively as follows.

* 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''.