Configuration linear program: Difference between revisions

Revision as of 20:30, 25 November 2021

Latest revision as of 13:04, 25 August 2025

(48 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Linear programming for Combinatorial optimization}}

The '''configuration linear program''' ('''configuration-LP''') is a particular [[linear programming]] technique used for solving [[combinatorial optimization]] problems. It was introduced in the context of the [[cutting stock problem]].<ref>{{Cite journal|last=Eisemann|first=Kurt|date=1957-04-01|title=The Trim Problem|url=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.3.3.279|journal=Management Science|volume=3|issue=3|pages=279–284|doi=10.1287/mnsc.3.3.279|issn=0025-1909|url-access=subscription}}</ref><ref name="Gilmore61">{{cite journal | jstor=167051 | title=A Linear Programming Approach to the Cutting-Stock Problem | last1=Gilmore | first1=P. C., | last2=Gomory | first2=R. E. Gomory| (1961).journal=Operations ''[https://web.archive.org/web/20190219020906/http://pdfs.semanticscholar.org/1417/64b5e86dc6c2647dfce48098794c79d5a38b.pdfResearch A| lineardate=1961 programming| approachvolume=9 to| theissue=6 cutting-stock| problem]''.pages=849–859 | Operationsdoi=10.1287/opre.9.6.849 Research| 9:s2cid=8079477 849-859}}</ref> Later, it has binbeen applied to the [[bin packing]]<ref name=":1">{{Cite journalbook|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|datetitle=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982-11-01) |titlechapter=An efficient approximation scheme for the one-dimensional bin-packing problem |urldate=https://ieeexplore.ieee.org/abstract/document/4568405/?casa_token=9mn1982-Ej2IsAQAAAAA:F6ppNaGyr23r55exi3PezsKFWbcKOoTH11-GOZ6JQre9FYdTZGAFxsnn6SnazQs7GYvm3KjuJx-yw|journal=23rd01 Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908}}</ref><ref>{{Cite journalbook|last1=Bansal|first1=Nikhil|last2=Caprara|first2=Alberto|last3=Sviridenko|first3=Maxim|date=2006-10-01|title=Improved approximation algorithms for multidimensional bin packing problems|url=https://ieeexplore.ieee.org/abstract/document/4031404?casa_token=1lyd-glredEAAAAA:wrrFIGkFxkirjYvEfDXcxnzz2U-wfCznKYsRUbEnUpNtDN0l7_BErBWVQ9LgWYzgDJ_JNupgUFU|journal=2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) |chapter=Improved approximation algorithms for multidimensional bin packing problems |date=2006-10-01|pages=697–708|doi=10.1109/FOCS.2006.38|isbn=0-7695-2720-5|s2cid=7690347}}</ref> and [[Optimal job scheduling|job scheduling]] problems.<ref name=":0">{{Cite journal|last1=Verschae|first1=José|last2=Wiese|first2=Andreas|date=2014-08-01|title=On the configuration-LP for scheduling on unrelated machines|url=https://doi.org/10.1007/s10951-013-0359-4|journal=Journal of Scheduling|language=en|volume=17|issue=4|pages=371–383|doi=10.1007/s10951-013-0359-4|s2cid=34229676|issn=1099-1425|arxiv=1011.4957}}</ref><ref>{{cite arxivarXiv|last1=Knop|first1=Dušan|last2=Koutecký|first2=Martin|date=2020-03-04|title=Scheduling Kernels via Configuration LP|class=cs.DS|eprint=2003.02187}}</ref> In the configuration-LP, there is a variable for each possible combination''configuration'' - each possible [[multiset]] of items ("configuration")that can fit in a single bin (these configurations are also known as ''patterns'') . Usually, the number of such combinationsconfigurations 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|bin packing problem]], there are ''n'' items with different sizes. The goal is to pack the items into a minimum number of bins, ofwhere sizeeach bin can contain at most ''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|archive-url=https://web.archive.org/web/20210715093252/https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3 |archive-date=2021-07-15 }}</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:

* ''n_s'' - the number of items of size ''s''.

* ''a_s''_,''c'' - the number of occurencesoccurrences 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: <blockquote><math>\text{minimize}~~~\sum_{c\in C}x_c~~~\text{subject to}</math>

<blockquote>

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

minimize <math>\sum_{c\in C}x_c</math> subject to

<math>x_c\in\sum_{0,c\ldotsin C}a_{s,n\c}x_c \geq n_s</math> for all ''cs'' in ''CS'' (- there are at mostall ''n_s'' configurationsitems of eachsize type''s'' are packed). </blockquote>

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

=== Solution ===

</blockquote>

The configuration LP is an [[integer linear program]], so in general it is NP-hard. But in the special-special case in which the number of sizes is some constant ''S'', and each size is at least ''eB'' (for some constant 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 <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n''.<ref>{{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>

*

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" />

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<ref>{{cite journal|last1=Fernandez de la Vega|first1=W.|last2=Lueker|first2=G. S.|date=1981|title=Bin packing can be solved within 1 + ε in linear time|journal=Combinatorica|language=en|volume=1|issue=4|pages=349–355|doi=10.1007/BF02579456|issn=1439-6912|s2cid=10519631}}</ref> 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 <math>(1/e^2)\cdot n^{(1/e^2)^{1/e}}</math>, 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.

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.

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.

=== FractionalThe binfractional packingLP ===

The '''fractional configuration LP'' of bin-packing''' It is the [[linear programming relaxation]] of the above ILP. It replaces the last constraint <math>x_c\in\{0,\ldots,n\}</math> with the constraint <math>x_c \geq 0</math>. In other words, each configuration can be used a fractional number of times. The relaxation was first presented by Gilmore and Gomory,<ref name="Gilmore61" /> and it is often called the '''Gilmore-Gomory linear program'''.<ref name=":22">{{Cite book|last=Rothvoß|first=T.|title=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |chapter=Approximating Bin Packing within O(log OPT · Log Log OPT) Bins |date=2013-10-01|volume=|pages=20–29|arxiv=1301.4010|doi=10.1109/FOCS.2013.11|isbn=978-0-7695-5135-7|s2cid=15905063}}</ref>

* ''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.

* ''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.

In short, the fractional LP can be written as follows:

<blockquote>

minimize <math>~\mathbf{1}\cdot \mathbf{x}~</math> s.t. <math>~\mathbf{A} \mathbf{x}\geq \mathbf{n}~</math> and <math>

~\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'').

=== ImprovementsSolving 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">{{cite book|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|title=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) |chapter=An efficient approximation scheme for the one-dimensional bin-packing problem |date=November 1982 |chapter-url=https://ieeexplore.ieee.org/document/4568405/references#references |pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908|chapter-url-access=subscription}}</ref> present an algorithm that overcomes this problem.

This technique was later improved by several authors:

First, they construct the [[dual linear program]] of 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 with run-time polynomial in <math>n</math> and <math>1/\varepsilon</math>. Their algorithm finds a solution with size at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(OPT))</math>.

<blockquote>

maximize<math>~\mathbf{n}\cdot \mathbf{y}~</math>s.t.<math>~A^T \mathbf{y} \leq \mathbf{1}~</math> and <math>~\mathbf{y}\geq 0</math>.

</blockquote>

It has ''S'' variables ''y''₁,...,''y_S'', and ''C'' constraints: for each configuration ''c'', there is a constraint <math>A^c\cdot y\leq 1</math>, where <math>A^c</math> is the column of '''''A''''' representing the configuration ''c''. 3It 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.

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.

* Rothvoss<ref name=":22">{{Cite journal|last=Rothvoß|first=T.|date=2013-10-01|title=Approximating Bin Packing within O(log OPT * Log Log OPT) Bins|url=https://ieeexplore.ieee.org/document/6686137|journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science|volume=|pages=20–29|arxiv=1301.4010|doi=10.1109/FOCS.2013.11|isbn=978-0-7695-5135-7|via=|s2cid=15905063}}</ref> presented an algorithm that generates a solution with size at most <math>\mathrm{OPT} + O(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))</math>.

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

* 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 this algorithm to generate a solution with size at most <math>\mathrm{OPT} + O(\log(\mathrm{OPT}))</math>. The algorithm is randomized, and its running-time is polynomial in the total number of items.

All in all, 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:

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

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">{{cite book|last1=Hoberg|first1=Rebecca |doi=10.1137/1.9781611974782.172|isbn=978-1-61197-478-2|last2=Rothvoss|first2=Thomas|title=Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms |chapter=A Logarithmic Additive Integrality Gap for Bin Packing |publisher=Society for Industrial and Applied Mathematics |date=2017 |pages=2616–2625 |s2cid=1647463|doi-access=free}}</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.

== In bin covering ==

In the [[bin packing|bin covering problem]], there are ''n'' items with different sizes. The goal is to pack the items into a ''maximum'' number of bins, where each bin should contain ''at least'' ''B''. A natural configuration LP for this problem could be:<blockquote><math>\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\leq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0</math></blockquote>where '''''A''''' represents all configurations of items with sum ''at least'' ''B'' (one can take only the inclusion-minimal configurations). 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<ref name=":24">{{Cite book|last1=Csirik|first1=Janos|last2=Johnson|first2=David S.|last3=Kenyon|first3=Claire|chapter=Better approximation algorithms for bin covering |date=2001-01-09 |chapter-url=https://dl.acm.org/doi/abs/10.5555/365411.365533 |title=SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms |publisher=Society for Industrial and Applied Mathematics |pages=557–566|isbn=978-0-89871-490-6}}</ref> present an alternative LP. First, they define a set of items that are called ''small''. Let ''T'' be the total size of all small items. Then, they construct a matrix '''A''' representing all configurations with sum < 2. Then, they consider the above LP with one additional constraint:<math display="block">\text{maximize}~~\mathbf{1}\cdot \mathbf{x}~~\text{s.t.}</math><math display="block">A \mathbf{x}\leq \mathbf{n}</math><math display="block">\sum_{c\in C: sum(c)<B} (B-sum(c))\cdot x_c \leq T</math><math display="block">\mathbf{x}\geq 0</math>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<ref name=":24" /> present a different method to solve it approximately in time exponential in 1/epsilon. Jansen and Solis-Oba'''<ref name=":32">{{Cite book|last1=Jansen|first1=Klaus|last2=Solis-Oba|first2=Roberto|title=Algorithms and Computation |chapter=An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering |series=Lecture Notes in Computer Science |date=2002-11-21 |volume=2518 |chapter-url=https://dl.acm.org/doi/abs/10.5555/646345.689912 |publisher=Springer-Verlag |pages=175–186|doi=10.1007/3-540-36136-7_16|isbn=978-3-540-00142-3}}</ref>''' present an improved method to solve it approximately in time exponential in 1/epsilon.

== In machine scheduling ==

ConsiderIn 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 <math>x_{i,c}</math> which equals 1 iff the actual configuration used in machine ''i'' is ''c'', and 0 otherwise. Then, the LP constraints are:

Line 54 ⟶ 78:

=== Properties ===

The [[integrality gap]] of the configuration-LP for unrelated-machines scheduling is 2.<ref name=":0" />

== See also ==

* [[High-multiplicity bin packing]]

== References ==

Line 61 ⟶ 89:

[[Category:Number partitioning]]

[[Category:Job scheduling]]

[[Category:Combinatorial optimization]]

[[Category:Linear programming]]