Editing Bin packing problem (section)

=== Exact algorithms ===
Martello and Toth<ref>{{harvnb|Martello|Toth|1990|pp=237–240}}.</ref> developed an exact algorithm for the 1-dimensional bin-packing problem, called MTP. A faster alternative is the Bin Completion algorithm proposed by [[Richard E. Korf]] in 2002<ref>{{cite conference|last=Korf|first=Richard E.|author1-link=Richard E. Korf|year=2002|title=A new algorithm for optimal bin packing.|url=http://www.aaai.org/Papers/AAAI/2002/AAAI02-110.pdf|conference=AAAI-02}}</ref> and later improved.<ref name="Korf2003Korf2">[[Richard E. Korf]] (2003), ''[https://web.archive.org/web/20190823231238/https://pdfs.semanticscholar.org/616d/77a41020941a89e782e877bf4cf7bb5ec9a4.pdf An improved algorithm for optimal bin packing]''. Proceedings of the International Joint Conference on Artificial Intelligence, (pp. 1252–1258)</ref>

A further improvement was presented by Schreiber and Korf in 2013.<ref>{{citation|last1=Schreiber|first1=Ethan L.|title=Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence|pages=651–658|year=2013|series=IJCAI '13|chapter=Improved Bin Completion for Optimal Bin Packing and Number Partitioning|chapter-url=https://www.ijcai.org/Proceedings/13/Papers/103.pdf|location=Beijing, China|publisher=AAAI Press|isbn=978-1-57735-633-2|last2=Korf|first2=Richard E.|author2-link=Richard E. Korf}}</ref> The new Improved Bin Completion algorithm is shown to be up to five orders of magnitude faster than Bin Completion on non-trivial problems with 100 items, and outperforms the BCP (branch-and-cut-and-price) algorithm by Belov and Scheithauer on problems that have fewer than 20 bins as the optimal solution. Which algorithm performs best depends on problem properties like the number of items, the optimal number of bins, unused space in the optimal solution and value precision.