A note on the exact solution of the minimum squared load assignment problem

The problem of finding a fair assignment of tasks to agents that minimizes the total sum of squared workloads was introduced by Karsu and Azizoglu (2019) as the Minimum Squared Load Assignment Problem (MSLAP). To solve this problem, the authors developed a tailored branch-and-bound algorithm. While this algorithm was shown to produce better results than CPLEX on a mixed binary linear programming formulation of the MSLAP, about 71% of the 1200 benchmark instances yet remained unsolved. In this note, we test two state-of-the-art solvers on different mathematical programming formulations of the MSLAP. Our computational results show that the performance of the solvers is heavily dependent on the type of mathematical optimization model. The best results are obtained when the MSLAP is expressed as a quadratically-constrained program. Such a formulation allows one of the solvers to find and verify an optimal solution for every problem in the existing benchmark data sets within just a few seconds per problem, on average. Additional experiments on large-sized instances demonstrate that the solvers’ performances remain at a high level.

Link zum Paper: https://doi.org/10.1016/j.cor.2023.106309Externer Link