Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 10:58, 13 January 2022

Revision as of 13:32, 13 January 2022

Line 101:

== Step 4. Solving the fractional LP ==

The main challenge in solving the fractional LP is that it may have a huge number of variables - a variable for each possible configuration.

=== The dual LP ===

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 ''Sm'' variables ''y''<sub>1</submath>y_1,...\ldots,''y<sub>Sy_m</submath>'', and ''C'' constraints - onea constraint for each configuration. It has the following economic interpretation. For each size ''s'', we should determine a nonnegative price ''y<submath>sy_i</submath>''. 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 -

* Assert that '''y''' is infeasible, and return a specific constraint that is violated, that is, a vector '''a''' such that <math>\mathbf{a}\cdot \mathbf{y} > 1</math>.

=== A separation oracle for the dual LP ===

We are given some ''m'' non-negative numbers <math>y_1,\ldots,y_m</math>. We have to decide between the following two options:

* For every feasible configuration, the sum of <math>y_i</math> corresponding to this configuration is at most 1; this means that '''y''' is feasible.

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

* If the total value of the optimal knapsack solution is larger than 1, then we say that '''y''' is infeasible, and the items in the optimal knapsack solution correspond to a configuration that violates a constraint (since <math>\mathbf{a}\cdot \mathbf{y} > 1</math> for the vector '''a''' that corresponds to this configuration).

=== Solving the fractional LP ===