Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*

Researchers propose a totally unimodular linear programming approach to conformance checking in process mining as an alternative to A* search algorithms. Testing on 2.1 million instances reveals complementary performance characteristics, with the LP method achieving 38.6% average runtime improvements for longer traces with deviations while A* excels on short, well-conforming traces.

This research addresses a fundamental computational bottleneck in process mining—specifically conformance checking, which validates whether observed business process executions align with their intended models. Traditional A* heuristic search suffers exponential runtime degradation when processing lengthy traces containing significant deviations, limiting practical applicability in real-world scenarios where such complexity is common.

The proposed LP reformulation leverages network flow theory to restructure the problem on synchronous product reachability graphs. By exploiting the totally unimodular property, the method guarantees integral solutions through LP relaxation alone, circumventing expensive integer programming branches. This mathematical insight transforms a combinatorially hard problem into polynomial-time solvability for certain problem instances.

The empirical evaluation across millions of real-world and synthetic benchmarks reveals nuanced performance characteristics. A* dominates small, well-conforming datasets due to tight heuristics guiding search efficiently. Conversely, the LP approach excels precisely where conformance checking provides maximum analytical value—longer traces with deviations requiring comprehensive deviation analysis. This complementarity suggests neither algorithm universally dominates, but rather exhibit domain-specific strengths.

The derived algorithm-selection guidelines achieving 96% selection accuracy with 38.6% runtime savings represent practical value for process mining systems. Organizations analyzing complex supply chains, manufacturing processes, or compliance workflows could benefit from faster conformance analysis. The research demonstrates how mathematical structure recognition can unlock computational efficiency gains beyond algorithmic tuning.

• →LP reformulation of conformance checking guarantees integral solutions without branch-and-bound overhead through totally unimodular structure.
• →A* and LP methods show complementary performance: A* excels on short well-conforming traces while LP accelerates longer traces with deviations.
• →Testing 2.1 million instances reveals 38.6% average runtime savings using hybrid algorithm selection with 96% accuracy.
• →LP approach provides substantial speedups where conformance checking is most informative for identifying process deviations.
• →Algorithm-selection guidelines enable practical deployment combining both methods for optimal conformance checking performance.