[1][2] Later, it has been applied to the bin packing[3][4] and job scheduling problems.
Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.
The configuration LP is an integer linear program, so in general it is NP-hard.
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
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 configuration LP of bin-packing It is the linear programming relaxation of the above ILP.
The relaxation was first presented by Gilmore and Gomory,[2] and it is often called the Gilmore-Gomory linear program.
Karmarkar and Karp[9] present an algorithm that overcomes this problem.
First, they construct the dual linear program of the fractional LP:
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.
Second, they apply a variant of the ellipsoid method, which does not need to list all the constraints - it just needs a separation oracle.
A separation oracle is an algorithm that, given a vector y, either asserts that it is feasible, or finds a constraint that it violates.
The separation oracle for the dual LP can be implemented by solving the knapsack problem with sizes s and values y: if the optimal solution of the knapsack problem has a total value at most 1, then y is feasible; if it is larger than 1, than y is not feasible, and the optimal solution of the knapsack problem identifies a configuration for which the constraint is violated.
All in all, for any tolerance factor h, finds a basic feasible solution of cost at most LOPT(I) + h, and runs in time:
A randomized variant of this algorithm runs in expected time:
Karmarkar and Karp further developed a way to round the fractional LP into an approximate solution to the integral LP; see Karmarkar-Karp bin packing algorithms.
Their proof shows that the additive integrality gap of this LP is in O(log2(n)).
Later, Hoberg and Rothvoss[10] 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.
The problem with this LP is that, in the bin-covering problem, handling small items is problematic, since small items may be essential for the optimal solution.
With small items allowed, the number of configurations may be too large even for the technique of Karmarkar and Karp.
Csirik, Johnson and Kenyon[11] present an alternative LP.
The additional constraint guarantees that the "vacant space" in the bins can be filled by the small items.
The dual of this LP is more complex and cannot be solved by a simple knapsack-problem separation oracle.
Csirik, Johnson and Kenyon[11] present a different method to solve it approximately in time exponential in 1/epsilon.
Jansen and Solis-Oba[12] present an improved method to solve it approximately in time exponential in 1/epsilon.
In the problem of unrelated-machines scheduling, there are some m different machines that should process some n different jobs.
When machine i processes job j, it takes time pi,j.
Then, the LP constraints are: The integrality gap of the configuration-LP for unrelated-machines scheduling is 2.