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

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 of size 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:

• 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 all s in S (- all n_s 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 ~ S^1/e, which can be very large if e is small.

However, this ILP serves as a basis for several approximation algorithms. The main idea of these algorithms is to reduce the original instance into a new instance in which S is small and e is large, so C is relatively small. Then, the ILP can be solved either by complete search (if S, C are sufficiently small), or by relaxing it into a fractional LP.

The fractional LP

The fractional configuration LP of bin-packing It is the linear programming relaxation of the above ILP. It replaces the last constraint $x_{c}\in \{0,\ldots ,n\}$ with the constraint $x_{c}\geq 0$. In other words, each configuration can be used a fractional number of times.

• 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:

${\text{minimize}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{s.t.}}~~A\mathbf {x} \geq \mathbf {n} ~~~{\text{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 (s₁,...,s_S).

Let FOPT(I) be the optimal solution of the fractional LP for instance I, and OPT(I) the optimal solution of the integral LP. Let AVG be the sum of all sizes divided by B. The following relations are obvious:

• AVG(I) ≤ FOPT(I), since AVG(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.
• FOPT(I) ≤ OPT(I), since FOPT(I) is a solution to a minimization problem with fewer constraints.
• OPT(I) < 2*AVG(I), since in any packing with at least 2*AVG(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 presented an algorithm for rounding an optimal solution for the fractional LP into a solution for the integral ILP, proving that OPT(I) ≤ FOPT(I) + S/2:

• Let x be an optimal basic feasible solution of the fractional LP. By definition, the value of x is FOPT(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*AVG(R) bins (since if there are at least 2*AVG(R) bins, the two smallest ones can be combined).
• The smallest of these packings requires min(S, 2*AVG(R)) ≤ average(S, 2*AVG(R)) = AVG(R) + S/2.
• Adding to this the rounded-down bins of the principal part yields FOPT(I) + S/2.
• The execution time of this conversion algorithm is O(n log n).

The dual LP

The dual linear program of the fractional LP is:

${\text{maximize}}~~\mathbf {n} \cdot \mathbf {y} ~~~{\text{s.t.}}~~\mathbf {y} ^{T}A\leq \mathbf {1} ~~~{\text{and}}~~\mathbf {y} \geq 0$.

It has S variables y₁,...,y_S, and C constraints - one for each configuration. It has the following economic interpretation. For each size s, we should determine a nonnegative price y_s. 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.

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, for any tolerance factor h, finds a basic feasible solution of cost at most FOPT(I) + h, and runs in time:

$O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$,

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 FOPT+1 bins in time: $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$.

A randomized variant of this algorithm runs in expected time:

$O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$.

Their algorithm uses separation oracle to the dual LP.

Approximation algorithms

The general scheme of approximation algorithms is:

• Separate the items to "small" (smaller than eB, for some fraction e in (0,1)) and "large" (at least eB).
• Handle the large items first:
  • Round the item sizes in some way, such that the number of different sizes is at most some constant S.
  • Write the integer LP for the rounded instance. Since the number of sizes is S and there are at most 1/e items in each bin, the total number of configurations is at most S^1/e.
  • Solve the integer LP.
• Allocate the small items greedily, e.g. with next-fit bin packing. If no new bins are created, then we are done. 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 ≤ (1+2e)OPT+1.

The algorithms differ in how they round the instance and in how the solve the integer LP.

Rounding the large-items instance

Lueker and de-la-Vega and 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. The solution of the rounded instance is feasible for the original instance too, but the number of bins may be larger than necessary. To quantify the loss, 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 fewer 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.

If all items are large (of size at least eB), then each bin in OPT contains at most 1/e items (of size at least eB), so OPT must be at least en. Therefore, Bins(U) ≤ (1+e)OPT.

Karmarkar and Karp present a more efficient rounding method which they call geometric rounding (in contrast to the linear rounding of de-la-Vega and Lueker).

Solving the integer LP for the rounded instance

A simple way to solve the integer LP is by exhaustive search. Since there are at most S^1/e configurations, and for each configuration there are at most n possible values, 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.

Based on these innovations, they present 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))$.

Improvements

This technique was later improved by several authors:

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