1. the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result; Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem 2. the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s); Jannik Peters Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany jannik.peters@student.hpi.de +49 331 5509-415 Daniel Stephan Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany daniel.stephan@student.hpi.de +49 331 5509-415 Isabel Amon Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany isabel.amon@student.hpi.de +49 331 5509-415 Hans Gawendowicz Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany hans.gawendowicz@student.hpi.de +49 331 5509-415 Julius Lischeid Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany julius.lischeid@student.hpi.de +49 331 5509-415 Lennart Salabarria Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany lennart.salabarria@student.hpi.de +49 331 5509-415 Jonas Umland Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany jonas.umland@student.hpi.de +49 331 5509-415 Felix Werner Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany felix.werner@student.hpi.de +49 331 5509-415 Martin S. Krejca Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany martin.krejca@hpi.de +49 331 5509-415 Ralf Rothenberger Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany ralf.rothenberger@hpi.de +49 331 5509-417 Timo Kötzing Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany timo.koetzing@hpi.de +49 331 5509-418 Tobias Friedrich Hasso-Plattner-Institut University of Potsdam Prof.-Dr.-Helmert-Str. 2--3 14482 Potsdam Germany tobias.friedrich@hpi.de +49 331 5509-410 3. the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition); Tobias Friedrich 4. the abstract of the paper(s); 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 state-of-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 %. 5. a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies; (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. (G) The result solves a problem of indisputable difficulty in its field. 6. a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission); (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. Staff assignment is the most important task for professional service companies such as KPMG, since a good assignment can vastly increase the efficiency of the services provided and number of satisfied customers, which increases the revenue of the company. To this date, all major companies in the area of financial audit assign their employees manually for a certain period in advance, since the underlying problem is deemed too complex for computers. Undoubtedly, this task is very time-consuming, error prone, and most likely follows a local greedy approach. Over time, managers get better in assigning their staff, as they learn from previous assignments and also know the preferences of their employees better. Nonetheless, the task is very time-consuming, and the quality of the result unknown, as the managers are unable to consider many different assignments at the same time and compare them. Our approach automates the process described above. By incorporating as much expert knowledge of managers as possible, our algorithm is able to determine the quality of an assignment. This makes it feasible to use an EA in order to solve the problem. Already after a few minutes, the EA produces solutions that are of a better quality than the solutions of the mangers, as has been confirmed by the managers of KPMG themselves for two instances, each spanning an entire year. After about an hour, the quality of the produced solutions is already margins above human level. As a consequence, KPMG is now using our approach for all of their branches in Germany independently. (G) The result solves a problem of indisputable difficulty in its field. Since the EA produces solutions better than those of humans very quickly, we compared it to the state-of-the-art MIP solver Gurobi. If the assignment problem were easy, Gurobi should be able to find solutions of at least equal quality to those of the EA quickly. However, as our paper demonstrates, the EA outperforms Gurobi significantly by finding a solution that is only by 1.7 % off from an upper bound of an optimal solution, while Gurobi only finds a solution that is still 10.5 % off. Thus, the problem seems to be hard, and the EA is able to optimize it very well. The hardness of this problem is further acknowledged by the reviewers of the 29th International Conference on Automated Planning and Scheduling (ICAPS'19; held July 11--15) -- the top conference (rated A* on CORE) for scheduling --, who accepted our paper. 7. a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable); Currently in press of ICAPS 2019. Proof of acceptance can be found at: https://icaps19.icaps-conference.org/program.html#papers Author names: Jannik Peters, Daniel Stephan, Isabel Amon, Hans Gawendowicz, Julius Lischeid, Lennart Salabarria, Jonas Umland, Felix Werner, Martin S. Krejca, Ralf Rothenberger, Timo Kötzing, Tobias Friedrich Name of conference: 29th International Conference on Automated Planning and Scheduling (ICAPS'19) 8. a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors; Any prize money, if any, is to be divided equally among the eight undergraduate students of this paper, who worked one year on the algorithm. The students' names are: - Jannik Peters, - Daniel Stephan, - Isabel Amon, - Hans Gawendowicz, - Julius Lischeid, - Lennart Salabarria, - Jonas Umland, and - Felix Werner. 9. a statement stating why the authors expect that their entry would be the "best," and We believe that the strongest point of our entry is that it does not only outperform human-level achievements but also those of a state-of-the-art solver and, thus, showcases very well the merits of EAs compared to other optimization approaches. EAs are capable of coping with highly complex problems that other algorithms fail at, while being guided by an objective that is sketched by human intuition. Additionally, our approach has further features that make it more attractive than other approaches: - It is customizable. The objective function can be tuned or switched for another one easily. In fact, our interface allows the user to choose weights for different objectives. Further, the set of mutation operators can be adjusted easily. This allows to experiment with different operators. Additionally, this means that the EA is able to solve a great class of assignment problems, not only those in the area of financial audit. - It is fast. After roughly an hour, our algorithm creates solutions of a far better quality than those of humans taking months of planning. This speed allows an efficient reoptimization of an instance if it is changed, which happens frequently when creating assignment schedules. In addition to that, it also allows for rapid tests of different operators or objective functions. - It works well with custom initial solutions. This allows the user to input their own solutions (or parts thereof) into the solver and see how it can be even further optimized. This also helps in reoptimization, as the algorithm does not need to start from a random initial solution but can, instead, quickly start from an old (optimized) solution. - It can provide multiple solutions. Due to the random nature of the EA and its speed allowing to be run in parallel easily, it will most likely create different solutions of similar quality. While some of these features can also be found in different optimization algorithms, such as Gurobi, it is generally hard to find all of them at once. Since our algorithm is used mainly by people who are not computer scientists, the ease and flexibility of our solution is a great benefit. 10. An indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc. memetic algorithm, using a combination of an EA and a min-cost max-flow algorithm 11. The date of publication of each paper. If the date of publication is not on or before the deadline for submission, but instead, the paper has been unconditionally accepted for publication and is “in press” by the deadline for this competition, the entry must include a copy of the documentation establishing that the paper meets the "in press" requirement. Copy of the paper attached to the e-mail.