Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*
A new paper introduces a totally unimodular linear program for optimal conformance checking, enhancing the traditional A*-based heuristic search. This approach aims to improve performance, particularly for longer traces with deviations. The findings suggest that combining both methods can lead to significant runtime savings and improved accuracy in conformance checking tasks.
- ▪The paper reformulates alignment-based conformance checking as a totally unimodular linear program defined on the reachability graph of the synchronous product.
- ▪The proposed LP formulation guarantees an integral optimal extreme-point solution, avoiding the combinatorial overhead of integer variables.
- ▪Empirical evaluations show that the LP approach offers substantial speedups for longer traces with deviations, complementing the A* method.
Opening excerpt (first ~120 words) tap to expand
Computer Science > Artificial Intelligence arXiv:2605.26938 (cs) [Submitted on 26 May 2026] Title:Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A* Authors:Izack Cohen View a PDF of the paper titled Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*, by Izack Cohen View PDF HTML (experimental) Abstract:Alignment-based conformance checking is the state-of-the-art approach for comparing observed process executions with normative process models. The standard exact solution relies on an A*-based heuristic search, which can exhibit exponential runtime in the presence of long traces or substantial deviations.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at arXiv cs.AI.
Discussion
0 commentsMore from arXiv cs.AI
