Lagrangian relaxation versus genetic algorithm based metaheuristic for a large partitioning problem

Publication Type:
Journal Article
Citation:
Theoretical Computer Science, 2018, 718 pp. 24 - 36
Issue Date:
2018-03-29
Metrics:
Full metadata record
Files in This Item:
Filename Description Size
QP_TCS_2.00.pdfAccepted Manuscript Version361.65 kB
Adobe PDF
© 2017 Elsevier B.V. This paper is concerned with a partitioning problem. One of the applications, and the motivation for this research, is the problem of class formation for training and retraining sessions at large electricity distributors. Two different approaches are developed. One is based on the Quadratic Multiple Knapsack formulation and Lagrangian relaxation. The other is a matheuristic developed as an amalgamation of Genetic Algorithms and Integer Programming. The approaches are tested by means of computational experiments. Both heuristics outperformed the direct application of quadratic programming, with the Lagrangian relaxation based approach performing the best on average, and the Genetic Algorithm based approach performing the best on the larger test cases.
Please use this identifier to cite or link to this item: