A decomposition approach for multidimensional knapsacks with family‐split penalties.
Saved in:
| Title: | A decomposition approach for multidimensional knapsacks with family‐split penalties. |
|---|---|
| Authors: | Mancini, Simona1,2 (AUTHOR) simona.mancini@aau.at, Meloni, Carlo3 (AUTHOR) carlo.meloni@uniroma1.it, Ciavotta, Michele4 (AUTHOR) michele.ciavotta@unimib.it |
| Source: | International Transactions in Operational Research. Jul2024, Vol. 31 Issue 4, p2247-2271. 25p. |
| Subjects: | Backpacks, Knapsack problems, Overhead costs, Integer programming, Decomposition method |
| Abstract: | The optimization of Multidimensional Knapsacks with Family‐Split Penalties has been introduced in the literature as a variant of the more classical Multidimensional Knapsack and Multi‐Knapsack problems. This problem deals with a set of items partitioned in families, and when a single item is picked to maximize the utility, then all items in its family must be picked. Items from the same family can be assigned to different knapsacks, and in this situation split penalties are paid. This problem arises in real applications in various fields. This paper proposes a new exact and fast algorithm based on a specific Combinatorial Benders Cuts scheme. An extensive experimental campaign computationally shows the validity of the proposed method and its superior performance compared to both commercial solvers and state‐of‐the‐art approaches. The paper also addresses algorithmic flexibility and scalability issues, investigates challenging cases, and analyzes the impact of problem parameters on the algorithm behavior. Moreover, it shows the applicability of the proposed approach to a wider class of realistic problems, including fixed costs related to each knapsack utilization. Finally, further possible research directions are considered. [ABSTRACT FROM AUTHOR] |
| Copyright of International Transactions in Operational Research is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | The optimization of Multidimensional Knapsacks with Family‐Split Penalties has been introduced in the literature as a variant of the more classical Multidimensional Knapsack and Multi‐Knapsack problems. This problem deals with a set of items partitioned in families, and when a single item is picked to maximize the utility, then all items in its family must be picked. Items from the same family can be assigned to different knapsacks, and in this situation split penalties are paid. This problem arises in real applications in various fields. This paper proposes a new exact and fast algorithm based on a specific Combinatorial Benders Cuts scheme. An extensive experimental campaign computationally shows the validity of the proposed method and its superior performance compared to both commercial solvers and state‐of‐the‐art approaches. The paper also addresses algorithmic flexibility and scalability issues, investigates challenging cases, and analyzes the impact of problem parameters on the algorithm behavior. Moreover, it shows the applicability of the proposed approach to a wider class of realistic problems, including fixed costs related to each knapsack utilization. Finally, further possible research directions are considered. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 09696016 |
| DOI: | 10.1111/itor.13207 |
