Process Tree Alignments
摘要
The state-of-the-art approach for computing alignments is to apply an exhaustive state-space search with a well-tailored A*-heuristic function. If the heuristic fails to provide good estimates, the alignment computation quickly becomes infeasible even for small event logs given the exponential search space. Since intractability is unavoidable for general process models, we here consider the restricted class of process trees which provides a good balance between expressiveness and algorithmic feasibility. As our main result, we prove that alignments on process trees can be expressed as solutions of Mixed Integer Linear Programs (MILP). Our novel approach does not only position the problem inside the class of NP, but also paves the way for applying a host of new optimization techniques from the field of mathematical programming to alignments on process trees. We further show that for process trees without parallel executions, our MILP formulation becomes a Linear Program (LP) which can be solved efficiently. This result gives fresh insights into the structure of the alignment problem and the role of concurrency as a key factor for intractability. Finally, we implement our new algorithmic approach in PM4Py and evaluate the performance against the standard algorithms.