Abstract
In this article, we address the classical One-Dimensional Bin Packing Problem (1D-BPP), an \(\mathcal {NP}\)-hard combinatorial optimization problem. We propose a new formulation of integer linear programming for the problem, which reduces the search space compared to those described in the literature, as well as two families of cutting planes. Computational experiments are conducted on the data-set found in BPPLib and the results show that it is possible to solve more instances and to decrease the computation time by using our new formulation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arbib, C., Marinelli, F.: Maximum lateness minimization in one-dimensional bin packing. Omega 68, 76–84 (2017)
Cambazard, H., O’Sullivan, B.: Propagating the bin packing constraint using linear programming. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 129–136. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15396-9_13
Delorme, M., Iori, M., Martello, S.: Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1), 1–20 (2016)
Delorme, M., Iori, M., Martello, S.: BPPLIB: a library for bin packing and cutting stock problems. Optim. Lett. 12(2), 235–250 (2018)
Dyckhoff, H.: A new linear programming approach to the cutting stock problem. Oper. Res. 29(6), 1092–1104 (1981)
Falkenauer, E.: A hybrid grouping genetic algorithm for bin packing. J. Heuristics 2(1), 5–30 (1996)
Lysgaard, J., Letchford, A.N., Eglese, R.W.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. 100(2), 423–445 (2004)
Martello, S., Toth, P.: Knapsack problems: algorithms and computer implementations (1990)
Martello, S., Toth, P.: Lower bounds and reduction procedures for the bin packing problem. Discrete Appl. Math. 28(1), 59–70 (1990)
Ryan, D., Foster, E.: An integer programming approach to scheduling. Computer scheduling of public transport urban passenger vehicle and crew scheduling, pp. 269–280 (1981)
Scholl, A., Klein, R., Jürgens, C.: Bison: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comput. Oper. Res. 24(7), 627–645 (1997)
Schwerin, P., Wäscher, G.: The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP. Int. Trans. Oper. Res. 4(5–6), 377–389 (1997)
Wäscher, G., Gau, T.: Heuristics for the integer one-dimensional cutting stock problem: a computational study. Oper.-Res.-Spectr. 18(3), 131–144 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Hadj Salem, K., Kieffer, Y. (2020). New Symmetry-less ILP Formulation for the Classical One Dimensional Bin-Packing Problem. In: Kim, D., Uma, R., Cai, Z., Lee, D. (eds) Computing and Combinatorics. COCOON 2020. Lecture Notes in Computer Science(), vol 12273. Springer, Cham. https://doi.org/10.1007/978-3-030-58150-3_34
Download citation
DOI: https://doi.org/10.1007/978-3-030-58150-3_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58149-7
Online ISBN: 978-3-030-58150-3
eBook Packages: Computer ScienceComputer Science (R0)