Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 09:50, 14 January 2022

Revision as of 10:10, 14 January 2022

Line 135:

* If the approximate oracle returns a solution with value larger than 1, then <math>\mathbf{y}_t</math> is definitely infeasible, and the solution correspond to a configuration that violates a constraint '''a'''. We do a "feasibility cut" in '''<math>\mathbf{y}_t</math>''', cutting the ellipsoid all points '''y''' for which <math>\mathbf{a}\cdot \mathbf{y} > 1</math>.

* If the approximate oracle returns a solution with value at most 1, then '''<math>\mathbf{y}_t</math>''' may or may not be feasible, but '''<math>\mathbf{y}_t</math>''' rounded down (denote it by '''<math>\mathbf{z}_t</math>''') is feasible. By definition of the rounding, we know that <math>\mathbf{n}\cdot \mathbf{z}_t \geq \mathbf{n}\cdot \mathbf{y}_t - \mathbf{n}\cdot \mathbf{1}\cdot (\delta/n) = \mathbf{n}\cdot \mathbf{y}_t - \delta</math>. We still do an "optimality cut" in '''<math>\mathbf{y}_t</math>''': we cut from the ellipsoid all points '''y''' for which <math>\mathbf{n}\cdot \mathbf{y} < \mathbf{n}\cdot \mathbf{y}_t</math>. For the removed points, <math>\mathbf{n}\cdot \mathbf{y} < \mathbf{n}\cdot \mathbf{z}_t+\delta</math>. Therefore, the remaining points are within at most <math>\delta</math> of the optimal solution.

Using the approximate separation oracle gives a feasible solution '''y*''' to the dual LP, with <math>\mathbf{n}\cdot \mathbf{y^*} \geq LOPT-\delta</math>, after at most ''<math>Q</math>'' iterations, where <math>Q = 4m^2 \ln(mn/g\delta)</math>. The total run-time of the ellipsoid method with the approximate separation oracle is <math>O(Q m n /\delta)</math>.

=== Eliminating constraints ===

During the ellipsoid method, we use at most ''Q'' constraints of the form <math>\mathbf{a}\cdot \mathbf{y} \leq 1</math>. All the other constraints can be eliminated, since they have no effect on the outcome '''y*''' of the ellipsoid method. We can eliminate even more constraints. It is known that, in any LP with ''m'' variables, there is a set of ''m'' constraints that is sufficient for determining the optimal solution (that is, the optimal value is the same even if only these ''m'' constraints are used). We can repeatedly run the ellipsoid method as above, each time trying to remove a specific set of constraints. If the resulting error is at most <math>\delta</math>, then we remove these constraints permanently. It can be shown that we need at most <math>\approx (Q/m) + m\ln(Q/m)</math> eliminations, so the accumulating error is at most <math>\approx \delta\cdot [(Q/m) + m\ln(Q/m)]</math>. If we try sets of constraints deterministically, then in the worst case, one out of ''m'' trials succeeds, so we need to run the ellipsoid method at most <math>\approx m\cdot[(Q/m) + m\ln(Q/m)]
= Q+m^2\ln(Q/m)
</math> times. If we choose the constraints to remove at random, then the expected number of iterations is <math> O(m)\cdot[1 + \ln(Q/m)]</math>.

Finally, we have a reduced dual LP, with only ''m'' variables and ''m'' constraints. The optimal value of the reduced LP is at least <math> LOPT-\epsilon</math>, where <math>\epsilon \approx \delta\cdot [(Q/m) + m\ln(Q/m)]</math>.

=== Solving the primal LP ===

By the [[Dual linear program|LP duality theorem]], the minimum value of the primal LP equals the maximum value of the dual LP, which we denoted by LOPT. Once we have a reduced dual LP, we take its dual, and take a reduced primal LP. This LP has only ''m'' variables - corresponding to only ''m'' out of ''C'' configurations. The maximum value of the reduced dual LP is at least <math> LOPT-\epsilon</math>. It can be shown{{Clarify|date=January 2022}} that the optimal solution of the reduced primal LP is at most <math> LOPT+\epsilon</math>. The solution gives a near-optimal bin packing, using at most ''m'' configurations.

Once we have a reduced dual LP, we take its dual, and take a reduced primal LP. This LP has only ''m'' variables - corresponding to only ''m'' out of ''C'' configurations. By the [[Dual linear program|LP duality theorem]], the minimum value of this reduced primal LP equals the maximum value of the reduced dual LP, which is at least <math> LOPT-\epsilon</math>.

The total run-time of the deterministic algorithm, when all items are larger than ''<math>g\cdot B</math>, is:''

<math>O\left(\frac{Q m n}{\delta}

\cdot( Q+m^2\ln\frac{Q}{m})

\right)

=

O

\left(\frac{Q^2 m n + Q m^3 n\ln\frac{Q}{m}}{\delta}

\right)

\approx

<math>O\left(Sm^8 \logln{Sm} \logln^2(\frac{Sm n}{eg h\epsilon}) + \frac{Sm^4 n \logln{Sm}}{h\epsilon}\logln(\frac{Sm n}{eg h\epsilon}) \right)</math>,

The expected total run-time of the randomized algorithm is: <math>O\left(Sm^7 \log{Sm} \log^2(\frac{Sm n}{eg h\epsilon}) + \frac{Sm^4 n \log{Sm}}{h\epsilon}\log(\frac{Sm n}{eg h\epsilon}) \right)</math>.

by running this procedure iteratively: we choose a set of constraints, remove them, and find an approximate solution of the dual without these constraints. If the new solution is within the tolerance ''t'' of the old solution, then the constraints are dropped; otherwise, they are retained and a new set of constraints is tried. It can be shown that, after sufficiently many attempts, we will get a dual LP with only ''m'' constraints, which has the same (approximate) solution as the original dual LP. The run-time is <math>O\left(m^8 \log{m} \log^2(\frac{m n}{g h}) + \frac{m^4 n \log{m}}{h}\log(\frac{m n}{g h}) \right)</math>. If the constraints to remove are chosen at random, then the run-time becomes <math>O\left(m^7 \log{m} \log^2(\frac{m n}{g h}) + \frac{m^4 n \log{m}}{h}\log(\frac{m n}{g h}) \right)</math>.

Karmarkar and Karp present an algorithm that, for any tolerance factor ''h'', finds a basic feasible solution of cost at most LOPT(I) + ''h'', and runs in time:

<math>O\left(S^8 \log{S} \log^2(\frac{S n}{e h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{e h}) \right)</math>,

where ''S'' is the number of different sizes, ''n'' is the number of different items, and the size of the smallest item is ''eB''. In particular, if ''e'' ≥ 1/''n'' and ''h''=1, the algorithm finds a solution with at most LOPT+1 bins in time: <math>O\left(S^8 \log{S} \log^2{n} + S^4 n \log{S}\log{n} \right)</math>.

A randomized variant of this algorithm runs in expected time:

<math>O\left(S^7 \log{S} \log^2(\frac{S n}{e h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{e h}) \right)</math>.

Their algorithm uses [[separation oracle]] to the dual LP.

== Guarantees ==

Karmarkar and Karp presented four different algorithms. The run-time of all these algorithms depends on a function <math>T(\cdot,\cdot)</math>, which is a polynomial function describing the time it takes to solve the [[configuration linear program]]: <math>T(m,n)\in O(m^8\log{m}\log^2{n} + m^4 n \log{m}\log{n} )</math>. The algorithms attain the following guarantees: