Ábrahám, Gyula and Dósa, György and Hvattum, Lars Magnus and Olaj, Tomas Attila and Tuza, Zsolt (2023) The board packing problem. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 308 (3). pp. 1056-1073. ISSN 0377-2217
|
Text
1-s2.0-S0377221723000498-main.pdf Available under License Creative Commons Attribution. Download (5MB) | Preview |
Abstract
We introduce the board packing problem (BoPP). In this problem we are given a rectangular board with a given number of rows and columns. Each position of the board has an integer value representing a gain, or revenue, that is obtained if the position is covered. A set of rectangles is also given, each with a given size and cost. The objective is to purchase some rectangles to place on the board so as to maximize the profit, which is the sum of the gain values of the covered cells minus the total cost of purchased rectangles. This problem subsumes several natural optimization problems that arise in practice. A mixedinteger programming model for the BoPP problem is provided, along with a proof that BoPP is NP -hard by reduction from the satisfiability problem. An evolutionary algorithm is also developed that can solve large instances of BoPP. We introduce benchmark instances and make extensive computer examinations.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ )
| Item Type: | Article |
|---|---|
| Additional Information: | University of Pannonia, Veszprém, Hungary Faculty of Logistics, Molde University College, Norway Alfréd Rényi Institute of Mathematics, Budapest, 1053, Hungary Export Date: 20 February 2023 CODEN: EJORD Correspondence Address: Dosa, G.; University of PannoniaHungary; email: dosagy@almos.uni-pannon.hu Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, 2019-2.1.11-TÉT-2020-00113, SNN 129364 Funding text 1: The authors would like to thank three anonymous reviewers, whose useful ideas and comments helped to improve this paper significantly. The research of Gyorgy Dosa and Zsolt Tuza is supported in part by the National Research, Development and Innovation Office – NKFIH under the grant SNN 129364 . Gyula Abraham and Gyorgy Dosa acknowledge financial support also from the Slovenian – Hungarian bilateral project, “Optimization and fault forecasting in port logistics processes using artificial intelligence, process mining and operations research”, grant 2019-2.1.11-TÉT-2020-00113. |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 05 Apr 2024 11:00 |
| Last Modified: | 05 Apr 2024 11:00 |
| URI: | https://real.mtak.hu/id/eprint/191859 |
Actions (login required)
 |
Edit Item |
