Editing Bin packing problem (section)

==Formal statement==
In ''[[Computers and Intractability]]''<ref name="GareyJohnson2">{{cite book|last1=Garey|first1=M.&nbsp;R.|title=<!-- [[ -->Computers and Intractability: A Guide to the Theory of NP-Completeness<!-- ]] -->|last2=Johnson|first2=D.&nbsp;S.|publisher=W.&nbsp;H.&nbsp;Freeman and Co.|year=1979|isbn=0-7167-1045-5|editor=Victor Klee|editor-link=Victor Klee|series=A Series of Books in the Mathematical Sciences|location=San Francisco, Calif.|pages=[https://archive.org/details/computersintract0000gare/page/ x+338]|mr=519066|author-link1=Michael R. Garey|author-link2=David S. Johnson}}</ref>{{Rp|226}} Garey and Johnson list the bin packing problem under the reference [SR1]. They define its decision variant as follows.

Instance: Finite set <math>I</math> of items, a size <math>s(i) \in \mathbb{Z}^+</math> for each <math>i \in I</math>, a positive integer bin capacity <math>B</math>, and a positive integer <math>K</math>.

Question: Is there a partition of <math>I</math> into [[disjoint sets]] <math>I_1,\dots, I_K</math> such that the sum of the sizes of the items in each <math>I_j</math> is <math>B</math> or less?

Note that in the literature often an alternate, but not equivalent, notation is used, where <math>B = 1</math> and <math>s(i) \in \mathbb{Q} \cap (0,1]</math> for each <math>i \in I</math>. Furthermore, research is mostly interested in the optimization variant, which asks for the smallest possible value of <math>K</math>. A solution is ''optimal'' if it has minimal <math>K</math>. The <math>K</math>-value for an optimal solution for a set of items <math>I</math> is denoted by <math>\mathrm{OPT}(I)</math> or just <math>\mathrm{OPT}</math> if the set of items is clear from the context.

A possible [[Integer programming|integer linear programming]] formulation of the problem is:
{|
| colspan="2" |minimize <math> K = \sum_{j=1}^n y_j</math>
|
|-
|subject to
|<math>K \geq 1,</math>
|-
|
|<math>\sum_{i \in I} s(i) x_{ij} \leq B y_j,</math>
|<math>\forall j \in \{1,\ldots,n\}</math>
|-
|
|<math>\sum_{j=1}^n x_{ij} = 1,</math>
|<math>\forall i \in I</math>
|-
|
|<math> y_j \in \{0,1\},</math>
|<math>\forall j \in \{1,\ldots,n\}</math>
|-
|
|<math> x_{ij} \in \{0,1\},</math>
|<math>\forall i \in I \, \forall j \in \{1,\ldots,n\}</math>
|}
where <math> y_j = 1</math> if bin <math>j</math> is used and <math> x_{ij} = 1</math> if item <math>i</math> is put into bin <math>j</math>.<ref name="Martello19902">{{harvnb|Martello|Toth|1990|p=221}}</ref>