ISSN 2071-8594

Russian academy of sciences


Gennady Osipov

E.M. Furems. Inverse bin packing problem with multiple qualitative criteria – formulation and survey of applicable approaches


The new formulation of inverse bin packing problem is proposed. Its peculiarity consists in the requirement to take into account DM’s preferences on the set of objects, estimated upon multiple qualitative criteria. The aspects of this problem attributable to the Theory of Multi-Criteria Decision Making are discussed. The survey of existing methods for both classical and inverse bin packing (including multiple knapsack problem) is provided.


inverse bin packing problem, preference relation, multicriteria sorting, approximate algorithms, branch-and-bound, genetic algorithms.

PP. 31-43.


1. Martello S., Toth P. (1980). Solution of the zero-one multiple knapsack problem. European Journal of Operational Research, 4(4), 276-283.
2. Johnson D. S., Demers A., Ullman J. D., Garey M. R., Graham R. L. (1974). Worst case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4), 299-325.
3. Coffman E.G., Jr., Leung J.Y.-T., Ting D. (1978). Bin Packing: Maximizing the Number of Pieces Packed, Acta Infomat., vol. 9, 263-271.
4. Coffman Jr, E. G., Leung J. Y. (1979). Combinatorial analysis of an efficient algorithm for processor and storage allocation. SIAM Journal on Computing, 8(2), 202-217.
5. Graham R. L., Lawler E. L., Lenstra J. K., KanA. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics, 5, 287-326.
6. Garey M. R., Graham R. L., Johnson D. S., Yao A. C. C. (1976). Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A, 21(3), 257-298.
7. Garey M. R., Graham R. L., Johnson D. S. (1978). Performance guarantees for scheduling algorithms. Operations research, 26(1), 3-21.
8. Dell'Amico M., Diaz J. C. D., Iori M. (2012). The bin packing problem with precedence constraints. Operations Research, 60(6), 1491-1504.
9. Furems Ye.M. Modeli upakovki v mnogokriterialnykh zadachakh prinyatiya resheniy pri ogranichennykh resursakh. Preprint VNIISI, M., 1986. S. 45.
10. Karp R.M. (1972). Reducibility among combinatorial problems, in Complexity of Computer Computations (R.E. Miller and J.M. Thatcher, eds.), 85–103, Plenum Press.
11. Geri M., Dzhonson D. Vychislitelnye mashiny i trudnoreshaemye zadachi. M.: Mir. 1982.
12. Dyckhoff H., Finke U. (1992). Cutting and Packing in Production and Distribution: a Typology and Bibliography, Springer, Berlin.
13. Wascher G., Hausner H., Schumann H. (2007). An improved typology of cutting and packing problems. EJOR, 183 (3), 1109–1130.
14. Chung F. R., Garey M. R., Johnson D. S. (1982). On packing two-dimensional bins. SIAM Journal on Algebraic Discrete Methods, 3(1), 66-76.
15. Berkey J. O., Wang P. Y. (1987). Two-dimensional finite bin-packing algorithms. Journal of the operational research society, 423-429.
16. Gimadi E.Kh., Zalyubovskiy V.V., Sharygin P.I. Zadacha upakovki v polosu: asimptoticheski tochnyy podkhod//Izvestiya vysshikh uchebnykh zavedeniy. Matematika, № 12, 1997.s.34-44.
17. Lodi A., Martello S., Vigo D. (1999). Approximation algorithms for the oriented two-dimensional bin packing problem. EJOR, 112(1), 158-166.
18. Dell'Amico M., Martello S., Vigo D. (2002). A lower bound for the non-oriented two-dimensional bin packing problem. Discrete Applied Mathematics 118(1-2), 13-24.
19. Lodi A., Martello S., Vigo D. (2002). Recent advances on two-dimensional bin packing problems. Discrete Applied Mathematics 123(1-3), 379-396.
20. Lodi A., Martello S., Vigo D (2002). Heuristic algorithms for the three dimensional bin packing problem. EJOR, 141(2), 410-420.
21. Lodi A., Martello S., Vigo D (2004). TSpack: A Unified Tabu Search Code for Multi-Dimensional Bin Packing Problems. Annals OR 131(1-4), 203-213.
22. Lodi A., Martello S., Vigo D (2004). Models and Bounds for Two-Dimensional Level Packing Problems. J. Comb. Optim. 8(3), 363-379.
23. den Boef E., Korst J., Martello S., Pisinger D., Vigo D. (2005). Erratum to ‘The Three-Dimensional Bin Packing Problem’: Robot-Packable and Orthogonal Variants of Packing Problems. Operations Research 53(4), 735-736.
24. Bansal N., Khan A. (2014, January). Improved approximation algorithm for two-dimensional bin packing. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms (pp. 13-25). SIAM.
25. Valeeva A.F. Primenenie metaevristiki muravinoy kolonii k zadacham dvukhmernoy upakovki //Informatsionnye tekhnologii, № 10, 2005. S. 36–43.
26. Mukhacheva E.A., Valeeva A.F., Filippova A.S., Polyakovskiy S.Yu. Zadacha dvumernoy konteynernoy upakovki: nizhnie granitsy i chislennyy eksperiment s algoritmami lokalnogo poiska optimuma //Informatsionnye tekhnologii, № 4, 2006, s.45–52.
27. Lopez-Camacho, Eunice, et al. (2013). An effective heuristic for the two-dimensional irregular bin packing problem. Annals of Operations Research 206.1: 241-264.
28. Lins L., Lins S., Morabito R. (2002). An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an n-container. EJOR 141, 421–439.
29. Coffman E.G., Jr., Garey M. R., Johnson D. S. (1983). Dynamic bin packing, SIAM J. Comput., 12, 227-258.
30. Rhee W.T., Talagrand M. (1993). On-line bin packing with items of random size. Math. Oper. Res. 18, 438–445.
31. Boyar J., Fayholdt L. M., Larsen K. S., Nielsen M. N. (2001). The competitive ratio for on-line dual bin packing with restricted input sequences, Nordic J. Comput., 8, 463-472.
32. Boyar J., et al. (2014). Online bin packing with advice. Algorithmica, 1-21.
33. Delorme M., Iori M., Martello S. (2015). Bin packing and cutting stock problems: Mathematical models and exact algorithms. In AIRO 2014 Conference (p. 77).
34. Simon H. (1960). The New Science of Management Decision. Harper and Row, New York.
35. Saaty T, Shihb H-S (2009), Structures in decision making: On the subjective geometry of hierarchies and networks. EJOR, vol. 199, 3:867-872.
36. von Winterfeldt D. (1980). Structuring Decision Problems for Decision Analysis. ActaPsychologica, vol. 45:71-93.
37. Wallenius J., Dyer J., Fishburn P., Steuer R., Zionts S., Deb K. (2008). Multiple Criteria Decision Making, Multiattribute Utility Analysis: Recent Accomplishments and What Lies Ahead. Management Science, Vol. 54, 7:1336-1349.
38. Furems Ye.M., Strukturizatsiya zadach klassifikatsii, osnovannykh na znaniyakh// Informatsionnye tekhnologii i vychislitelnye sistemy, № 3, 2007.s. 7-17.
39. Furems Eugenia M. (2011). Domain Structuring For Knowledge-Based Multiattribute Classification (A Verbal Decision Analysis Approach), TOP, Springer Berlin /
Heidelberg, 19, pp. 402–420.
40. Furems Ye.M. Mnogokriterialnaya poryadkovaya klassifikatsiya na osnove metoda STEPCLASS //Iskusstvennyy intellekt i prinyatie resheniy, № 4, 2012, s. 95-100.
41. Larichev O.I., Moshkovich Ye.M. Kachestvennye metody prinyatiya resheniy. M.: Fizmatlit. 1996.
42. Ashikhmin I., Furems E., Petrovsky A., Sternin M. (2008). Intelligent DSS Under Verbal Decision Analysis. Encyclopedia of Decision Making and Decision Support
Technologies (2 Volumes), Information Science Reference, Hershey • New York, Edited By: Frederic Adam, University College Cork, Ireland; Patrick Humphreys, London School of Economics, UK, Volume 2, pp. 514-527
43. Ashikhmin I., Furems E. (2005). UniComBOS: Intelligent Decision Support System for multi-criteria comparison and choice. Journal of Multi-Criteria Decision Analysis, 13 (2-3), pp.147-157.
44. Gudman S., Khidentniemi S. Vvedenie v razrabotku i analiz vychislitelnykh algoritmov. M.: Mir. 19 81. S. 386.
45. Marshal L., Fisher M.S. (1980). Worst-case Analysis of Heuristics Algorithms, Manag. Sci., vol 26, No 1, 1-8.
46. Coffman Jr., Garey M. R., Johnson D. S. (1984). Approximation algorithms for bin-packing—an updated survey. In Algorithm design for computer system design
(pp. 49-106). Springer Vienna.
47. Johnson D.S. (1974). Fast algorithms for bin packing. Journal of Computer and System Sciences, vol. 8.3, 272-314.
48. Ullman J. D. (1971). The performance of a memory allocation algorithm. Technical Report 100, Princeton Univ., Princeton, NJ.
49. Garey M. R., Graham R. L., Ullman J. D. (1973), Worstcase analysis of memory allocation algorithms. In Proc. 4th Symp. Theory of Computing (STOC), 143-150, ACM.
50. Dosa G., Sigall J. (2014). Optimal analysis of Best Fit bin packing, Automata, Languages, and Programming. Springer Berlin Heidelberg, 429-441.
51. Coffman Jr., Garey M.R., Johnson D.S. (1978). An Application of Bin Packing to Multiprocessor Scheduling, SIAM J. Comput., vol. 7, No. 1, 1-17.
52. Chi-Chin Yao (1980). New Algorithms for Bin Packing/Journal of the Association for Computer Machinery, vol 27, No. 2, 207-227.
53. Frederickson G.N. (1980). Probabilistic analysis for simple one- and two-dimensional bin packing algorithms, Information Processing Letters, V. 11, №4-5, 156-161.
54. de Carvalho J.M., Valerio (2002). LP models for bin packing and cutting stock problems, EJOR 141/2, 253-273.
55. Eilon S., Christofides N. (1990). The loading problem, Management Science, V. 17, 259267.
56. Martello, S., and Toth, P. (1990), Bin-packing problem. In Knapsack Problems: Algorithms and Computer Implementations. Wiley, chapter 8, 221-245.
57. Martello S., Toth P. (1990). Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Mathematics 28:59-70.
58. Korf R. E. (2002, July). A new algorithm for optimal bin packing. In AAAI/IAAI (pp. 731-736).
59. Scholl, A., Klein, R., Jurgens, C. (1997), BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers and Operations Research, 24, 627–645.
60. de Carvalho J.M., Valerio (1999). Exact solution of binpacking problems using column generation and branchand-bound, Annals of Operation Research, 86, 629–659.
61. Fukunaga A.S., Korf R. E. (2007). Bin Completion Algorithms for Multicontainer Packing, Knapsack, and Covering Problems, Journal of Artificial Intelligence Research, 28, 393-429
62. Schreiber E. L., Korf R. E. (2013, August). Improved Bin Completion for Optimal Bin Packing and Number Partitioning. In IJCAI.
63. Martello S., Toth, P. (1981). A bound and bound algorithm for the zero-one multiple knapsack problem. Discrete Applied Mathematics, 3, 275–288.
64. Pisinger D. (1999). An exact algorithm for large multiple knapsack problems. EJOR, 114, 528–541.
65. Martello S., Toth P. (1977). An upper bound for the zeroone knapsack problem and a branch and bound algorithm. EJOR, 1, 169–175.
66. Smith D. (1985). Bin-packing with adaptive search, in: Grefenstette (ed.), Proceedings of an International Conference on Genetic Algorithms and their Applications, Lawrence Erlbaum, 202-206.
67. Prosser P. (1988). A hybrid genetic algorithm for pallet loading, in: B. Radig (ed.), ECAI 88 Proceedings 8th European Conference on Artificial Intelligence, Pitman, London, 159-164.
68. Falkenauer E., Delchambre A. (1992). A genetic algorithm for bin-packing and line balancing, Proceedings of the 1992 IEEE International Conference on Robotics and Automation, Nice, Fr, vol. 2, 1186-1192.
69. Falkenauer E.. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2(1):5–30, 1996.
70. Reeves C. (1996). Hybrid genetic algorithms for binpacking and related problems, Annals of Operations Research, 63.3, 371-396.
71. Ross P., Mar?n-Blazquez J. G., Schulenburg S., Hart E. (2003). Learning a Procedure That Can Solve Hard Bin Packing Problems: A New GA-Based Approach to Hyperheuristics. E. Cant.u-Paz et al. (Eds.): GECCO 2003, LNCS 2724, Springer-Verlag Berlin Heidelberg, 1295–1306.
72. Djang P.A., Finch P.R. (1998). Solving one dimensional bin packing problems, Journal of Heuristics, 123-144.
73. Sim K., Hart E., Paechter B. (2012). A Hyper-Heuristic Classifier for One Dimensional Bin Packing Problems: Improving Classification Accuracy by Attribute Evolution. Coello Coello et al. (Eds.): PPSN, Part II, LNCS 7492, 348–357, 2012. Springer-Verlag Berlin Heidelberg.
74. Quiroz-Castellanos, Marcela, et al.(2015). A grouping genetic algorithm with controlled gene transmission for the bin packing problem. Computers & Operations Research 55: 52-64.
75. Khuri S., Back T., Heitkotter J. (1994, April). The zero/one multiple knapsack problem and genetic algorithms. In Proceedings of the 1994 ACM symposium on Applied computing (pp. 188-193). ACM.
76. Michalewicz Z., Arabas J. (1994). Genetic algorithms for the 0/1 knapsack problem. In Methodologies for Intelligent Systems (pp. 134-143). Springer Berlin Heidelberg.77. Cotta C., Troya J. M. (1998). A hybrid genetic algorithm for the 0–1 multiple knapsack problem. In Artificial neural nets and genetic algorithms (pp. 250-254). Springer Vienna.
78. Andre L., Stubs Parpinelli R. (2015). The Multiple Knapsack Problem Approached by a Binary Differential Evolution Algorithm with Adaptive Parameters. Polibits, (51), 47-54.
79. Krause J., Parpinelli R. S., Lopes H. S. (2012). Proposta de um algoritmo inspirado em evolucao diferencial aplicado ao problema multidimensional da mochila. Anais do IX Encontro Nacional de Inteligencia Artificial–ENIA. Curitiba, PR: SBC.