The integral LP In the
bin packing problem, there are
n items with different sizes. The goal is to pack the items into a minimum number of bins, where each bin can contain at most
B. A
feasible configuration is a set of sizes with a sum of at most
B. •
Example: suppose the item sizes are 3,3,3,3,3,4,4,4,4,4, and
B=12. Then the possible configurations are: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. If we had only three items of size 3, then we could not use the 3333 configuration. Denote by
S the set of different sizes (and their number). Denote by
C the set of different configurations (and their number). For each size
s in
S and configuration
c in
C, denote: •
ns - the number of items of size
s. •
as,
c - the number of occurrences of size
s in configuration
c. •
xc - a variable denoting the number of bins with configuration
c. Then, the
configuration LP of bin-packing is: minimize \sum_{c\in C}x_c subject to \sum_{c\in C}a_{s,c}x_c \geq n_s for all
s in
S (all
ns items of size
s are packed). x_c\in\{0,\ldots,n\} for all
c in
C (there are at most
n bins overall, so at most
n of each individual configuration). The configuration LP is an
integer linear program, so in general it is NP-hard. Moreover, even the problem itself is generally very large: it has
C variables and
S constraints. If the smallest item size is
eB (for some fraction
e in (0,1)), then there can be up to 1/
e items in each bin, so the number of configurations
C ~
S1/
e, which can be very large if
e is small (if e is considered a constant, then the integer LP can be solved by exhaustive search: there are at most
S1/e configurations, and for each configuration there are at most
n possible values, so there are at most n^{S^{1/e}} combinations to check. For each combination, we have to check
S constraints, so the run-time is S\cdot n^{S^{1/e}}, which is polynomial in
n when
S, e are constant). •
Example: suppose there are 31 items of size 3 and 7 items of size 4, and the bin-size is 10. The configurations are: 4, 44, 34, 334, 3, 33, 333. The constraints are [0,0,1,2,1,2,3]*
x=31 and [1,2,1,1,0,0,0]*
x=7. An optimal solution to the fractional LP is [0,0,0,7,0,0,17/3] That is: there are 7 bins of configuration 334 and 17/3 bins of configuration 333. Note that only two different configurations are needed. In short, the fractional LP can be written as follows: minimize ~\mathbf{1}\cdot \mathbf{x}~ s.t. ~\mathbf{A} \mathbf{x}\geq \mathbf{n}~ and ~\mathbf{x}\geq 0~ 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 (
n1,...,
nS).
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 present an algorithm that overcomes this problem. First, they construct the
dual linear program of the fractional LP: maximize~\mathbf{n}\cdot \mathbf{y}~s.t.~A^T \mathbf{y} \leq \mathbf{1}~ and ~\mathbf{y}\geq 0. It has
S variables
y1,...,
yS, and
C constraints: for each configuration
c, there is a constraint A^c\cdot y\leq 1, where A^c is the column of
A representing the configuration
c. 3It has the following economic interpretation. improved their result and proved that the integrality gap is in O(log(
n)). The best known lower bound on the integrality gap is a constant Ω(1). Finding the exact integrality gap is an
open problem. == In bin covering ==