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

  • 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

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

Published
2019-07-06