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

摘要: Assigning staff to engagements according hard constraints while optimizing several objectives is a task encountered by many companies on regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, typical approach solving them consists formulating as mixed integer programming (MIP) and using stateof-the-art solver get solutions that closely approximate the optimum.In this paper, we consider complex real-world problem professional service company KPMG, with goal finding an algorithm solves it faster better solution than commercial MIP solver. We follow evolutionary (EA) metaheuristic design search heuristic which iteratively improves domain-specific mutation operators. Furthermore, use flow optimally solve subproblem, tremendously reduces space for EA.For our instance problem, given same total time budget 100 hours, parallel EA finds only 1.7% away from upper bound (unknown) optimum within under five Gurobi still has gap 10.5%.