Configuration linear program: Difference between revisions

Revision as of 20:19, 8 January 2022

Revision as of 20:27, 8 January 2022

Line 29:

In short, the fractional LP can be written as follows:<blockquote><math>\text{minimize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\geq \mathbf{n}~~~\text{and}~~ \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 (''s''₁,...,''s_S'').

Let FOPTLOPT(I) be the optimal solution of the fractional LP for instance I, and OPT(I) the optimal solution of the integral LP. Let TOPTFOPT be the sum of all sizes divided by ''B''; this is the theoretically-optimal number of bins, when all bins are completely filled with items or item-fractions. The following relations are obvious:

* TOPTFOPT(I) ≤ FOPTLOPT(I), since TOPTFOPT(I) is the (possibly fractional) number of bins when all bins are completely filled with items or fractions of items. Clearly, no solution can be more efficient.

* FOPTLOPT(I) ≤ OPT(I), since FOPTLOPT(I) is a solution to a minimization problem with fewer constraints.

* OPT(I) < 2*TOPTFOPT(I), since in any packing with at least 2*TOPTFOPT(I) bins, the sum of the two least-full bins is at most ''B'', so they can be combined into a single bin.

=== Rounding the fractional LP ===

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> presented an algorithm for ''rounding'' an optimal solution for the fractional LP into a solution for the integral ILP, proving that OPT(I) ≤ FOPTLOPT(I) + S/2:

* Let '''x''' be an optimal [[basic feasible solution]] of the fractional LP. By definition, the value of '''x''' is FOPTLOPT(I). Since the fractional LP has ''S'' constraints, '''x''' has at most ''S'' nonzero variables, that is, at most ''S'' different configurations are used. We construct from '''x''' an integral packing consisting of a ''principal part'' and a ''residual part''.

* The principal part contains floor(''x_c'') bins of each configuration ''c'' for which ''x_c'' > 0.

* For the residual part (denoted by ''R''), we construct two candidate packings:

** A single bin of each configuration ''c'' for which ''x_c'' > 0; all in all ''S'' bins are needed.

** A greedy packing, with fewer than 2*TOPTFOPT(''R'') bins (since if there are at least 2*TOPTFOPT(''R'') bins, the two smallest ones can be combined).

* The smallest of these packings requires min(S, 2*TOPTFOPT(''R'')) ≤ average(S, 2*TOPTFOPT(''R'')) = TOPTFOPT(R) + S/2.

* Adding to this the rounded-down bins of the principal part yields FOPTLOPT(I) + S/2.

* The execution time of this conversion algorithm is O(''n'' log ''n'').

Line 50:

=== 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" /> present an algorithm that, for any tolerance factor ''h'', finds a basic feasible solution of cost at most FOPTLOPT(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 FOPTLOPT+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: