Configuration linear program

The configuration linear program (configuration-LP) is a particular linear programming used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem. Later, it has bin applied to bin packing and job scheduling. In the configuration-LP, there is a variable for each possible combination of items ("configuration") in a bin. Usually, the number of such combinations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.

In bin packing

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 of size B. A feasible configuration is a set of sizes with a sum of at most B. For 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.

For each size s and configuration c, denote:

• n_s - the number of items of size s.
• a_s,c - the number of occurences of size s in configuration c.
• x_c - a variable denoting the number of bins with configuration c.

Then, the configuration LP of bin-packing is:

${\text{minimize}}~~~\sum _{c\in C}x_{c}~~~{\text{subject to}}$

$\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ for every size s (- all n_s items of size s are packed)

$x_{c}\in \{0,\ldots ,n\}$ (- there are at most n configurations of each type).

In the special-special case in which the number of sizes is some constant S, and each size is at least eB (for some fraction e<1), there are at most 1/e items in each bin, so the total number of configurations is at most S^1/e. Therefore, the configuration LP has at most S^1/e variables and S constraints, and it can be solved by exhaustive search in time $S\cdot n^{S^{1/e}}$, which is polynomial in n.

Consider now a less-special case in which the number of sizes is general, but each size is still at least eB. Fernandez de la Vega and Lueker invented the idea of adaptive input rounding. Order the items by their size, and group them into 1/e² groups of cardinality ne². In each group, round the sizes upwards to the maximum size in the group. Now, there are only 1/e² different sizes, so the problem can be solved exactly in time $(1/e^{2})\cdot n^{(1/e^{2})^{1/e}}$, which is polynomial in n when e is constant. The resulting solution is feasible for the original instance too, but the number of bins may be larger than necessary. To analyze the approximation factor, consider the instance rounded down to the maximum size in the previous group (the first group is rounded down to 0). The rounded-down instance D is almost equal to the rounded-up instance U, except that in D there are some ne² zeros while in U there are some ne² large items instead; but their size is at most B. Therefore, U requires at most ne² more bins than D. Since D requires less bins than the optimum, we get that Bins(U) ≤ OPT + ne², that is, we have an additive error that can be made as small as we like by choosing e. Moreover, since each bin in OPT can contain at most 1/e items (of size at least eB), OPT must be at least en. Therefore, Bins(U) ≤ (1+e)OPT.

Finally, consider the general case in which there are also some small items, of size less than eB. These items can be added greedily into the bins with the large items using e.g. Next-fit bin packing. If no new bins are created, then the number of bins is still at most (1+e)OPT. If new bins are created, this means that all bins (except maybe the last one) are full up to at least (1-e)B. Therefore, the number of bins is at most OPT/(1-e)+1, which is (1+O(e))OPT+1.

This technique was later improved by several authors:

• Karmarkar and Karp presented an algorithm with run-time polynomial in $n$ and $1/\varepsilon$. Their algorithm finds a solution with size at most $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(OPT))$.

• Rothvoss presented an algorithm that generates a solution with size at most $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$.

• Hoberg and Rothvoss improved this algorithm to generate a solution with size at most $\mathrm {OPT} +O(\log(\mathrm {OPT} ))$. The algorithm is randomized, and its running-time is polynomial in the total number of items.

In machine scheduling

Consider the problem of unrelated-machines scheduling. In this problem, there are some m different machines that should process some n different jobs. When machine i processes job j, it takes time p_i,j. The goal is to partition the jobs among the machines such that maximum completion time of a machine is as small as possible. The decision version of this problem is: given time T, is there a partition in which the completion time of all machines is at most T?

For each machine i, there are finitely many subsets of jobs that can be processed by machine i in time at most T. Each such subset is called a configuration for machine i. Denote by C_i(T) the set of all configurations for machine i, given time T. For each machine i and configuration c in C_i(T), define a variable $x_{i,c}$ which equals 1 iff the actual configuration used in machine i is c, and 0 otherwise. Then, the LP constraints are:

• $\sum _{c\in C_{i}(T)}x_{i,c}=1$ for every machine i in 1,...,m;
• $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ for every job j in 1,...,n;
• $x_{i,j}\in \{0,1\}$ for every i, j.

Properties

The integrality gap of the configuration-LP for unrelated-machines scheduling is 2.