Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 4:
== In bin packing ==
===
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 of size ''B''. A ''feasible configuration'' is a set of sizes with a sum of at most ''B''.
* ''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. For each size ''s'' and configuration ''c'', denote:
Line 15 ⟶ 17:
Then, the configuration LP of bin-packing is: <blockquote><math>\text{minimize}~~~\sum_{c\in C}x_c~~~\text{subject to}</math>
<math>\sum_{c\in C}a_{s,c}x_c \geq n_s</math> for every size ''s'' (- all ''n<sub>s</sub>'' items of size ''s'' are packed).
<math>x_c\in\{0,\ldots,n\}</math> for all ''c'' in ''C'' (- there are at most ''n'' configurations of each type). </blockquote>
=== Solution ===
Line 28 ⟶ 30:
=== Fractional bin packing ===
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'': 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.
=== Improvements ===
| |||