A Numerically Exact Algorithm for the Bin-Packing Problem

References

• Applegate DL, Cook W, Dash S, Espinoza DG (2007) Exact solutions to linear programming problems. Oper. Res. Lett. 35(6):693–699.Crossref, Google Scholar
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Program. 115:351–385.Crossref, Google Scholar
• Belov G, Scheithauer G (2006) A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European J. Oper. Res. 171(1):85–106.Crossref, Google Scholar
• Caprara A, Dell’Amico M, Díaz-Díaz JC, Iori M, Rizzi R (2015) Friendly bin packing instances without integer round-up property. Math. Programming 150(1):5–17.Crossref, Google Scholar
• Coniglio S, D’Andreagiovanni F, Furini F (2019) A lexicographic pricer for the fractional bin packing problem. Oper. Res. Lett. 47(6):622–628.Crossref, Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12:129–146.Crossref, Google Scholar
• Cook W, Dash S, Fukasawa R, Goycoolea M (2009) Numerically safe Gomory mixed-integer cuts. INFORMS J. Comput. 21(4):641–649.Link, Google Scholar
• Cook W, Koch T, Steffy D, Wolter K (2011) An Exact Rational Mixed-Integer Programming Solver, Lecture Notes in Computer Science, vol. 6655 (Springer, New York).Google Scholar
• Cook W, Koch T, Steffy DE, Wolter K (2013) A hybrid branch-and-bound approach for exact rational mixed-integer programming. Math. Programming Comput. 5(3):305–344.Crossref, Google Scholar
• Cornuéjols G, Margot F, Nannicini G (2013) On the safety of Gomory cut generators. Math. Programming Comput. 5(4):345–395.Crossref, Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Amer. 2(4):393–410.Link, Google Scholar
• de Lima VL, Iori M, Miyazawa FK (2021) New exact techniques applied to a class of network flow formulations. Singh M, Williamson DP, eds. Integer Programming and Combinatorial Optimization (Springer International Publishing, Cham, Switzerland), 178–192.Crossref, Google Scholar
• de Lima VL, Iori M, Miyazawa FK (2022) Exact solution of network flow models with strong relaxations. Math. Programming 197(2):813–846.Google Scholar
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. European J. Oper. Res. 255(1):1–20.Crossref, Google Scholar
• Dósa G, Sgall J (2014) Optimal analysis of best fit bin packing. International Colloquium on Automata, Languages, and Programming (Springer, New York), 429–441.Google Scholar
• Eifler L, Gleixner A (2022) A computational status update for exact rational mixed integer programming. Math. Programming 197(2):793–812.Crossref, Google Scholar
• Eisenbrand F, Pálvölgyi D, Rothvoß T (2013) Bin packing via discrepancy of permutations. ACM Trans. Algorithms 9(3):1–15.Crossref, Google Scholar
• Farley AA (1990) A note on bounding a class of linear programming problems, including cutting stock problems. Oper. Res. 38(5):922–923.Link, Google Scholar
• Fukasawa R, Goycoolea M (2011) On the exact separation of mixed integer knapsack cuts. Math. Programming 128(1):19–41.Crossref, Google Scholar
• Fukasawa R, Poirrier L (2017) Numerically safe lower bounds for the capacitated vehicle routing problem. INFORMS J. Comput. 29(3):544–557.Link, Google Scholar
• Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Gleixner AM, Steffy DE, Wolter K (2012) Improving the accuracy of linear programming solvers with iterative refinement. Proc. 37th Internat. Sympos. Symbolic and Algebraic Computation (ACM, New York), 187–194.Google Scholar
• Gleixner AM, Steffy DE, Wolter K (2016) Iterative refinement for linear programming. INFORMS J. Comput. 28(3):449–464.Link, Google Scholar
• Gurobi Optimization LLC (2022) Gurobi Optimizer Reference Manual. https://www.gurobi.com.Google Scholar
• Held S, Cook WJ, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Karmarkar N, Karp RM (1982) An efficient approximation scheme for the one-dimensional bin-packing problem. 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), 312–320.Google Scholar
• Kartak VM, Ripatti AV, Scheithauer G, Kurz S (2015) Minimal proper non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl. Math. 187:120–129.Crossref, Google Scholar
• Lübbecke M, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, New York).Google Scholar
• Neumaier A, Shcherbina O (2004) Safe bounds in linear and mixed-integer linear programming. Math. Programming 99(2):283–296.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E (2021) Solving bin packing problems using VRPSolver models, SN Operations Research Forum 2, 20.Google Scholar
• Pessoa AA, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183(1):483–523.Crossref, Google Scholar
• Ryan D, Foster B (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam).Google Scholar
• Sadykov R, Vanderbeck F (2013) Bin packing with conflicts: A generic branch-and-price algorithm. INFORMS J. Comput. 25(2):244–255.Link, Google Scholar
• Scheithauer G, Terno J (1997) Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem. Oper. Res. Lett. 20(2):93–100.Crossref, Google Scholar
• Steffy DE, Wolter K (2012) Valid linear programming bounds for exact mixed-integer programming. INFORMS J. Comput. 25(2):271–284.Link, Google Scholar
• Vance PH, Barnhart C, Johnson EL, Nemhauser GL (1994) Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. Appl. 3(2):111–130.Crossref, Google Scholar
• Wei L, Luo Z, Baldacci R, Lim A (2020) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS J. Comput. 32(2):428–443.Link, Google Scholar
• Wunderling R (1996) Paralleler und Objektorientierter Simplex-Algorithmus, PhD thesis, Technische Universität Berlin, Berlin.Google Scholar