A robust heuristic for the Generalized Assignment Problem.
Saved in:
| Title: | A robust heuristic for the Generalized Assignment Problem. |
|---|---|
| Authors: | Racer, Michael1 racerm@msuvx1.memst.edu, Amini, Mohammad M.2 aminim@msuvx1.memst.edu |
| Source: | Annals of Operations Research. 1994, Vol. 50 Issue 1-4, p487-503. 17p. |
| Subjects: | Operations research, Nonlinear assignment problems, Nonlinear statistical models, Mathematical optimization, Heuristic, Duality (Logic) |
| Abstract: | The Generalized Assignment Problem, in the class of NP-hard problems, occurs in a wide range of applications — vehicle packing, computers, and logistics, to name only a few. Previous research has been concentrated on optimization methodologies for the GAP. Because the Generalized Assignment Problem is NP-hard, optimization methods tend to require larger computation times for large-scale problems. This paper presents a new heuristic, Variable-Depth-Search Heuristic (VDSH). We show that on the sets of large test problems, the quality of the solution found by VDSH exceeds that of the leading heuristic by an average of over twenty percent, while maintaining acceptable solution times. On difficult problem instances, VDSH provides solutions having costs 140% less than those found by the leading heuristic. A duality gap analysis of VDSH demonstrates the robustness of our heuristics. [ABSTRACT FROM AUTHOR] |
| Copyright of Annals of Operations Research is the property of Springer Nature 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 18649968 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A robust heuristic for the Generalized Assignment Problem. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Racer%2C+Michael%22">Racer, Michael</searchLink><relatesTo>1</relatesTo><i> racerm@msuvx1.memst.edu</i><br /><searchLink fieldCode="AR" term="%22Amini%2C+Mohammad+M%2E%22">Amini, Mohammad M.</searchLink><relatesTo>2</relatesTo><i> aminim@msuvx1.memst.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Annals+of+Operations+Research%22">Annals of Operations Research</searchLink>. 1994, Vol. 50 Issue 1-4, p487-503. 17p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Operations+research%22">Operations research</searchLink><br /><searchLink fieldCode="DE" term="%22Nonlinear+assignment+problems%22">Nonlinear assignment problems</searchLink><br /><searchLink fieldCode="DE" term="%22Nonlinear+statistical+models%22">Nonlinear statistical models</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Heuristic%22">Heuristic</searchLink><br /><searchLink fieldCode="DE" term="%22Duality+%28Logic%29%22">Duality (Logic)</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: The Generalized Assignment Problem, in the class of NP-hard problems, occurs in a wide range of applications — vehicle packing, computers, and logistics, to name only a few. Previous research has been concentrated on optimization methodologies for the GAP. Because the Generalized Assignment Problem is NP-hard, optimization methods tend to require larger computation times for large-scale problems. This paper presents a new heuristic, Variable-Depth-Search Heuristic (VDSH). We show that on the sets of large test problems, the quality of the solution found by VDSH exceeds that of the leading heuristic by an average of over twenty percent, while maintaining acceptable solution times. On difficult problem instances, VDSH provides solutions having costs 140% less than those found by the leading heuristic. A duality gap analysis of VDSH demonstrates the robustness of our heuristics. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Annals of Operations Research is the property of Springer Nature 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=18649968 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/BF02085655 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 17 StartPage: 487 Subjects: – SubjectFull: Operations research Type: general – SubjectFull: Nonlinear assignment problems Type: general – SubjectFull: Nonlinear statistical models Type: general – SubjectFull: Mathematical optimization Type: general – SubjectFull: Heuristic Type: general – SubjectFull: Duality (Logic) Type: general Titles: – TitleFull: A robust heuristic for the Generalized Assignment Problem. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Racer, Michael – PersonEntity: Name: NameFull: Amini, Mohammad M. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 04 Text: 1994 Type: published Y: 1994 Identifiers: – Type: issn-print Value: 02545330 Numbering: – Type: volume Value: 50 – Type: issue Value: 1-4 Titles: – TitleFull: Annals of Operations Research Type: main |
| ResultId | 1 |
