Content deleted Content added
m →The fractional LP: fix another blockquote causing unwanted line breaks in inline math |
m →Solving the fractional LP: fix another blockquote causing linebreak in inline math |
||
Line 43:
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> 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''<sub>1</sub>,...,''y<sub>S</sub>'', 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<sub>s</sub>''. 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>
▲
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.
| |||