Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 32:
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 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> present an algorithm that overcomes this problem.
First, they construct the [[dual linear program]] of the fractional LP:<blockquote><math>\text{maximize}~~\mathbf{n}\cdot \mathbf{y}~~~\text{s.t.}~~ A^T \mathbf{y} \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
Second, they apply a variant of the [[ellipsoid method]], which does not need to list all the constraints - it just needs a [[Separation oracle|''separation oracle'']]. A separation oracle is an algorithm that, given a vector '''y''', either asserts that it is feasible, or finds a constraint that it violates. The separation oracle for the dual LP can be implemented by solving the [[knapsack problem]] with sizes '''s''' and values '''y''': if the optimal solution of the knapsack problem has a total value ''at most'' 1, then '''y''' is feasible; if it is ''larger'' than 1, than '''y''' is ''not'' feasible, and the optimal solution of the knapsack problem identifies a configuration for which the constraint is violated.
Line 50:
== 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> 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 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 improved method to solve it approximately in time exponential in 1/epsilon.
== In machine scheduling ==
| |||