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

• URL: http://arxiv.org/abs/2605.26938v1
• Date: Tue, 26 May 2026 12:30:23 GMT
• Title: Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*
• Abstract summary: This paper introduces a reformulation of alignment-based conformance checking as a totally unimodular linear program (LP)<n>By exploiting the underlying network-flow structure, the proposed formulation guarantees an optimal extreme-point solution through LP relaxation.<n>We derive simple algorithm-selection guidelines that combine both approaches, achieving average runtime savings of 38.6% with 96% selection accuracy compared to always using A*.
• Score: 0.324890820102255
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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. 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 overhead associated with integer variables and branch-and-bound search. We conduct an extensive empirical evaluation on more than 2.1 million conformance checking instances derived from real-world and synthetic benchmark datasets. The results show that A* and the LP approach exhibit complementary performance characteristics: the former performs best on short, well-conforming traces, while the LP formulation provides substantial speedups for longer traces with deviations, precisely where conformance checking is most informative. Based on these findings, we derive simple algorithm-selection guidelines that combine both approaches, achieving average runtime savings of 38.6% with 96% selection accuracy compared to always using A*.

Related papers

• Route-Align-Verify for Functional Correctness in Code Generation [0.8475107963160777]
  RAV is a lightweight and modular framework that improves code generation with a fixed backbone model through three coordinated stages.<n>We evaluate RAV on the MBPP benchmark under both the sanitized and full settings.<n>Results indicate that functional correctness in code generation can be meaningfully improved without modifying the backbone architecture.
  arXiv  Detail & Related papers  (2026-08-04T08:52:40Z)
• Self-Improving In-Context Learning [3.9202238580555417]
  We propose to improve in-context learning by optimizing the embeddings of a few prompt test at time.<n>We formalize this signal as a bounded, self-supervised calibration procedure.<n>Across a comprehensive suite of ICL tasks, the proposed calibration improves or matches upon the base model and consistently outperforms classification-specific baselines on most tasks.
  arXiv  Detail & Related papers  (2026-05-22T03:01:34Z)
• PRIME: A Process-Outcome Alignment Benchmark for Verifiable Reasoning in Mathematics and Engineering [71.15346406323827]
  We introduce PRIME, a benchmark for evaluating verifiers on Process-Outcome Alignment verification.<n>We find that current verifiers frequently fail to detect derivation flaws.<n>We propose a process-aware RLVR training paradigm utilizing verifiers selected via PRIME.
  arXiv  Detail & Related papers  (2026-02-12T04:45:01Z)
• Direct Preference Optimization with Rating Information: Practical Algorithms and Provable Gains [67.71020482405343]
  We study how to design algorithms that can leverage additional information in the form of rating gap.<n>We present new algorithms that can achieve faster statistical rates than DPO in presence of accurate rating gap information.
  arXiv  Detail & Related papers  (2026-01-31T08:38:21Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Conformance Checking for Less: Efficient Conformance Checking for Long Event Sequences [3.3170150440851485]
  ConLES is a sliding-window conformance checking approach for long event sequences.<n>It partitions traces into manageable subtraces and aligns each against the expected behavior.<n>We use global information that captures structural properties of both the trace and the process model.
  arXiv  Detail & Related papers  (2025-03-09T16:42:59Z)
• A Scalable and Near-Optimal Conformance Checking Approach for Long Traces [3.3170150440851485]
  Conformity checking, a key task in process mining, can become computationally infeasible due to the exponential complexity of finding an optimal alignment. This paper introduces a novel sliding window approach to address these scalability challenges. By breaking down traces into manageable subtraces and iteratively aligning each with the process model, our method significantly reduces the search space.
  arXiv  Detail & Related papers  (2024-06-08T11:04:42Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras [0.0]
  Relative Pose problem (RPp) for cameras aims to the relative orientation translation (pose) given a set of pair-wise rotations between two cameras. In this paper, we introduce a family of certifiers that is shown to increase the ratio of detected optimal solutions. We prove through synthetic and real data that the proposed framework provides a fast and robust relative pose estimation.
  arXiv  Detail & Related papers  (2021-01-21T10:07:05Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.