Content deleted Content added
Erel Segal (talk | contribs) |
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 |
||
| (23 intermediate revisions by 9 users not shown) | |||
Line 1:
{{Short description|Linear programming for Combinatorial optimization}}
The '''configuration linear program''' ('''configuration-LP''') is a
== In bin packing ==
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, where each 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|archive-url=https://web.archive.org/web/20210715093252/https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3 |archive-date=2021-07-15 }}</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.
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:
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>\sum_{c\in C}a_{s,c}x_c \geq n_s</math> for all ''s'' in ''S'' (- all ''n<sub>s</sub>'' items of size ''s'' are packed). ▼
minimize <math>\sum_{c\in C}x_c</math> subject to
▲<math>\sum_{c\in C}a_{s,c}x_c \geq n_s</math> for all ''s'' in ''S'' (
<math>x_c\in\{0,\ldots,n\}</math> for all ''c'' in ''C'' (- there are at most ''n'' bins overall, so at most ''n'' of each individual configuration). </blockquote>The configuration LP is an [[integer linear program]], so in general it is NP-hard. Moreover, even the problem itself is generally very large: it has ''C'' variables and ''S'' constraints. If the smallest item size is ''eB'' (for some fraction ''e'' in (0,1)), then there can be up to 1/''e'' items in each bin, so the number of configurations ''C'' ~ ''S''<sup>1/''e''</sup>, which can be very large if ''e'' is small (if e is considered a constant, then the integer LP can be solved by exhaustive search: there are at most ''S<sup>1/e</sup>'' configurations, and for each configuration there are at most ''n'' possible values, so 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" />▼
<math>x_c\in\{0,\ldots,n\}</math> for all ''c'' in ''C'' (there are at most ''n'' bins overall, so at most ''n'' of each individual configuration).
</blockquote>
▲
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.
=== 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
* ''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> minimize <math> ~\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 (''n''<sub>1</sub>,...,''n<sub>S</sub>''). === 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:
<blockquote> maximize<math> </blockquote> It has ''S'' variables ''y''<sub>1</sub>,...,''y<sub>S</sub>'', and ''C'' constraints Second, they apply a variant of the [[ellipsoid method]], which does not need to list all the constraints - it just needs a ''[[
Third, they show that, with an approximate solution to the knapsack problem, one can get an approximate solution to the dual LP, and from this, an approximate solution to the primal LP; see [[Karmarkar-Karp bin packing algorithms]].
Line 47 ⟶ 62:
=== 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<sup>2</sup>(''n'')). Later, Hoberg and Rothvoss<ref name=":3">{{
== 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 book|last1=Csirik|first1=Janos|last2=Johnson|first2=David S.|last3=Kenyon|first3=Claire|chapter=Better approximation algorithms for bin covering |date=2001-01-09 |chapter-url=https://dl.acm.org/doi/abs/10.5555/365411.365533 |title=SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms |publisher=Society for Industrial and Applied Mathematics |pages=557–566|isbn=978-0-89871-490-6}}</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. The dual of this LP is more complex and cannot be solved by a simple knapsack-problem separation oracle. Csirik, Johnson and Kenyon<ref name=":24" /> present a different method to solve it approximately in time exponential in 1/epsilon. Jansen and Solis-Oba'''<ref name=":32">{{Cite book|last1=Jansen|first1=Klaus|last2=Solis-Oba|first2=Roberto|title=Algorithms and Computation |chapter=An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering |series=Lecture Notes in Computer Science |date=2002-11-21 |volume=2518 |chapter-url=https://dl.acm.org/doi/abs/10.5555/646345.689912 |publisher=Springer-Verlag |pages=175–186|doi=10.1007/3-540-36136-7_16|isbn=978-3-540-00142-3}}</ref>''' present an improved method to solve it approximately in time exponential in 1/epsilon.
== In machine scheduling ==
Line 76 ⟶ 89:
[[Category:Number partitioning]]
[[Category:Job scheduling]]
[[Category:Linear programming]]
| |||