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

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. This paper introduces a reformulation of alignment-based conformance checking as a totally unimodular linear program (LP) defined on the reachability graph of the synchronous product. By exploiting the underlying network-flow structure, the proposed formulation guarantees the existence of an integral optimal extreme-point solution through LP relaxation, thereby avoiding the combinatorial...

<iframe src="https://silytics.si/embed/item/886b17c8-a618-4aa9-9af8-c0a0b3d2995d" width="420" height="190" style="border:0" loading="lazy" title="Silytics entry"></iframe>

Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.