A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems
The many-to-many assignment problem (MMAP) is a recent topic of study in the field of combinatorial optimization. In this paper, a gradient-based interior-point method is proposed to solve MMAP. It is a deterministic method which assures an optimal solution. In this approach, the relaxation of the c...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2019/8405036 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850168179622412288 |
|---|---|
| author | Nitish Das P. Aruna Priya |
| author_facet | Nitish Das P. Aruna Priya |
| author_sort | Nitish Das |
| collection | DOAJ |
| description | The many-to-many assignment problem (MMAP) is a recent topic of study in the field of combinatorial optimization. In this paper, a gradient-based interior-point method is proposed to solve MMAP. It is a deterministic method which assures an optimal solution. In this approach, the relaxation of the constraints is performed initially using the cardinality constraint detection operation. Then, the logarithmic barrier function (LBF) based gradient descent approach is executed to reach an accurate solution. Experiments have been performed to validate the practical implementation of the proposed algorithm. It also illustrates a significant improvement in convergence speed for the large MMAPs (i.e., if group size, α≥80) over state-of-the-art literature. |
| format | Article |
| id | doaj-art-e63f06bd81da4bdfb45b3edbb23ad2a4 |
| institution | OA Journals |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-e63f06bd81da4bdfb45b3edbb23ad2a42025-08-20T02:21:02ZengWileyComplexity1076-27871099-05262019-01-01201910.1155/2019/84050368405036A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment ProblemsNitish Das0P. Aruna Priya1Department of Electronics and Communication Engg., SRM Institute of Science and Technology, Kattankulathur 603203, Chennai, IndiaDepartment of Electronics and Communication Engg., SRM Institute of Science and Technology, Kattankulathur 603203, Chennai, IndiaThe many-to-many assignment problem (MMAP) is a recent topic of study in the field of combinatorial optimization. In this paper, a gradient-based interior-point method is proposed to solve MMAP. It is a deterministic method which assures an optimal solution. In this approach, the relaxation of the constraints is performed initially using the cardinality constraint detection operation. Then, the logarithmic barrier function (LBF) based gradient descent approach is executed to reach an accurate solution. Experiments have been performed to validate the practical implementation of the proposed algorithm. It also illustrates a significant improvement in convergence speed for the large MMAPs (i.e., if group size, α≥80) over state-of-the-art literature.http://dx.doi.org/10.1155/2019/8405036 |
| spellingShingle | Nitish Das P. Aruna Priya A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems Complexity |
| title | A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems |
| title_full | A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems |
| title_fullStr | A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems |
| title_full_unstemmed | A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems |
| title_short | A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems |
| title_sort | gradient based interior point method to solve the many to many assignment problems |
| url | http://dx.doi.org/10.1155/2019/8405036 |
| work_keys_str_mv | AT nitishdas agradientbasedinteriorpointmethodtosolvethemanytomanyassignmentproblems AT parunapriya agradientbasedinteriorpointmethodtosolvethemanytomanyassignmentproblems AT nitishdas gradientbasedinteriorpointmethodtosolvethemanytomanyassignmentproblems AT parunapriya gradientbasedinteriorpointmethodtosolvethemanytomanyassignmentproblems |