Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 01:13, 2 February 2023

Revision as of 21:01, 28 February 2023

Line 111:

The [[dual linear program]] of the fractional LP is:<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 ''m'' variables <math>y_1,\ldots,y_m</math>, and ''C'' constraints - a constraint for each configuration. It has the following economic interpretation. For each size ''s'', we should determine a nonnegative price ''<math>y_i</math>''. 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. This LP now has only ''m'' variables, but a huge number of constraints. Even listing all the constraints is infeasible.

Fortunately, it is possible to solve the problem up to any given precision without listing all the constraints, by using a variant of the [[ellipsoid method]]. This variant gets as input, a ''[[Separation oracle|''separation oracle]]'']]: a function that, given a vector '''y''' ≥ 0, returns one of the following two options:

* Assert that '''y''' is feasible, that is, <math>A^T \mathbf{y} \leq \mathbf{1}</math>; or -

Line 128:

* There exists a feasible configuration for which the sum of <math>y_i</math> is larger than 1; this means that '''y''' is infeasible. In this case, we also have to return the configuration.

This problem can be solved by solving a ''[[Knapsack problem|''knapsack problem]]'']], where the item values are <math>y_1,\ldots,y_m</math>, the item weights are <math>s_1,\ldots,s_m</math>, and the weight capacity is ''B'' (the bin size).

* If the total value of the optimal knapsack solution is at most 1, then we say that '''y''' is feasible.