Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 21

Proceedings of the 2020 Federated Conference on Computer Science and Information Systems

An Experimental Study on Symmetry Breaking Constraints Impact for the One Dimensional Bin-Packing Problem

,

DOI: http://dx.doi.org/10.15439/2020F19

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 317–326 ()

Full text

Abstract. We consider the classical One-Dimensional Bin Packing Problem (1D-BPP), an NP-hard optimization problem, where, a set of weighted items has to be packed into one or more identical capacitated bins. We give an experimental study on using symmetry breaking constraints for strengthening the classical integer linear programming proposed to optimally solve this problem. Our computational experiments are conducted on the data-set found in BPPLib and the results have confirmed the theoretical results.

References

  1. A. Scholl, R. Klein and C. Jürgens, “Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem,” Computers & Operations Research, vol. 24(7), 1997, pp. 627–645.
  2. B. T. Denton, A. J. Miller, H. J. Balasubramanian and T. R. Huschka, “Optimal allocation of surgery blocks to operating rooms under uncertainty,” Operations research, vol. 58(4-part-1), 2010, pp. 802–816.
  3. D.M. Ryan and E.A. Foster, “An integer programming approach to scheduling,” scheduling of public transport urban passenger vehicle and crew scheduling, 1981, pp. 269–280.
  4. E. Falkenauer, “A hybrid grouping genetic algorithm for bin packing,” Journal of heuristics, vol. 2(1), 1996, pp. 5–30.
  5. F. Margot, “Symmetry in integer linear programming,” 50 Years of Integer Programming 1958-2008, Springer, 2010, pp. 647–686.
  6. H. Cambazard and B. O’Sullivan, “Propagating the bin packing constraint using linear programming,” International Conference on Principles and Practice of Constraint Programming, St. Andrews, Scotland, 2010, pp. 129–136.
  7. H. Dyckhoff, “A new linear programming approach to the cutting stock problem,” Operations Research, vol. 29(6), 1981, pp. 1092–1104.
  8. H.D. Sherali and J.C. Smith, “Improving discrete model representations via symmetry considerations,” Management Science, vol. 47(10), 2001, pp. 1396–1407.
  9. J. Lysgaard, A.N Letchford and R.W Eglese, “A new branch-and-cut algorithm for the capacitated vehicle routing problem,” Mathematical Programming, vol. 100(2), 2004, pp. 423–445.
  10. J. Ostrowski, M.F. Anjos and A. Vannelli, “Symmetry in scheduling problems,” ,Citeseer, 2010, pp. 59–70.
  11. J. V. De Carvalho, “LP models for bin packing and cutting stock problems,” European Journal of Operational Research, vol. 141(2), 2002, pp. 253-273.
  12. K. Hadj Salem and Y. Kieffer, “New Symmetry-less ILP Formulation for the Classical One Dimensional Bin-Packing Problem,” 26th International Computing and Combinatorics Conference, Atlanta, GA, USA, 2020, in press.
  13. L. Liberti, “Symmetry in mathematical programming,” Mixed Integer Nonlinear Programming, Springer, New York, NY, 2012, pp. 263–283.
  14. M. Delorme, M. Manuel and S. Martello, “Bin packing and cutting stock problems: Mathematical models and exact algorithms,” European Journal of Operational Research, vol. 255, 2016, pp. 1–20.
  15. M. Delorme, M. Manuel and S. Martello, “BPPLIB: a library for bin packing and cutting stock problems,” Optimization Letters, vol. 12(2), 2018, pp. 235–250.
  16. M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi and L. A. Wolsey, “50 Years of integer programming 1958-2008: From the early years to the state-of-the-art,” Springer Science & Business Media, 2009, pp. 123-136.
  17. P. Schwerin G. and Wäscher, “The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP,” Transactions in Operational Research, vol. 4(5-6), 1997, pp. 377–389.
  18. R. Jans, “Solving lot-sizing problems on parallel identical machines using symmetry-breaking constraints,” INFORMS Journal on Computing, vol. 21(1), 2009, pp. 123-136.
  19. S. Martello and P. Toth, “Knapsack problems: algorithms and computer implementations,” John Wiley & Sons, Inc., 1990, pp. 123-136.
  20. S. Martello and P. Toth, “Lower bounds and reduction procedures for the bin packing problem,” Discrete applied mathematics, vol. 28(1), 1990, pp. 59–70.
  21. G. Wäscher and T. Gau, “Heuristics for the integer one-dimensional cutting stock problem: A computational study,” Operations-Research-Spektrum, vol. 18(3), 1996, pp. 131–144.