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.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 175945771 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A decomposition approach for multidimensional knapsacks with family‐split penalties. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Mancini%2C+Simona%22">Mancini, Simona</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> simona.mancini@aau.at</i><br /><searchLink fieldCode="AR" term="%22Meloni%2C+Carlo%22">Meloni, Carlo</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> carlo.meloni@uniroma1.it</i><br /><searchLink fieldCode="AR" term="%22Ciavotta%2C+Michele%22">Ciavotta, Michele</searchLink><relatesTo>4</relatesTo> (AUTHOR)<i> michele.ciavotta@unimib.it</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22International+Transactions+in+Operational+Research%22">International Transactions in Operational Research</searchLink>. Jul2024, Vol. 31 Issue 4, p2247-2271. 25p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Backpacks%22">Backpacks</searchLink><br /><searchLink fieldCode="DE" term="%22Knapsack+problems%22">Knapsack problems</searchLink><br /><searchLink fieldCode="DE" term="%22Overhead+costs%22">Overhead costs</searchLink><br /><searchLink fieldCode="DE" term="%22Integer+programming%22">Integer programming</searchLink><br /><searchLink fieldCode="DE" term="%22Decomposition+method%22">Decomposition method</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=175945771 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1111/itor.13207 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 25 StartPage: 2247 Subjects: – SubjectFull: Backpacks Type: general – SubjectFull: Knapsack problems Type: general – SubjectFull: Overhead costs Type: general – SubjectFull: Integer programming Type: general – SubjectFull: Decomposition method Type: general Titles: – TitleFull: A decomposition approach for multidimensional knapsacks with family‐split penalties. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Mancini, Simona – PersonEntity: Name: NameFull: Meloni, Carlo – PersonEntity: Name: NameFull: Ciavotta, Michele IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: Jul2024 Type: published Y: 2024 Identifiers: – Type: issn-print Value: 09696016 Numbering: – Type: volume Value: 31 – Type: issue Value: 4 Titles: – TitleFull: International Transactions in Operational Research Type: main |
| ResultId | 1 |
