An effective branch and bound method to find the optimal solution of an assignment problem with maximization objective function
In this study, a different simple and successful branch and bound technique is constructed to find the best solution for the assignment problems with a maximization objective function without converting the objective function to minimization, as proposed by other assignment problem-solving strategie...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
World Scientific Publishing
2025-01-01
|
| Series: | Mathematics Open |
| Subjects: | |
| Online Access: | https://www.worldscientific.com/doi/10.1142/S281100722550004X |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In this study, a different simple and successful branch and bound technique is constructed to find the best solution for the assignment problems with a maximization objective function without converting the objective function to minimization, as proposed by other assignment problem-solving strategies. The constructed method calculates the upper boundary values and selects the maximum value for every row, which qualifies for further branching on a tree diagram. The optimal solution is the sum of the assignment values through the optimal path of a tree diagram by referring to the assignments on the original matrix. Two numerical examples were tested and verified using the new branch and bound technique, and compared with the Hungarian method. The results show that both approaches yield the same optimal solution values and profits of 97 and 369, respectively. The implementation of the new approach can help find the optimal solution of the assignment problem with less operational time and fewer steps without converting the objective function to minimization and accuracy in comparison with other methods in combinatorial optimization problems. |
|---|---|
| ISSN: | 2811-0072 |