Content deleted Content added
m →The integral LP: fix math formulas not rendered inline because of missing newlines around blockquote |
m →The fractional LP: fix another blockquote causing unwanted line breaks in inline math |
||
Line 33:
* ''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> ~\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''<sub>1</sub>,...,''n<sub>S</sub>''). === Solving the fractional LP ===
| |||