Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem

Authors

  • Jannik Peters University of Potsdam
  • Daniel Stephan University of Potsdam
  • Isabel Amon University of Potsdam
  • Hans Gawendowicz University of Potsdam
  • Julius Lischeid University of Potsdam
  • Lennart Salabarria University of Potsdam
  • Jonas Umland University of Potsdam
  • Felix Werner University of Potsdam
  • Martin S. Krejca University of Potsdam
  • Ralf Rothenberger University of Potsdam
  • Timo Kotzing University of Potsdam
  • Tobias Friedrich University of Potsdam

DOI:

https://doi.org/10.1609/icaps.v29i1.3521

Abstract

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.

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.

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.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.5%.

Downloads

Published

2021-05-25

How to Cite

Peters, J., Stephan, D., Amon, I., Gawendowicz, H., Lischeid, J., Salabarria, L., Umland, J., Werner, F., Krejca, M. S., Rothenberger, R., Kotzing, T., & Friedrich, T. (2021). Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 541-554. https://doi.org/10.1609/icaps.v29i1.3521