Configuration linear program: Difference between revisions

Revision as of 05:31, 30 December 2023

Latest revision as of 13:04, 25 August 2025

(6 intermediate revisions by 3 users not shown)

Line 1:

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

The '''configuration linear program''' ('''configuration-LP''') is a [[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. | journal=Operations Research | date=1961 | volume=9 | issue=6 | pages=849–859 | doi=10.1287/opre.9.6.849 | s2cid=8079477 }}</ref> Later, it has been 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/document/4568405|journal=23rd1982-11-01 Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908}}</ref><ref>{{Cite book|last1=Bansal|first1=Nikhil|last2=Caprara|first2=Alberto|last3=Sviridenko|first3=Maxim|title=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|chapter-url=https://ieeexplore.ieee.org/document/4031404|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 arXiv|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 ''configuration'' - each possible [[multiset]] of items that can fit in a single bin (these configurations are also known as ''patterns'') . 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.

== In bin packing ==

Line 15:

* ''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 all ''s'' in ''S'' (- all ''n_s'' items of size ''s'' are packed).

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

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

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

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

=== 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 <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|chapter-url=https://ieeexplore.ieee.org/document/6686137|volume=|pages=20–29|arxiv=1301.4010|doi=10.1109/FOCS.2013.11|isbn=978-0-7695-5135-7|via=|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.

In short, the fractional LP can be written as follows:
<blockquote>
minimize <math>\text{minimize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{</math> s.t.}~~ <math>~\mathbf{A} \mathbf{x}\geq \mathbf{n}~~~\text{</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'').

=== 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">{{cite journalbook|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|datetitle=November23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) |titlechapter=An efficient approximation scheme for the one-dimensional bin-packing problem |date=November 1982 |chapter-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|chapter-url-access=subscription}}</ref> present an algorithm that overcomes this problem.

First, they construct the [[dual linear program]] of the fractional LP:

First, they construct the [[dual linear program]] of the fractional LP:<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: 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.

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

First, they construct the [[dual linear program]] of the fractional LP:<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: 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.