Configuration linear program: Difference between revisions

Revision as of 20:50, 25 November 2021

Revision as of 20:52, 25 November 2021

Line 32:

The ''fractional configuration LP'' of bin-packing 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.

* ''Example'':<ref name=":12" /> 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.

Let FOPT be the optimal solution of the fractional LP, and OPT the optimal solution of the integral LP. Let SUM be the sum of all sizes. Karmarkar and Karp<ref name=":12" /> prove the following inequalities:<blockquote><math>SUM/B \leq FOPT \leq OPT \leq FOPT+(S+1)/2</math></blockquote>

=== Improvements ===