{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:26:50Z","timestamp":1759847210850,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,12,4]],"date-time":"2021-12-04T00:00:00Z","timestamp":1638576000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,4]],"date-time":"2021-12-04T00:00:00Z","timestamp":1638576000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002957","name":"Technische Universit\u00e4t Dresden","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002957","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The aim of this letter is to design and computationally test several improvements for the compact integer linear programming (ILP) formulations of the temporal bin packing problem with fire-ups (TBPP-FU). This problem is a challenging generalization of the classical bin packing problem in which the items, interpreted as jobs of given weight, are active only during an associated time window. The TBPP-FU objective function asks for the minimization of the weighted sum of the number of bins, viewed as servers of given capacity, to execute all the jobs and the total number of fire-ups. The fire-ups count the number of times the servers are activated due to the presence of assigned active jobs. Our contributions are effective procedures to reduce the number of variables and constraints of the ILP formulations proposed in the literature as well as the introduction of new valid inequalities. By extensive computational tests we show that substantial improvements can be achieved and several instances from the literature can be solved to proven optimality for the first time.\n<\/jats:p>","DOI":"10.1007\/s11590-021-01825-x","type":"journal-article","created":{"date-parts":[[2021,12,4]],"date-time":"2021-12-04T02:02:25Z","timestamp":1638583345000},"page":"2333-2358","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups"],"prefix":"10.1007","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5428-9351","authenticated-orcid":false,"given":"John","family":"Martinovic","sequence":"first","affiliation":[]},{"given":"Nico","family":"Strasdat","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9","family":"Val\u00e9rio de Carvalho","sequence":"additional","affiliation":[]},{"given":"Fabio","family":"Furini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,4]]},"reference":[{"issue":"1","key":"1825_CR1","doi-asserted-by":"publisher","first-page":"117","DOI":"10.3390\/challe6010117","volume":"6","author":"ASG Andrae","year":"2015","unstructured":"Andrae, A.S.G., Edler, T.: On global electricity usage of communication technology: trends to 2030. Challenges 6(1), 117\u2013157 (2015)","journal-title":"Challenges"},{"issue":"1","key":"1825_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"EM Arkin","year":"1987","unstructured":"Arkin, E.M., Silverberg, E.B.: Scheduling jobs with fixed start and end times. Discret. Appl. Math. 18(1), 1\u20138 (1987)","journal-title":"Discret. Appl. Math."},{"key":"1825_CR3","doi-asserted-by":"crossref","unstructured":"Aydin, N., Muter, I., Birbil, S.I.: Multi-objective temporal bin packing problem: an application in cloud computing. Comput. Oper. Res. 121, Article 104959 (2020)","DOI":"10.1016\/j.cor.2020.104959"},{"key":"1825_CR4","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/11493853_5","volume":"3524","author":"M Bartlett","year":"2005","unstructured":"Bartlett, M., Frisch, A.M., Hamadi, Y., Miguel, I., Tarim, S., Unsworth, C.: The temporal knapsack problem and its solution. Lect. Notes Comput. Sci. 3524, 34\u201348 (2005)","journal-title":"Lect. Notes Comput. Sci."},{"issue":"3","key":"1825_CR5","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1287\/ijoc.1120.0521","volume":"25","author":"A Caprara","year":"2013","unstructured":"Caprara, A., Furini, F., Malaguti, E.: Uncommon Dantzig\u2013Wolfe reformulation for the temporal knapsack problem. INFORMS J. Comput. 25(3), 560\u2013571 (2013)","journal-title":"INFORMS J. Comput."},{"issue":"5","key":"1825_CR6","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.ipl.2016.01.008","volume":"116","author":"A Caprara","year":"2016","unstructured":"Caprara, A., Furini, F., Malaguti, E., Traversi, E.: Solving the temporal knapsack problem via recursive Dantzig\u2013Wolfe reformulation. Inf. Process. Lett. 116(5), 379\u2013386 (2016)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1825_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0166-218X(00)00267-5","volume":"111","author":"A Caprara","year":"2001","unstructured":"Caprara, A., Toth, P.: Lower bounds and algorithms for the 2-dimensional vector packing problem. Discret. Appl. Math. 111(3), 231\u2013262 (2001)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1825_CR8","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1016\/j.ejor.2020.12.036","volume":"293","author":"F Clautiaux","year":"2021","unstructured":"Clautiaux, F., Detienne, B., Guillot, G.: An iterative dynamic programming approach for the temporal knapsack problem. Eur. J. Oper. Res. 293(2), 442\u2013456 (2021)","journal-title":"Eur. J. Oper. Res."},{"key":"1825_CR9","doi-asserted-by":"crossref","unstructured":"de Cauwer, M., Mehta, D., O\u2019Sullivan, B.: The temporal bin packing problem: an application to workload management in data centres. In: Proceedings of the 28th IEEE International Conference on Tools with Artificial Intelligence, pp. 157\u2013164 (2016)","DOI":"10.1109\/ICTAI.2016.0033"},{"key":"1825_CR10","doi-asserted-by":"crossref","unstructured":"Dell\u2019Amico, M., Furini, F., Iori, M.: A branch-and-price algorithm for the temporal bin packing problem. Comput. Oper. Res. 114, Article 104825 (2020)","DOI":"10.1016\/j.cor.2019.104825"},{"key":"1825_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2016.04.030","volume":"255","author":"M Delorme","year":"2016","unstructured":"Delorme, M., Iori, M., Martello, S.: Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur. J. Oper. Res. 255, 1\u201320 (2016)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"1825_CR12","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1109\/JPROC.2018.2874895","volume":"107","author":"G Fettweis","year":"2019","unstructured":"Fettweis, G., D\u00f6rpinghaus, M., Castrillon, J., Kumar, A., Baier, C., Bock, K., Ellinger, F., Fery, A., Fitzek, F., H\u00e4rtig, H., Jamshidi, K., Kissinger, T., Lehner, W., Mertig, M., Nagel, W., Nguyen, G.T., Plettemeier, D., Schr\u00f6ter, M., Strufe, T.: Architecture and advanced electronics pathways towards highly adaptive energy-efficient computing. Proc. IEEE 107(1), 204\u2013231 (2019)","journal-title":"Proc. IEEE"},{"issue":"2","key":"1825_CR13","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/j.ejor.2020.06.050","volume":"289","author":"M Iori","year":"2021","unstructured":"Iori, M., de Lima, V.L., Martello, S., Miyazawa, F.K., Monaci, M.: Exact solution techniques for two-dimensional cutting and packing. Eur. J. Oper. Res. 289(2), 399\u2013415 (2021)","journal-title":"Eur. J. Oper. Res."},{"key":"1825_CR14","doi-asserted-by":"crossref","unstructured":"Jones, N.: How to stop data centres from gobbling up the world\u2019s electricity. Nature 561, 163\u2013166 (2018)","DOI":"10.1038\/d41586-018-06610-y"},{"key":"1825_CR15","doi-asserted-by":"crossref","unstructured":"Kantorovich, L.V.: Mathematical methods of organising and planning production. Manag. Sci. 6, 366\u2013422 (1939 Russian, 1960 English)","DOI":"10.1287\/mnsc.6.4.366"},{"issue":"3","key":"1825_CR16","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1287\/ijoc.15.3.310.16082","volume":"15","author":"S Martello","year":"2003","unstructured":"Martello, S., Monaci, M., Vigo, D.: An exact approach to the strip-packing problem. INFORMS J. Comput. 15(3), 310\u2013319 (2003)","journal-title":"INFORMS J. Comput."},{"key":"1825_CR17","doi-asserted-by":"crossref","unstructured":"Martinovic, J., Strasdat, N., Selch, M.: Compact integer linear programming formulations for the temporal bin packing problem with fire-ups. Comput. Oper. Res. 132, Article 105288 (2021)","DOI":"10.1016\/j.cor.2021.105288"},{"key":"1825_CR18","doi-asserted-by":"crossref","unstructured":"Scheithauer, G.: Introduction to cutting and packing optimization\u2014problems, modeling approaches, solution methods. In: International Series in Operations Research & Management Science, vol. 263. Springer (2018)","DOI":"10.1007\/978-3-319-64403-5_1"},{"key":"1825_CR19","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0305-0548(94)90059-0","volume":"21","author":"FCR Spieksma","year":"1994","unstructured":"Spieksma, F.C.R.: A branch-and-bound algorithm for the two-dimensional vector packing problem. Comput. Oper. Res. 21, 19\u201325 (1994)","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"1825_CR20","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0377-2217(02)00124-8","volume":"141","author":"JM Val\u00e9rio de Carvalho","year":"2002","unstructured":"Val\u00e9rio de Carvalho, J.M.: LP models for bin packing and cutting stock problems. Eur. J. Oper. Res. 141(2), 253\u2013273 (2002)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"1825_CR21","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1287\/opre.37.5.741","volume":"37","author":"LA Wolsey","year":"1989","unstructured":"Wolsey, L.A.: Uncapacitated lot-sizing problems with start-up costs. Oper. Res. 37(5), 741\u2013747 (1989)","journal-title":"Oper. Res."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01825-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01825-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01825-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T12:56:50Z","timestamp":1665061010000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01825-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,4]]},"references-count":21,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1825"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01825-x","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2021,12,4]]},"assertion":[{"value":"20 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they do not have any conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The instances were solved by the commercial software Gurobi. The underlying implementation of the models in Python can be found in .","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}