This paper addresses conformance checking in a time-aware setting, that relates the timing of recorded events in the log with the time constraints of the process model specified as a Time Petri Net. To evaluate whether a model reflects the observed executions, several quality criteria were proposed. We define the Timed Anti-Alignment Problem as finding model traces whose timing most deviate from observed log traces. Anti-alignments, as witnesses for imprecision of the model, were proposed in untimed settings to measure precision. We solve the Purely Timed Anti-Alignment Problem for Acyclic Time Marked Graphs. By framing the problem as an optimization task with linear constraints, we enable the use of eficient Linear Programming solvers. Finally, we test our implementation's performance to understand its practicability.
Processes are crucial for organizations, coordinating activities needed for delivering products and services. The increase in event data collection has raised the need for process analysis techniques. Process Mining uses event data to discover processes, check compliance, analyze bottlenecks, compare process variants, and suggest improvements [1]. Conformance checking techniques evaluate how well a process model represents an actual process. Real executions, recorded in event logs, are collections of events executed during system operations: process models abstract these operations. The metrics that assess model accuracy include fitness, precision[ 2], generalization, and simplicity. Alignments are essential for the first three metrics, relating the model to an observed trace by providing the run that most closely resembles it [3]. This paper focuses on Anti-Alignments [4], which identify the most deviating behaviors not seen in the log. For models that should strictly adhere to specific behaviors (e.g., banking, healthcare), the absence of highly deviating Anti-Alignments and their early identification may be crucial. This conformance checking tool has been first introduced in [ 5] as a way to complement the already existing notion of alignment, i.e. the run of a process model the most similar to a given log trace. Later in the same year, in [6] the authors expanded on the utility of anti-alignments, showing how they can be used to measure two fundamental process mining metrics, i.e. precision (highly deviating anti-alignments indicate a loss in precision) and generalization [4] [6], which remains the main use of this conformance checking tool. In untimed settings, Anti-Alignments have been defined using both Hamming and Levenshtein distances [4]. For the Levenshtein distance, an implementation through a SAT encoding is provided in [7]. By introducing a discount factor into the distance calculation, a more eficient algorithm was later developed in [ 8], allowing for practical yet approximate computation with reduced complexity. However, Anti-Alignments have only been explored in untimed settings so far. Our study is instead situated in the field of Time-Aware Process Mining, which focuses on identifying timing-related properties in processes, such as the minimum delay between events or the maximum duration for the system to reach a specific state. This field not only seeks to understand the processes governing system behavior but also the time constraints they obey [9] [10] [11]. Various established process model notations already exist to incorporate time constraints. In this paper we use Time Petri
Nets (TPNs) [12], where each transition has an interval [, ] of possible firing delays: if transition was last enabled at time , then can not fire before + and must fire by + , unless it becomes disabled. Firing a transition takes no time to complete [13]. Hence, TPNs record and check the duration for firing transitions, imposing constraints on the relationships between the timestamps of diferent events. In [14], it is shown how to describe symbolically the possible execution times for events of a poset execution of a TPN. The case of extended free choice TPNs was studied in [15]. As Time-Aware Process Mining grows, it becomes necessary to adapt quality measures and conformance checking artifacts to consider temporal constraints. While in untimed contexts the computation of alignments has been widely studied [16] [17] [18], the first attempt to extend this work to timed settings was made only in [19]: the problem was addressed using two novel distance metrics and focusing exclusively on the temporal aspects of traces. The authors later expand the work to include a solution for an additional distance metric on timed traces [20]. Today, the problem of Anti-Alignments in timed settings remains unaddressed in current research: this paper aims at being the first step in this direction. We first define the General Timed Anti-Alignment Problem (GTAAP), i.e. finding the most distant traces from a log using distance functions that consider both time and activities. However, to eventually approach such problem, we initially focus on the reduced Purely Timed Anti-Alignment Problem (PTAAP), where the untimed part of traces is not considered. We consider two distance functions, Stamp-Only and Delay-Only [19]. We restrict the study to TPNs with no choice between activities and no loops, i.e., Acyclic Time Marked Graphs (ATMGs). For this class of models, each trace consists of the same activities, allowing us to ignore its untimed part to focus on Purely Timed Anti-Alignments. We present the following example to provide an initial understanding of the notion of Purely Timed Anti-Alignments. Example 1. The process in Figure 1 describes a simple refunding process of an airline (adapted from [21]): it starts with the registration of a client, the examination of their ticket, and the final decision and payment from the airline. Considering only the activity information, this model produces one trace variant, = (, , , ). However, a TPN produces "timed traces", where the timestamps for each activity must comply with the model constraints. Therefore, variants difer in terms of timestamp information. An example of a timed log accepted by this TPN is:
⎧ = ⎨ ⟨(reg, 0), (et, 2), (dec, 4), (pay, 4)⟩ ⟨(reg, 0), (et, 2), (dec, 4.5), (pay, 5)⟩ ⎩ ⟨(reg, 0.5), (et, 2.5), (dec, 5), (pay, 5.2)⟩ ⎭ ⎫ ⎬ Ignoring the activity information (as it is the same for all traces) and only considering timestamp sequences, the log becomes:
⎧
= ⎨
(
In the provided example, due to its simplicity, we could find a solution using common sense and manual checks. However, this is not feasible for all cases. In this paper, we solve the PTAAP by framing it as an optimization problem and using only linear constraints. As the problem is non-linear, we derive equivalent linear formulations, obtaining a Mixed Integer Programming (MIP) problem. This allows us to use more eficient Linear Programming solvers. We test the performance of our implementation to assess its practicability, evaluating both accuracy and time requirements for increasingly complex instances. Our results indicate lower time requirements and improved accuracy compared to a bruteforce approach. The paper is organized as follows. Section 2 provides the preliminary definitions: TPNs, functions to work with timestamps, ATMGs, and the distances used. Section 3 formalizes the GTAAP and the PTAAP, with relevant examples. Section 4 briefly summarizes the characteristics of the linear reformulation of the problem. Section 5 reports experiments and their results. Section 6 concludes the paper and suggests future research directions.
Definition 1 (Timed trace and Timed events). A timed trace is a sequence ∈ (Σ × R+)* of timed events. In other words, we represent events as pairs (, ) where ∈ Σ is the label of the action and denotes the time at which said action was taken.
Definition 2 (Timed event log). A timed event log L is a multiset of timed traces ∈ (Σ × R+)* .
The timed process model used here are Time Petri Nets.
Definition 3 (Time Petri Net [12]). A Time Petri Net (TPN) is a tuple = (, , , , Σ, , 0, ), where is the set of places, is the set of transitions (with ∩ = ∅), ⊆ ( × )∪( × ) is the flow relation, : → (R+) × (R+ ∪ {∞}) is the static interval function, with () = ( (), ()), where stands for Earliest Firing Time and for Latest Firing Time (therefore () ≤ ()), : → Σ is the labelling function that labels transitions with actions from the action set Σ, and 0, : → N are the initial and final markings.
Given a transition ∈ , the pre-set of is ∙ = { ∈ |(, ) ∈ } and its post-set is ∙ = { ∈ |(, ) ∈ } (the presets and post-sets of places are defined similarly). A transition of a TPN is enabled at marking if ∀ ∈ ∙ : () > 0. The set of all enabled transitions at a marking is denoted by Enabled(M).
A state of a TPN = (, , , , Σ, , 0, ) is a pair = (, ), where is a marking of and : ( ) → R+ is called the clock function. Every enabled transition hence has an implicit clock, measuring how long it has been since its most recent enabling. The initial state is (0, 0), where 0 is the zero function.
A transition can fire from state = (, ) after a delay of ∈ R+ if is enabled at , and () + ∈ [ (), ()], and ∀′ ∈ ( ), (′) + ≤ (′). This firing is denoted (, )[⟩( ′, ′) with new state ( ′, ′) defined as follows:
⎧⎪ () + 1 ∈ ∙ ∖ ∙ ′() = ⎨
() − 1 ∈ ∙ ∖ ∙ ⎪⎩ () ℎ ′() = {︃() + ∈ ( ′) 0
A valid execution of the model begins at the initial marking, fires a sequence of transitions and reaches , with any clock function . In this paper, we consider TPNs with only one token in every starting place.
Definition 4 (Language of a Time Petri Net). A timed trace = (, ) ∈ (Σ × R+) is in the language of (or is accepted by) a TPN, i.e. ∈ ℒ( ), if there is a fireable sequence of transitions (0, 1, ..., ) ∈ such that ⟨( (0), 0), ( (1), 1), ..., ( (), )⟩ = and they transform the initial marking into the final one, that is, for some clock function on , (0, 0)[0, 1, . . . ⟩( , ). Example 2. The TPN in Figure 2 (adapted from [21]) models the refunding process of an airline. An acceptable timed trace for it is ⟨(, 1), (, 1.5), (, 3), (, 3), (, 5)⟩. Initially, actions reg and cid are enabled: the request is registered at time 1, so the marking is updated by removing the token from reg’s pre-place and filling its two post-places, thus enabling ex and ct. After 0.5 time units, at time 1.5, the action ex is triggered, fulfilling the constraint and populating one pre-place of dec. Later, the actions cid and ct fire in parallel after being enabled for 3 and 2 units of time respectively, at time 3: as dec is now enabled, it is executed after at time 5, after two time units, and the final marking is reached.
As in this paper we will mostly consider timestamp sequences, we also define some functions that will be necessary to operate directly on sequences of timestamps.
Definition 5 (Timing function). Given a TPN N and a trace = ⟨(1, 1), ..., (, )⟩ ∈ ℒ( ), we
define the timing function for as : {1, 2, ..., } → R+ s.t. () = . The set of all acceptable
timing functions for the TPN N will be denoted as Γ , i.e. Γ = { | ∈ ℒ( )}.
Definition 6 (Timing sequence). Given a TPN N and a timing function ∈ Γ , we define the timing
sequence obtained from using the bijective function : Γ → ℛ s.t. ( ) = ( (
Example 3. Given the TPN and the trace in Example 2, the corresponding timing function is (
In order to retrieve the relationships between transitions, i.e. retrieve all the transitions that contribute to enabling a transition and all the transitions that are, at least partly, enabled by the firing of a transition , we define: Definition 7 (Parent and Children Transitions). Given a TPN N and one of its transitions , we define its parent transitions, i.e. set of transitions that, when firing, contribute to enabling , and its children transitions, i.e. the set of transitions that, when fires, become at least partly enabled, respectively as: () = ⋃︁ ∙ ∈∙ () = ⋃︁ ∙ ∈ ∙ To ease notation and improve readability, we will denote these two functions also as ∙ and ∙ respectively. We also define the recursive counterparts of these functions as: * () = ∙ ∪
⋃︁ * ( ) ∈∙ * () = ∙ ∪
⋃︁ * ( ) ∈ ∙
In this paper we use a sub-class of TPNs, Acyclic Time Marked Graphs (ATMGs), i.e. an acyclic TPN where each place has no more than one input and one output transition.
Example 4. Two examples of ATMG are in Examples 1 and 2. While the first ATMG allows only for sequential behaviour, the second one introduces parallelism at the level of the transition , executable in every moment before the execution of , and at the level of transitions and , that can be executed in diferent orders or at the same time.
As we are mainly interested in the timestamp information of timed traces, it is useful to map them to points in a n-dimensional space. Since the traces produced by ATMGs contain always the same activities, but possibly with a diferent execution order , we want to define a unique index for every transition to identify the related timestamp in a timing sequence (n-dimensional point). This implies that, when considering only timing sequences, the execution order of the events will not influence how we map activities to the sequence of timestamps. We will call this function the ordering function. We assume that each ATMG comes with a bijective ordering function : → {1, ...| |}, so that the timestamp for the event originated by transition , with () = , is the value of the i-th dimension of the mapped point. To improve readability, we refer to specific transitions using the index assigned, i.e. is the transition related to the event in the -th position of an ordered trace.
Example 5. Given the ATMG in Example 2, a possible ordering is: () = 1, () =
2, () = 3, () = 4, () = 5. Given a point = (1, 2, 3, 4, 5) ∈ R5, each
value is the timestamp of the action generated by the transition with index . An example trace
= ⟨(, 2), (, 3), (, 4), (, 2), (, 4)⟩ is then mapped to the point (
To further simplify notation, some functions defined over transitions will equivalently be defined over indexes, and vice versa (this is possible when a bijective ordering function is defined for a TPN, i.e. when neither choice nor loops are allowed, which is the case for ATMGs). For example, the function , previously defined over transitions, can be applied to indexes to return the indexes of resulting transitions: ∙ = { ∈ 1, ..., | ∈ ∙ }.
As the Anti-Alignment problem in this paper is restricted to the time relationships, we hereby describe the two types of distances that we will consider, defined by Rino and Chatain in [ 19]. To define them, we make use of the definition of moves, i.e. functions that map one time sequence to another. In [19], two types of moves are described: • Stamp Move: changes the timestamp for one event in a trace, i.e. edits one value of a timestamp sequence. • Delay Move: changes the timestamp for one event in the trace and potentially shifts the timestamps of the following actions, i.e. edits one or more values of a timestamp sequence.
Definition 8 (Stamp Move). Given an ATMG timing function : = {1, 2, ..., } → R+, ∀ ∈
R, ∀ ∈ , a Stamp Move is a function (, ) = ′ where,
Example 6. Given the ATMG N and the timing function related to the trace of Example 5, a Stamp
Move can be (
While a Stamp Move is purely local (when it is applied for the i-th activity in a trace it does not imply a derailment of the rest of the system), a Delay Move will instead preserve relative relationships in the future, potentially shifting the timestamp of every causal descendent of the action on which it is applied. However, the cost of a Delay Move is not necessarily propagated equally to all the following activities. In fact, it depends on the Flow Function, an alternative representation of timing function that, instead of assigning timestamps to a transition, labels each transition with the duration since it was enabled. Definition 9 (Flow function). Given an ATMG timing function : = {1, . . . , } → R+, the flow function of is defined as : → R+ s.t.
() = {︃ () Definition 10 (Delay Move). Given an ATMG timing function : = {1, 2, ..., } → R+, ∀ ∈ R, ∀ ∈ , a Delay Move is a function (, ) = ′, where ⎧⎪max∈∙ ′() + () ∈ * () ⎨
() + =
⎪⎩ () ℎ
Example 7. Given the ATMG and the timing function related to the trace of Example 5, the
corresponding Flow Function would be (
In the third move, the delay applied to action afects the rest of the trace because the maximum timestamp of the parents of transition changes. However, action is not delayed by the same amount as . Its new value is the new maximum previous timestamp, 5, plus the value of the flow function for , which is 0.
Distance functions for time-aware scenarios can be considered as a cost minimisation problem over the set of all moves between two traces. Specifically, given two ATMG timing functions 1, 2 over the same set = {1, 2, ..., }, we consider two distance functions: • Stamp-Only distance: the minimum cost for a sequence of Stamp Moves that transforms 1 into 2. • Delay-Only distance: the minimum cost for a sequence of Delay Moves that transforms 1 into 2.
However, formulating these distances as optimization problems is impractical. A more feasible way to compute them for ATMGs has been presented in [19].
Lemma 1 (Stamp-Only distance : ). Given two ATMG timing functions 1, 2 for the same ATMG , with | | = , the Stamp-Only distance ( 1, 2) is the Manhattan distance or L1 Norm between the two timing sequences, i.e.:
( 1, 2) = ∑︁ | 1() − 2()| = || ( 1) − ( 2)||1
=1 Lemma 2 (Delay-Only distance : ). Given two ATMG timing functions 1, 2 for the same ATMG , with | | = , the Delay-Only distance ( 1, 2) is the Manhattan distance or L1 Norm between the two timing sequences, modified by applying the flow function to them, i.e.:
( 1, 2) = ∑︁ | 1 () − 2 ()|
=1
Example 8. Given two timing functions accepted by the ATMG in Example 5, expressed as timing
sequences and with the same ordering of the example, ( 1) = (
The fact that both distances can be represented as Manhattan distances is a significant finding that makes the solution to the PTAAP similar for both.
The Anti-Alignment Problem, given a log and a TPN, involves finding the valid run(s) of the model that are the farthest from the log for a given distance metric.
Definition 11 (The General Timed Anti-Alignment Problem (GTAAP)). Given a Time Petri Net and a timed log ⊆ ℒ ( ), find a timed trace ∈ ℒ( ) such that (, ) = max ∈ℒ() (, ), where (, ) = min ∈ (, ) for some distance function on timed traces.
In untimed settings, the problem involves identifying the model run(s) that maximize the cost over the log, i.e. identifying series of moves (insertions or deletions) with the highest cost. This untimed version of the problem has been explored in [22]. However, the problem becomes more complex with timed traces, as the challenge lies in finding model runs that deviate significantly from the observed traces in both action labels and timestamps, necessitating a distance metric that covers both aspects. To eventually approach the GTAAP, one crucial yet unexplored step is to find anti-alignments only for the timed part of a trace. Consequently, the distance functions we consider to find anti-alignments are initially solely based on the timestamps of the traces (e.g. Stamp-Only and Delay-Only distances as defined previously). Thus, the problem is reduced as follows.
Definition 12 (Purely Timed Anti-Alignment Problem (PTAAP)). Given a Time Petri Net and a timed log ⊆ ℒ ( ), where the timing function for a timed trace ∈ is denoted as , find the valid timing function(s) ∈ Γ s.t. (, ) = max ∈Γ (, ), where (, ) = min ∈ ( , ) for some distance on timing functions.
In this paper, we solve the PTAAP, considering the Stamp-Only and Delay-Only distances, specifically for ATMGs. These restictions are motivated by two main factors.
First, solving the GTAAP would need an approach that incorporates additional constraints to ensure mutual coherence between Untimed Anti-Alignments (UAAs) and Purely Timed Anti-Alignments (PTAAs) while maximizing a combined distance metric (e.g. weighted sum of activity-based and timestamp-based distances). In fact, the GTAAP cannot be efectively decomposed into two independent sub-problems (finding the furthest UAA and PTAA separately), because the two solutions may not be consistent with each other. For example, the UAA may not follow the temporal constraints derived from the PTAA in models that allow for parallelism. A naive approach, such as first determining the UAA and then assigning a compliant timestamp sequence that maximizes the distance from the log, risks overemphasizing one aspect (e.g., activities) at the expense of the other (e.g., timestamps), resulting in biased or suboptimal outcomes. In previous attempts to define edit distances between timed words, e.g. in [23], the edit distance is indeed computed by first identifying an optimal sequence of edit operations that aligns the untimed parts of the words and then by minimizing the distance between the corresponding timestamp sequences.
Secondly, in [19], the Stamp-Only and Delay-Only distances were defined only for timing functions over the same causal process, i.e., for identical untimed runs on the untimed version of a TPN. This ensures meaningful comparisons of timestamps, i.e. by computing their distances only if related to the same activities. While this constraint does not pose issues when searching for Purely Timed Alignments, where the search space is confined to the timing functions allowed by a single trace’s constraints, searching for Purely Timed Anti-Alignments instead requires exploring all timing functions allowed by the model. Consequently, it is necessary to restrict the class of models to those that only produce traces with the same activity information.
We now provide examples of problem instances and their solutions to illustrate the problem and expected behaviors.
Example 9. Suppose we have the simple ATMG below, which models a simple sequential process. Note that traces will be considered just for their timestamp information, i.e. as points in a space, as described previously.
We hereby present some possible logs accepted by this model and the corresponding solution to the PTAAP, using the Stamp-Only distance as it is the most intuitive and does not require any transformation to the traces.
Event Log 1: = { } = {(0, 0, 0)}
Suppose we have a log with only one point , the minimal point of the model, obtained by executing
every transition at the earliest possible time ( s.t. ∀ ∈ , () = ()). As we seek a point
accepted by N that is farthest from the log (i.e., from ), it is clear that the solution to the PTAAP is
the maximal point = (
Event Log 2: = { , } = {(0, 0, 0), (
Given that ( 1, 2) = 3 is smaller than ( 2, 3) = 7, we can discard the first option. Since ( 3, ) = 3 is less than half the distance between 2 and 3, the optimal point is the one equidistant from 2 and 3, i.e. the point = (2, 2.75, 2.75), with ( , 2) = ( , 3) = 4.5. Notably, for the ifrst dimension (activity), the optimal timestamp is greater than those for both 2 and 3 (2 > 1 > 0), as it maximizes the distance from both traces but still within the constraints of the model. However, decisions of this kind are not always as straightforward, as the timestamp taken by a transition executed early then influences the timestamps of the following events. Therefore, a dimension-wise optimization does not necessarily guarantee the best (farthest) timestamp sequence.
For ATMGs allowing for parallelism, the timestamps taken by parallel activities will not influence each other, and only their maximal timestamp will have an impact on the timestamps of the rest of the trace.
For the Delay-Only distance, instead, dimension-wise optimization is possible since timestamp sequences are considered as their flow function form, i.e. the value taken for an activity does not influence the search space for the following.
The PTAAP can be seen as a version of the Largest Empty Sphere problem [24], where the question is to find a hypersphere of largest radius whose interior does not contain any of a finite set of points (in a -dimensional space) given as input; or equivalently, to find a point (the center of the sphere) which maximizes its distance to the set of input points, where the distance to the set of points is understood as the distance to the closest point of the set. The search space is usually delimited by bounds, e.g. the convex hull of the input points.
In our case, the input points are the time sequences in the log, their dimension is the length of the traces, and the distance is Manhattan (or 1) distance.
The Largest Empty Sphere problem has been studied, specially in small dimensions where it can be solved with good complexity (typically log() in dimension 2 with the Euclidian distance) using techniques based on Voronoi diagrams. The complexity grows exponentially with the dimension [25]. In higher dimensions, the Largest Empty Sphere becomes indeed a non-convex optimization problem (for our case, with the Manhattan distance, one sees easily the non-convexity coming from the absolute values in the definition of the distance).
For these reasons, we propose to encode our problem as a non-convex optimization problem and rely on the performances of the solvers.
The Purely Timed Anti-Alignment Problem can be viewed as an optimization problem, maximizing the chosen distance from a fixed set of observed traces , over the set of valid timestamp series ( ) for the model . The characteristics of such a search space ( ) change depending on whether the chosen ATMG allows for parallelism or not.
Therefore, the optimization problem at hand, given an ATMG , with | | = , a timed log ⊆ ℒ ( ) and using the Stamp-Only distance function, is the following: maximize As for the search space ( ), it results that, given an ATMG N with | | = equipped with a certain ordering function , each component of a -dimensional point (timestamp sequence) = (1, . . . , ) ∈ ( ) ⊂ R+ can take values in the intervals defined by the bounding function: where the operation + between an interval and a number is defined here as [1, 2]+ = [1+, 2+ ]. As the function returns an interval, for readability we will express its lower bound and upper bound as () and () respectively. In practice, this constraint ensures that the execution of transition occurs after the completion of its latest parent transition, if any, by an interval specified by the lower bound () and upper bound ().
When considering the Delay-Only distance instead, there are two diferences. First, timestamp sequences are mapped to their flow function values (so that the distance can be represented in the form of the Manhattan distance) and the search space ( ) will be much simpler, as the boundaries for each dimension can now only range within the interval defined for the corresponding transition.
Therefore, the problem becomes the following: maximize
min ∑︁ | () − | ∈ =1 subject to () ≤ ≤ (), ∀ ∈ {1, ..., }
The approach used to solve such optimization problem involves Linear Programming (LP). Linear Programming is the process of minimizing/maximizing a linear objective function subject to a finite number of linear equality and inequality constraints [26]. However, to describe the characteristics of many optimization problems it is sometimes necessary to adopt a set of non-linear terms. Finding an optimal solution for a non-linear problem in acceptable computational time is still a big challenge in the optimization theory [27]: instead, in comparison, linear forms require significantly less computational time [28]. Therefore, one of the techniques often used to solve optimization problems with non-linear terms consists in replacing the latter with equivalent linear formulations, at the cost of often increasing the size of the problem [29]. This is the case also for the Purely Timed Anti-Alignment Problem. Specifically, equivalent linear formulations are needed to express: • the fact that this is a max-min problem, i.e. a problem where the goal is to maximize the minimum of the objective function for all potential scenarios; • the absolute value contained in the objective function; • the maximum function contained in the definition of the search space ( ) for the distance .
We use established techniques [29] to retrieve linear formulations for these functions. As the structure of an ATMG can difer, we also found a simpler reformulation (in terms of number of variables and constraints) for models that allow only for sequential events (no parallelism). An in-depth explanation of the diferent linear reformulations obtained is contained in the Appendix.
We implemented the Linear Programming solution in Python1 using PuLP [30], a modeling library that uses Python syntax for constraints and supports various solvers, including the default CBC solver [31] that we used. The experiments were executed on Google Colaboratory [32], using a virtual environment with an Intel Xeon CPU @ 2.20GHz and 12 GB of available RAM.
To assess our implementation’s practicality, we generated various problem examples, varying both the model dimension ( transitions) and log cardinality ( traces). The chosen parameter values are: • Cardinality ||: {10, 100, 1000} • Dimension | |: {5, 15, 30} These values reflect realistic scenarios, as process models typically do not reach extremely high complexity in the number of transitions, but logs often contain many traces and events.
As we found diferent linear formulations depending on whether parallelism is allowed or not in the model, we tested them separately to study the diference in eficiency. We therefore considered two types of models, sequential ATMGs (as in Example 9) and ATMGs with parallelism: since for the second type diferent structures are allowed, the chosen one is shown in Figure 3.
We automatically generated models and logs of increasing complexity as follows: 1Available at: github.com/StefanoBavaro/TimedAntiAlignments
• Given a model dimension , an ATMG with transitions is generated, following the structures
mentioned above. For each transition , the timestamp interval () is set using a random
process. The lower bound is a random number between 0 and 5, rounded to two decimal places
( () ∼ Uniform(
This creates intervals with variable ranges, better representing real time relationships. • Given the generated model and some cardinality , a log with points is created by randomly assigning valid values (rounded to two decimal places) for each dimension, ensuring each point is accepted by .
For every combination of dimension, cardinality and type of ATMGs, we compute the time needed for the solver to find the optimal point, the number of variables (#V) and the number of constraints (#C). As for the last two measures, we can identify three cases by observing the linear formulations: 1. Sequential ATMGs for both distances and ATMGs allowing parallelism and with the structure in Fig 3 for distance , that share the number of constraints and variables, i.e. # = 1+3(× )+ and # = + 3( × ) + 2. 2. ATMGs allowing parallelism with the structure in Fig 3 with distance , for which # = 1 + 3( × ) + 4 − 5 and # = 1 + 3( × ) + 8 − 12. 3. ATMGs allowing parallelism with no specific structure. In this case, the determining factors are the amount of non-starting transitions | | (with = { ∈ {1, ..., } | ∙ ̸= ∅}) and the number of parent transitions for each of them. We computed the lower and upper bounds for such metrics in this case, as the exact value depends on these variable factors, obtaining that 1 + 3( × ) + ≤ # ≤ 1 + 3( × ) + + | | + | |2 and that + 3( × ) + 2 ≤ # ≤ + 3( × ) + 2 + 3| |2.
Note that, for the metric #, the amounts reported are the ones computed by our implementation, that do not consider variables being binary or positive as constraints as they can just be declared as such.
Results (the elapsed time is expressed in seconds, rounded to the nearest integer) for the two structures of models are reported in Tables 1 and 2.
As expected, time requirements significantly increase with the growth of variables and constraints. More time is usually needed to solve the problem when considering the Delay-Only distance for Sequential ATMGs: as the amount of variables and constraints do not change for the two distances, a possible factor might be the change in magnitude of the search space. Instead, for the second type of ATMGs, it usually takes less time to solve the problem when considering the Delay-Only distance: this can be explained by the lower amount of variables and constraints for the two distance settings. However, to interpet these results, it is necessary to consider the high variability in the performance of MIP solvers [33], influenced by factors like variable declaration order and search space shape. Hence, the reported time needed to solve diferent instances of the PTAAP ofers insights into the solver behavior across diferent problem settings, but cannot precisely indicate solve times for further similar instances with the same controlled parameters, as also the specific time constraints and the log provided can have an impact.
To provide a baseline for comparison, we also implemented a Brute-Force solver and tested it against the LP solver. The brute force approach builds the search space recursively by splitting the range of possible timestamps into evenly spaced values for each dimension. Each value is then used to compute the timestamps for the following dimensions in the point, until the final dimension is reached and the complete point is added to the search space. The computational complexity, both in time and space, increases with the granularity of the timestamp intervals: finer splits improve accuracy but require more computational resources. Every point in such search space is a possible solution: the solver computes the distance from the log for each point and selects the maximum as the optimal distance. The results (execution time in seconds, rounded to the nearest integer) of both solvers for both types of ATMGs are presented in Tables 3. The interval subdivision value for the brute-force search space is 5.
The brute-force approach performs significantly worse for increasing dimensions, as evidenced by the steep growth in execution time in the models with 10 and 11 dimensions. In fact, such explosion, also in terms of RAM requirements, prevented the exploration of the BF solver beyond 11 dimensions. It can also be noticed that execution time doesn’t scale as drastically with cardinality as with dimensions: this is because computing distances is not as computationally intensive as building the search space. Finally, it is worth noticing that in some cases (in bold), the distance found by the LP solver was greater (therefore better) by some decimals than the one found through the BF approach: this might be due to insuficient discretization of the BF search space, which, if increased, would require even more time and space resources.
In this paper, we introduced time-aware anti-alignments and solved the Purely Timed Anti-Alignment Problem for Acyclic Time Marked Graphs using the Stamp-Only and Delay-Only distances. Our LP implementation of the problem, reformulated as a Mixed-Integer Programming problem, notably outperformed a brute-force solver as model complexity increased. Alongside [19] and [20], our work contributes to advancing conformance checking in time-aware process mining. Solving the Purely Timed Anti-Alignment Problem is key to potentially defining new time-aware metrics using timed anti-alignments, e.g. for precision or generalization as done in untimed settings. Future research could explore solving the problem for other distance functions, such as the Mixed-Moves distance [19]. The work can also be extended to models that include loops or choice: this would probably require new ways of computing the Stamp-Only and Delay-Only distances, so that to compare timestamps related to diferent sequences of activities. Finally, this is another step towards tackling the General Timed Anti-Alignment Problem, which would require additional strategies to balance the contributions of activity-based and timestamp-based distances while ensuring coherence between the purely-timed and untimed optimal anti-alignments.
During the preparation of this work, the authors did not use any GenAI tool. [30] S. Mitchell, M. OSullivan, I. Dunning, Pulp: a linear programming toolkit for python, The
University of Auckland, Auckland, New Zealand 65 (2011). [31] J. Forrest, R. Lougee-Heimer, Cbc user guide, in: Emerging theory, methods, and applications,
INFORMS, 2005, pp. 257–277. [32] Google, Google colaboratory, 2024. URL: https://colab.research.google.com/. [33] A. Lodi, A. Tramontani, Performance variability in mixed-integer programming, in: Theory driven by influential applications, INFORMS, 2013, pp. 1–12.
We start by presenting the reformulation for the Stamp-Only distance, which is the most straightforward case as no transformation has to be performed on traces. We later present how to adapt the solution to the Delay-Only Distance. The initial form of the problem is then:
Note that in the further formulations, to ease notation, we will identify the timing function related to a trace as rather than .
In the following sections, we detail every reformulation needed, showing how each non-linear constraint can be transformed into a linear form.
The problem at hand is a Maximin problem, i.e. a problem where the goal is to maximize the minimum of the objective function for all potential scenarios. In fact, we aim at maximizing the distance with the timed log, which by definition is the minimum distance from any point in the log. We therefore introduce a new objective function, represented by the only variable . The decision variables are now used to set , through multiple linear inequalities, as lower than the distance from any point in the log . This way, an upper bound is set for so that, by maximizing it, the minimum distance from any point in the log is necessarily obtained. The first transformation is therefore the following: maximize subject to ≤
∑︁ | () − |, ∀ ∈ {1, ..., } =1 ∈ ( ) where is the cardinality of the log .
To reformulate the absolute value function, it is needed to express the values of every absolute diference | () − |. To do so, we introduce new positive variables dif +, and dif −, for each element of the log and each dimension of the solution space, i.e. ∀ ∈ = {1, ..., } and ∀ ∈ = {1, ..., }. By using binary variables ,, we also set one of the two variables dif +, and dif −, to be 0 (Constraints 3 and 4). The constant is used to prevent any of these variables from becoming infinite: we set it as the maximum possible distance between two points in the search space, i.e. the distance between the minimal trace and the maximal trace , ( , ). With these constraints, we split () − into the possibly positive and negative results (Constraint 2). If () − is positive, its value will be taken by dif +,; vice versa, if () − is negative, the absolute value will be taken by dif −,. Therefore, it follows that | () − | = dif +, + dif −,, which is indeed substituted in Constraint 1.
The reformulated linear programming problem incorporating these transformations is then:
maximize
subject to
≤
dif +, − dif −, = () − ,
∀ ∈ , ∀ ∈
(
With this function, we can now explict (for sequential ATMGs) the constraint ∈ ( ) that we
momentarily left out in the previous formulations in the form of the new Constraint 6. Therefore, the
problem will now be:
0 ≤ dif −, ≤ · (1 − ,),
(
This reformulation transforms the original problem with absolute value functions into a Mixed Integer Programming (MIP) problem (due to the presence of binary variables, considered as integers) that can be eficiently solved using linear programming solvers.
Finally, we specify the constraints of the search space ( ), i.e. the constraints for each decision variable . For sequential ATMGs, the search space can be further simplified than the one presented in the paper. Given a sequential ATMG N with | | = equipped with a standard ordering function that trivially follows the causal relationships of the transitions, each component of a d-dimensional point (timestamp sequence) = (1, . . . , ) ∈ ( ) ⊂ R+ can take values in the intervals defined by the bounding function: maximize subject to ≤ 0 ≤ dif −, ≤ · (1 − ,), () ≤ ≤ (), ∀ ∈ {1, ..., }
When dealing with ATMGs with paralellism, the search space ( ) changes as defined previously (Section 4). Additional complexity arises as now transitions can have multiple parent transitions: therefore, it is needed to retrieve only the maximum value among their timestamps. For transitions without parents, no reformulation is needed (Constraint 6) and the constraint is the same as for sequential ATMGs. Instead, when a transition has any parent transition (for readability, = { ∈ {1, ..., } | ∙ ̸= ∅} is the set of indexes of transitions with any parent transition), we need to reformulate the function for both inequalities (i.e. both endpoints of the interval).
The inequality max∈∙ + () ≤ can be directly modeled by defining the same for each parent transition instead of just the maximal (Constraint 7): the inequality with the maximum term will be a stricter constraint, therefore dictating the lower bound for .
The second inequality ≤ max∈∙ + () requires additional variables to express the function[29]. We introduce a variable maxVar for every transition to act as a proxy for the maximum timestamp of the transition’s parents (Constraint 12). First, the lower bound of every maxVar is set as the maximal timestamp of parent transitions (Constraint 8) as done previously. The upper bound, which has to be the same as the lower bound, is set using binary variables , whose sum is 1 (Constraint 10). Constraint 9 prevent any maxVar from becoming infinite and, as the only assignment of binary variables that make the problem feasible is the one for which only the binary variable related to the maximum of the parents timestamps is set to 1, maxVar will take exactly the maximal value of parents transactions.
Finally, the problem will now be:
maximize
subject to
≤
0 ≤ dif −, ≤ · (1 − ,),
() ≤ ≤ (), ∀ ∈ . ∙ = ∅
() + ≤ , ∀ ∈ , ∀ ∈ ∙
≤ , ∀ ∈ , ∀ ∈ ∙
≤ + · (1 − ,), ∀ ∈ , ∀ ∈ ∙
∑︁ , = 1, ∀ ∈
∈∙
, ∈ {0, 1}, ∀ ∈ , ∀ ∈ ∙
≤ () + , ∀ ∈
(
We here present the full reformulation of the PTAAP for ATMGs considering the Delay-Only distance
rather than the Stamp-Only distance. The two main main diferences are presented already in Section 4,
and correspond to Constraints 2 and 6. Therefore, the formulation of such problem is:
maximize
subject to
dif +, − dif −, = () − ,
0 ≤ dif −, ≤ · (1 − ,),
(
Due to the transformation of the traces given as input, the optimal point obtained in this case needs to be mapped back to the original timestamp values, i.e. by reverting the efect of the flow function. To do that, one can simply sum the values of the found optimal point according to the transitions relationships. Therefore, given the obtained optimal sequence, which can as well be represented as a timing function , the timing function of the non-transformed trace is: {︃ () + max∈∙ () ℎ