Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation

References

• Andersen ED (2001) Certificates of primal or dual infeasibility in linear programming. Comput. Optim. Appl. 20(2):171–183.Crossref, Google Scholar
• Bergman D (2019) An exact algorithm for the quadratic multiknapsack problem with an application to event seating. INFORMS J. Comput. 31(3):477–492.Link, Google Scholar
• Bergman D, Cire AA (2016) Decomposition based on decision diagrams. Quimper CG, ed. Proc. Integration of AI and OR Techniques in Constraint Programming (Springer, Cham, Switzerland) 45–54.Crossref, Google Scholar
• Bergman D, Lozano L (2021) Decision diagram decomposition for quadratically constrained binary optimization. INFORMS J. Comput. 33(1):401–418.Link, Google Scholar
• Bergman D, Cardonha C, Mehrani S (2019) Binary decision diagrams for bin packing with minimum color fragmentation. Rousseau LM, Kostas S, eds. Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (CPAIOR) (Springer, Cham, Switzerland), 57–66.Google Scholar
• Bertsekas DP (2017) Dynamic Programming and Optimal Control, vol. 1, 4th ed. (Athena Scientific, Belmont, MA).Google Scholar
• Bettinelli A, Cacchiani V, Malaguti E (2017) A branch-and-bound algorithm for the knapsack problem with conflict graph. INFORMS J. Comput. 29(3):457–473.Link, Google Scholar
• Brandão F, Pedroso JP (2016) Bin packing and related problems: General arc-flow formulation with graph compression. Comput. Oper. Res. 69:56–67.Crossref, Google Scholar
• Bryant RE (1986) Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35(8):677–691.Crossref, Google Scholar
• Bryant RE (1992) Symbolic Boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surveys 24(3):293–318.Crossref, Google Scholar
• Chebil K, Khemakhem M (2015) A dynamic programming algorithm for the knapsack problem with setup. Comput. Oper. Res. 64:40–50.Crossref, Google Scholar
• Côté JF, Dell’Amico M, Iori M (2014) Combinatorial benders’ cuts for the strip packing problem. Oper. Res. 62(3):643–661.Link, Google Scholar
• De Carvalho JMV (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res. 86:629–659.Crossref, Google Scholar
• Dell’Amico M, Díaz JCD, Iori M (2012) The bin packing problem with precedence constraints. Oper. Res. 60(6):1491–1504.Link, Google Scholar
• Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J. Comput. 32(1):101–119.Link, Google Scholar
• Doulabi SHH, Rousseau LM, Pesant G (2016) A constraint-programming-based branch-and-price-and-cut approach for operating room planning and scheduling. INFORMS J. Comput. 28(3):432–448.Link, Google Scholar
• Elhedhli S, Li L, Gzara M, Naoum-Sawaya J (2011) A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS J. Comput. 23(3):404–415.Link, Google Scholar
• Falkenauer E (1996) A hybrid grouping genetic algorithm for bin packing. J. Heuristics 2(1):5–30.Crossref, Google Scholar
• Furini F, Monaci M, Traversi E (2018) Exact approaches for the knapsack problem with setups. Comput. Oper. Res. 90:208–220.Crossref, Google Scholar
• Garey MR, Johnson DS (1978) Strong NP-completeness results: Motivation, examples, and implications. J. ACM 25(3):499–508.Crossref, Google Scholar
• Gendreau M, Laporte G, Semet F (2004) Heuristics and lower bounds for the bin packing problem with conflicts. Comput. Oper. Res. 31(3):347–358.Crossref, Google Scholar
• Gualandi S, Malucelli F (2012) Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24(1):81–100.Link, Google Scholar
• Gul S, Denton BT, Fowler JW, Huschka T (2011) Bi-criteria scheduling of surgical services for an outpatient procedure center. Production Oper. Management 20(3):406–417.Crossref, Google Scholar
• Gurobi Optimization L (2020) Gurobi optimizer reference manual. Accessed July 8, 2021, http://www.gurobi.com.Google Scholar
• Jung KS, Pinedo M, Sriskandarajah C, Tiwari V (2019) Scheduling elective surgeries with emergency patients at shared operating rooms. Production Oper. Management 28(6):1407–1430.Crossref, Google Scholar
• Kell B, Van Hoeve WJ (2013) An MDD approach to multidimensional bin packing. Gomes CP, Sellmann M, eds. Integration of (AI) and (OR) Techniques in Constraint Programming for Combinatorial Optimization Problems. Proc. 10th Internat. Conf. CPAIOR, May 18-22, Lecture Notes in Computer Science (Yorktown Heights, NY), 7874:128–143.Google Scholar
• Kondakov A, Kochetov Y (2018) A core heuristic and the branch-and-price method for a bin packing problem with a color constraint. OPTA (Springer), 309–320.Google Scholar
• Korf RE (2002) A new algorithm for optimal bin packing. 18th National Conf. Artificial Intelligence. American Assoc. Artificial Intelligence (AAAI, Edmonton, Alberta, Canada), 731–736.Google Scholar
• Korf RE (2003) An improved algorithm for optimal bin packing. Proc. 18th Internat. Joint Conf. on Artificial Intelligence (IJCAI), Acapulco, Mexico, vol. 3 (Morgan Kaufmann Publishers Inc., San Francisco, CA), 1252–1258.Google Scholar
• Lin KM, Ehrgott M, Raith A (2017) Integrating column generation in a method to compute a discrete representation of the non-dominated set of multi-objective linear programmes. 4OR 15(4):331–357.Crossref, Google Scholar
• Martello S, Toth P (1990) Lower bounds and reduction procedures for the bin packing problem. Discrete Appl. Math. 28(1):59–70.Crossref, Google Scholar
• Monaci M, Toth P (2006) A set-covering-based heuristic approach for bin-packing problems. INFORMS J. Comput. 18(1):71–85.Link, Google Scholar
• Muritiba AEF, Iori M, Malaguti E, Toth P (2010) Algorithms for the bin packing problem with conflicts. INFORMS J. Comput. 22(3):401–415.Link, Google Scholar
• Neame PJ (2000) Nonsmooth dual methods in integer programming. Unpublished PhD thesis, University of Melbourne, Department of Mathematics and Statistics, Australia.Google Scholar
• Olivier P, Lodi A, Pesant G (2018) A comparison of optimization methods for multi-objective constrained bin packing problems. Van Hoeve WJ, ed. CPAIOR (Springer), 462–476.Crossref, Google Scholar
• Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, et al. (2011) Scikit-learn: Machine learning in Python. J. Machine Learn. Res. 12:2825–2830.Google Scholar
• Peeters M, Degraeve Z (2004) The co-printing problem: A packing problem with a color constraint. Oper. Res. 52(4):623–638.Link, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Pferschy U, Scatamacchia R (2018) Improved dynamic programming and approximation results for the knapsack problem with setups. Internat. Trans. Oper. Res. 25(2):667–682.Crossref, 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
• Thorsteinsson ES (2001) Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming. Walsh T, ed. Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg, Germany), 16–30.Google Scholar
• Vanderbeck F (1999) Computational study of a column generation algorithm for bin packing and cutting stock problems. Math. Programming 86(3):565–594.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
• Zhang Z, Denton BT, Xie X (2020) Branch and price for chance-constrained bin packing. INFORMS J. Comput. 32(3):547–564.Link, Google Scholar