Configuration linear program: Difference between revisions

Revision as of 11:47, 14 January 2022

Revision as of 22:50, 16 January 2022

Line 7:

In the [[bin packing|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'':<ref name=":2">{{Cite web|last=Claire Mathieu|title=Approximation Algorithms Part I, Week 3: bin packing|url=https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3|url-status=live|website=Coursera}}</ref> 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:

Line 19:

<math>\sum_{c\in C}a_{s,c}x_c \geq n_s</math> for all ''s'' in ''S'' (- all ''n_s'' items of size ''s'' are packed).

<math>x_c\in\{0,\ldots,n\}</math> for all ''c'' in ''C'' (- there are at most ''n'' bins overall, so at most ''n'' of each individual configuration). </blockquote>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 (if e is considered a constant, then the integer LP can be solved by exhaustive search: there are at most ''S^1/e'' configurations, and for each configuration there are at most ''n'' possible values, so there are at most <math> n^{S^{1/e}}</math> combinations to check. For each combination, we have to check ''S'' constraints, so the run-time is <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n'' when ''S, e'' are constant).<ref name=":2" />

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.

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 (''n''₁,...,''n_S'').

=== Solving the fractional LP ===

Let LOPT(I) be the optimal solution of the fractional LP for instance I, and OPT(I) the optimal solution of the integral LP. Let FOPT 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:

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">{{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> presentedpresent an algorithm for ''rounding'' an optimal solution for the fractional LP into a solution for the integral ILP, proving that overcomes OPT(I) ≤ LOPT(I) + S/2:this problem.

TheFirst, they construct the [[dual linear program]] of the fractional LP is:<blockquote><math>\text{maximize}~~\mathbf{n}\cdot \mathbf{y}~~~\text{s.t.}~~ A^T \mathbf{y} \leq \mathbf{1}~~~\text{and}~~ \mathbf{y}\geq 0</math>.</blockquote>It has ''S'' variables ''y''₁,...,''y_S'', and ''C'' constraints - one for each configuration. It has the following economic interpretation.<ref name=":12" /> 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.

* FOPT(I) ≤ LOPT(I), since FOPT(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.

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

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

Second, they apply a variant of the [[ellipsoid method]], which does not need to list all the constraints - it just needs a [[Separation oracle|''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.

=== 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) ≤ LOPT(I) + S/2:

* Let '''x''' be an optimal [[basic feasible solution]] of the fractional LP. By definition, the value of '''x''' is LOPT(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*FOPT(''R'') bins (since if there are at least 2*FOPT(''R'') bins, the two smallest ones can be combined).

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

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

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

Third, they show that, with an approximate solution to the knapsack problem, one can get an approximate solution to the dual LP, and from this, an approximate solution to the primal LP; see [[Karmarkar-Karp bin packing algorithms]].

=== The dual LP ===

The [[dual linear program]] of the fractional LP is:<blockquote><math>\text{maximize}~~\mathbf{n}\cdot \mathbf{y}~~~\text{s.t.}~~ A^T \mathbf{y} \leq \mathbf{1}~~~\text{and}~~ \mathbf{y}\geq 0</math>.</blockquote>It has ''S'' variables ''y''₁,...,''y_S'', and ''C'' constraints - one for each configuration. It has the following economic interpretation.<ref name=":12" /> 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.

All in all, for any tolerance factor ''h'', finds a basic feasible solution of cost at most LOPT(I) + ''h'', and runs in time:

=== 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 LOPT(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 LOPT+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:

A randomized variant of this algorithm runs in expected time:

<math>O\left(S^7 \log{S} \log^2(\frac{S n}{e h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{e h}) \right)</math>.

=== Rounding the fractional LP ===

Their algorithm uses [[separation oracle]] to the dual LP.

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(log²(''n'')). Later, Hoberg and Rothvoss<ref name=":3">{{Citation|last1=Hoberg|first1=Rebecca|title=A Logarithmic Additive Integrality Gap for Bin Packing|date=2017-01-01|url=https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.172|work=Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms|pages=2616–2625|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611974782.172|isbn=978-1-61197-478-2|access-date=2021-02-10|last2=Rothvoss|first2=Thomas|s2cid=1647463}}</ref> 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.

=== 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 <math> n^{S^{1/e}}</math> combinations to check. For each combination, we have to check ''S'' constraints, so the run-time is <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n'' when ''S, e'' are constant.<ref name=":2">{{Cite web|last=Claire Mathieu|title=Approximation Algorithms Part I, Week 3: bin packing|url=https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3|url-status=live|website=Coursera}}</ref>

== 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''?