TY - JOUR AU - Peters, Jannik AU - Stephan, Daniel AU - Amon, Isabel AU - Gawendowicz, Hans AU - Lischeid, Julius AU - Salabarria, Lennart AU - Umland, Jonas AU - Werner, Felix AU - Krejca, Martin S. AU - Rothenberger, Ralf AU - Kotzing, Timo AU - Friedrich, Tobias PY - 2021/05/25 Y2 - 2024/03/28 TI - Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 29 IS - 1 SE - Novel Applications DO - 10.1609/icaps.v29i1.3521 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/3521 SP - 541-554 AB - <p>Assigning staff to engagements according to hard constraints while optimizing several objectives is a task encountered by many companies on a regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, a typical approach to solving them consists of formulating them as mixed integer programming (MIP) problems and using a stateof-the-art solver to get solutions that closely approximate the optimum.</p><p>In this paper, we consider a complex real-world staff assignment problem encountered by the professional service company KPMG, with the goal of finding an algorithm that solves it faster and with a better solution than a commercial MIP solver. We follow the evolutionary algorithm (EA) metaheuristic and design a search heuristic which iteratively improves a solution using domain-specific mutation operators. Furthermore, we use a flow algorithm to optimally solve a subproblem, which tremendously reduces the search space for the EA.</p><p>For our real-world instance of the assignment problem, given the same total time budget of 100 hours, a parallel EA approach finds a solution that is only 1<em>.</em>7% away from an upper bound for the (unknown) optimum within under five hours, while the MIP solver Gurobi still has a gap of 10<em>.</em>5%.</p> ER -