Consider an instance of the Bin-Packing Problem where there are mj items of size wj ∈ (0, 1] for j  1, 2, . . . , n. Define a bin configuration to be a vector c  (c1, c2, . . . , c  n) with the property that ci ≥ 0 for i  1, 2, . . . , n and n j1 cjwj ≤ 1. Enumerate all possible bin configurations. Let there be M such configurations. DefineCjk to be the number of items of sizewj in bin configuration k, for k  1, 2, . . . , M and j  1, 2, . . . , n.

Formulate an integer program to solve this Bin-Packing Problem using the following variables: xk is the number of times configuration k is used, for k 

1, 2, . . . , M.