Branch-and-Price for the Set-Union Bin Packing Problem

References

• Adjiashvili D, Bosio S, Zemmer K (2015) Minimizing the number of switch instances on a flexible machine in polynomial time. Oper. Res. Lett. 43(3):317–322.Crossref, Google Scholar
• Arulselvan A (2014) A note on the set union knapsack problem. Discrete Appl. Math. 169:214–218.Crossref, Google Scholar
• Baldacci R, Coniglio S, Cordeau JF, Furini F (2024) A numerically exact algorithm for the bin-packing problem. INFORMS J. Comput. 36(1):141–162.Link, Google Scholar
• Barnhart C, Johnson E, Nemhauser G, Savelsbergh M, Vance P (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Burger AP, Jacobs C, van Vuuren JH, Visagie SE (2015) Scheduling multi-colour print jobs with sequence-dependent setup times. J. Sched. 18:131–145.Crossref, Google Scholar
• Calmels D (2019) The job sequencing and tool switching problem: State-of-the-art literature review, classification, and trends. Internat. J. Production Res. 57(15–16):5005–5025.Crossref, Google Scholar
• Campêlo M, Campos VA, Corrêa RC (2008) On the asymmetric representatives formulation for the vertex coloring problem. Discrete Appl. Math. 156(7):1097–1111.Crossref, Google Scholar
• Crama Y, Oerlemans AG (1994) A column generation approach to job grouping for flexible manufacturing systems. Eur. J. Oper. Res. 78(1):58–80.Crossref, Google Scholar
• Crama Y, Moonen LS, Spieksma FC, Talloen E (2007) The tool switching problem revisited. Eur. J. Oper. Res. 182(2):952–957.Crossref, Google Scholar
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1–20.Crossref, Google Scholar
• Denizel M (2003) Minimization of the number of tool magazine setups on automated machines: A Lagrangean decomposition approach. Oper. Res. 51(2):309–320.Link, Google Scholar
• Desrosiers J, Jans R, Adulyasak Y (2013) Improved column generation algorithms for the job grouping problem. Technical report G-2013-26, Les Cahiers du GERAD, Montreal, Canada.Google Scholar
• Dror M, Haouari M (2000) Generalized Steiner problems and other variants. J. Comb. Optim. 4:415–436.Crossref, Google Scholar
• Gokgur B, Özpeynirci S (2022) Minimization of number of tool switching instants in automated manufacturing systems. J. Sci. 35(1):113–130.Google Scholar
• Goldschmidt O, Hochbaum DS, Hurkens C, Yu G (1996) Approximation algorithms for the k-clique covering problem. SIAM J. Discrete Math. 9(3):492–509.Crossref, Google Scholar
• Goldschmidt O, Nehme D, Yu G (1994) Note: On the set-union knapsack problem. Naval Res. Logist. 41(6):833–842.Crossref, Google Scholar
• Grange A, Kacem I, Martin S (2018) Algorithms for the bin packing problem with overlapping items. Comput. Indust. Engrg. 115:331–341.Crossref, Google Scholar
• Grange A, Kacem I, Martin S, Minich S (2023) Fully polynomial time approximation scheme for the pagination problem with hierarchical structure of tiles. Rairo-Oper. Res. 57(1):1–16.Crossref, Google Scholar
• Gschwind T, Irnich S (2016) Dual inequalities for stabilized column generation revisited. INFORMS J. Comput. 28(1):175–194.Link, Google Scholar
• Gschwind T, Bianchessi N, Irnich S (2019) Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem. Eur. J. Oper. Res. 278(1):91–104.Crossref, Google Scholar
• Gschwind T, Irnich S, Furini F, Calvo RW (2021) A branch-and-price framework for decomposing graphs into relaxed cliques. INFORMS J. Comput. 33(3):1070–1090.Link, Google Scholar
• He Y, Xie H, Wong TL, Wang X (2018) A novel binary artificial bee colony algorithm for the set-union knapsack problem. Future Generation Comput. Systems 78:77–86.Crossref, Google Scholar
• Heβler K, Gschwind T, Irnich S (2018) Stabilized branch-and-price algorithms for vector packing problems. Eur. J. Oper. Res. 271(2):401–419.Crossref, Google Scholar
• Hirabayashi R, Suzuki H, Tsuchiya N (1984) Optimal tool module design problem for NC machine tools. J. Oper. Res. Soc. Jpn. 27(3):205–229.Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer-Verlag, Boston), 33–65.Crossref, Google Scholar
• Izumi T, Yokomaru T, Takahashi A, Kajitani Y (1998) Computational complexity analysis of set-bin-packing problem. IEICE Trans. Fundamentals Electron. Comm. Comput. Sci. 81(5):842–849.Google Scholar
• Jans R, Desrosiers J (2010) Binary clustering problems: Symmetric, asymmetric and decomposition formulations. Technical report G-2010-44, Les Cahiers du GERAD, Montreal, Canada.Google Scholar
• Jans R, Desrosiers J (2013) Efficient symmetry breaking formulations for the job grouping problem. Comput. Oper. Res. 40(4):1132–1142.Crossref, Google Scholar
• Junglas D (2007) Optimised grid-partitioning for block structured grids in parallel computing. PhD thesis, Technische Universität Darmstadt, Fachbereich Mathematik, Darmstadt, Germany.Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin Heidelberg).Crossref, Google Scholar
• Kochetov Y, Kondakov A (2017) VNS matheuristic for a bin packing problem with a color constraint. Electron. Notes Discrete Math. 58:39–46.Crossref, Google Scholar
• Konak A, Kulturel-Konak S (2007) An ant colony optimization approach to the minimum tool switching instant problem in flexible manufacturing system. 2007 IEEE Symposium Comput. Intelligence Scheduling (IEEE, Piscataway, NJ), 43–48.Google Scholar
• Konak A, Kulturel-Konak S, Azizoğlu M (2008) Minimizing the number of tool switching instants in flexible manufacturing systems. Internat. J. Production Econom. 116(2):298–307.Crossref, Google Scholar
• Locatelli A (2023) Optimization Methods for Knapsack and tool switching problems. 4OR-Q. J. Oper. Res. 21(4):715–716.Crossref, Google Scholar
• Lübbecke M, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Marvizadeh SZ, Choobineh F (2013) Reducing the number of setups for CNC punch presses. Omega 41(2):226–235.Crossref, Google Scholar
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam), 269–280.Google Scholar
• Shirazi R, Frizelle G (2001) Minimizing the number of tool switches on a flexible machine: An empirical study. Internat. J. Production Res. 39(15):3547–3560.Crossref, Google Scholar
• Sindelar M, Sitaraman RK, Shenoy P (2011) Sharing-aware algorithms for virtual machine colocation. Proc. Twenty-Third Annual ACM Symposium Parallelism Algorithms Architectures (Association for Computing Machinery, New York), 367–378.Google Scholar
• Tang CS, Denardo EV (1988) Models arising from a flexible manufacturing machine, part II: Minimization of the number of switching instants. Oper. Res. 36(5):778–784.Link, Google Scholar
• Wahlen J, Gschwind T (2023) Branch-price-and-cut-based solution of order batching problems. Transportation Sci. 57(3):756–777.Link, Google Scholar
• Wahlen J, Gschwind T (2025) Branch-and-price for the set-union bin packing problem. https://doi.org/10.1287/ijoc.2024.0791.cd, https://github.com/INFORMSJoC/2024.0791.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
• Wei Z (2021) Optimization algorithms for two knapsack problems. PhD thesis, Université d’Angers, Angers, France.Google Scholar