The language-based theory of regions, stemming from the area of Petri net synthesis, forms a fundamental basis for Integer Linear Programming (ILP)-based process discovery. Based on example behavior in an event log, a process model is derived that aims to describe the observed behavior. Building on top of the existing ILP-formulation, we present a new ILP-based process discovery formulation that unifies two existing types of language-based regions and, additionally, we present a generalized ILP objective function that captures both region-types and helps us to find suitable process discovery results.
Process Mining [
The area of Petri net synthesis [
Language-based region theory forms a fundamental basis for ILP-based process
discovery [
In this paper we propose a unified approach w.r.t. ILP-based process discovery, based on the newly introduced concept of hybrid variable-based regions. Hybrid variablebased regions unite two existing language-based region definitions and allow us to vary the number of variables used within the ILP problems being solved. Therefore, we assess the impact of using a different number of variables on the average computation time of solving ILPs during ILP-based process discovery. Additionally we present a new generalized ILP objective function that supports hybrid variable-based regions and show that the objective function yields correct process discovery results.
The outline of this paper is as follows. In Section 2 we present basic preliminaries. In Section 3 we present language-based regions. In Section 4 we show how to adopt language-based regions within process discovery using ILP. In Section 5 we present a brief evaluation of the performance of the approach. Section 6 covers related work. Section 7 concludes the paper. 2 2.1
Let Z denote the set of integers, let N denote the set of positive integers including 0 and let N+ denote the set of positive integers excluding 0. Let R denote the set of real numbers and let R+ denote the set of positive real numbers excluding 0.
Let S denote a set. Let us define a bag B as a function B : S ! N. Notation-wise we write a bag as [e1n1 ; e2n2 ; :::; e3n3 ], where ei 2 S, ni 2 N+ and eini B(ei) = ni. If for some element e, B(e) = 1, we omit its superscript. An empty bag is denoted as ;. As an example let S1 = fa; b; c; dg and let B1 denote a bag consisting of 3 a’s, 5 b’s, 1 c and 0 d’s, i.e. B1 = [a3; b5; c]. Element inclusion applies to bags as well, i.e. given e 2 S and B(e) > 0 then also e 2 B. Thus we have a 2 B1 whereas d 2= B1.
A sequence is a function relating positions to elements e 2 S, i.e. : f1; 2; :::; kg ! S. An empty sequence is denoted as . We write every non-empty sequence as he1; e2; :::; eki. The set of all possible sequences over a set S is denoted as S . We define concatenation of sequences 1 and 2 as 1 2, e.g., ha; bi hc; di = ha; b; c; di. If we are given a set X of sequences over S, i.e., X S , we define X’s prefix-closure as X = f 1 2 S j9 22S ( 1 2 2 X)g. Let X S , X is prefix-closed if X = X. Let X S and let BX : X ! N be a bag, we define BX ’s prefix closure as BX : X ! N BX ( ) = B( ) +
X hei2X
BX ( hei) Thus, for set X1 = fha; bi; ha; cig we have X1 = f ; hai; ha; bi; ha; cig whereas for bag B2 = [ha; bi5; ha; ci3] we have B2 = [ 8; a 8 h i ; ha; bi5; ha; ci3].
Let S be a set on which we can pose some total order and let R R be a range of values. Vectors are denoted as ~z 2 RjSj, where ~z(e) 2 R and e 2 S. A vector ~z represents a column vector. For vector multiplication we assume vectors to agree on their indices. Thus, given a totally ordered set S = fe1; e2; :::; eng and ~z1; ~z2 2 RjSj we have ~z1|~z2 = Pi2f1;2;:::;ng ~z1(ei)~z2(ei). Parikh vectors represent the number of occurrences of a certain element within a sequence. A Parikh vector is a function p~ : S ! NjSj with p~( ) = ( e1 ; e2 ; :::; en ) where ei = jfj j 1 j j j; (j) = eigj. As an example consider S = fa; b; c; dg, 1 = ha; b; di and 2 = ha; c; di. We have p~( 1)| = (1; 1; 0; 1) and p~( 2)| = (1; 0; 1; 1). Note that 1 b = 1 whereas 2 b = 0. Given a Parikh vector p~ : S ! NjSj and a set Q S, we define p~Q : S ! NjQj. Thus given S = fa; b; c; dg and 1 = ha; b; di we have p~fa;c;dg( 1)| = (1; 0; 1). 2.2
The main goal of process discovery is to describe the observed behavior within an event log by means of a process model. Thus, event logs act as the input of process discovery whereas some process model acts as the output of process discovery. An abstract example of an event log is presented in Table 1. Often more data attributes are available in an event log, e.g., customer id, credit balance etc. In this paper we focus on the sequential ordering of activities w.r.t. cases, i.e. the control-flow perspective. Definition 1 (Event log). Let A be a set of activities, an event log L is a bag of sequences over A, i.e., L : A ! N.1 A sequence of activities 2 L is referred to as a trace. We assume that any given set of activities A is totally ordered (or we are able to trivially pose a total ordering on A).
We consider Petri nets to describe process models. A Petri net is a bipartite graph consisting of a set of vertices called places and a set of vertices called transitions. Arcs (directed edges) are connecting places and transitions and have an associated positive weight.
Definition 2 (Petri net). A Petri net is a 3-tuple N = (P; T; W ), where P is a set of places and T is a set of transitions with P \ T = ;. W is the weighted flow relation of N , W : (P T ) [ (T P ) ! N.
For a given node x 2 P [ T , the pre-set of x in N is defined as x = fy j W (y; x) > 0g. Correspondingly x = fy j W (x; y) > 0g denotes the post-set of x in N . Graphically we represent places as circles and transitions as boxes. For every (x; y) 2 (P T ) [ (T P ) with W (x; y) > 0 we draw an arc from x to y. If W (x; y) > 1
1In practice we extract an event log L from some information system. Consequently A is implicitly defined by the event log, i.e., A only consists of events that are actually present L. we denote the arc’s weight W (x; y) on top of the arc from x to y. A Petri net is pure if it does not contain self-loops, i.e., if W (x; y) > 0 then W (y; x) = 0. An example (pure) Petri net is depicted in Figure 1.
Definition 3 (Marked Petri net). Let N = (P; T; W ) be a Petri net. A marking of N is a bag over N ’s places, i.e. M : P ! N. A marked Petri net is a pair (N; M0), where M0 represents N ’s initial marking.
Let N = (P; T; W ) be a Petri net and let M be a marking of N . A transition t 2 T is enabled, denoted (N; M )[ti, if and only if 8p2 t(M (p) W (p; t)). Graphically we represent a marking by drawing exactly a place’s marking-multiplicity number of dots inside the place (e.g. p1 in Figure 1 with M0 = [p1]). If a transition t is enabled in (N; M ), t may fire, resulting in a new marking M 0. When t fires, denoted as (N; M )[ti(N; M 0), we have 8p2P (M 0(p) = M (p) W (p; t) + W (t; p)). For example in Figure 1 we have (N1; [p1])[ai(N1; [p2]).
Definition 4 (Firing sequences). Let N = (P; T; W ) be a Petri net and let (N; M0) be a corresponding marked Petri net. Sequence = ht1; t2; :::; tni 2 T is a firing sequence of (N; M0), written as (N; M0)[ i(N; Mn) if and only if for n = j j there exist markings M0; M1; M2; :::; Mn such that (N; M0)[t1i(N; M1), (N; M1)[t2i(N; M2); :::; (N; Mn 1)[tni(N; Mn).
Note that infinitely many firing sequences can exist given a Petri net. Some example firing sequences of the Petri net depicted in Figure 1 are: (N1; [p1])[haii(N1; [p2]), (N1; [p1])[ha; bii(N1; [p3]) and (N1; [p1])[ha; c; d; e; f; e; f; e; gii(N1; ;). The set of all possible firing sequences in a Petri net N is called N 0s language, i.e., all sequences 2 T s.t. (N; M0)[ i(N; Mi). N ’s language is denoted as L(N ) T and is prefixclosed.
Consider Figure 1 and event log L1 = [ha; b; d; e; gi10; ha; c; d; e; gi9; ha; b; d; e; f; e; gi11; ha; c; d; e; f; e; gi8] over A1 = fa; b; c; d; e; f; gg. Clearly we have L1 L(N1), and thus replay-fitness of L1 on N1 is perfect. We will use N1, A1 and L1 throughout the paper as a running-example. 3
The concept of regions forms the basis of region theory within Petri net synthesis. Given an event log L over a set of activities A, language-based regions are used to represent a p1 p2
d p3 p4 p5
g b c e f places in a resulting Petri net N = (P; A; W ). A language-based region maps every a 2 A to an integer representing arc-weight. For such mapping over A to be a region we pose the restriction that the corresponding place p 2 P should not block any 2 L, i.e., 2 L ) 2 L(N ). We identify two basic definitions of language-based regions which we classify as single variable-based regions and dual variable-based regions. The main difference is the number of variables used to define a region.
tivities A. Let m 2 N and let ~v 2 ZjAj. A pair r = (m; ~v) is a single variable-based region iff: 8 2L(m + p~( )|~v 0) (3.1) Let Rs(L) denote the set of all possible single variable-based regions of L. Equation 3.1 generates a set of linear inequalities, i.e. applying Equation 3.1 on L1 yields: m m + ~v(a) m + ~v(a) + ~v(b)
... m + ~v(a) + ~v(b) + ~v(d) + 2~v(e) + ~v(f) + ~v(g) m + ~v(a) + ~v(c) + ~v(d) + 2~v(e) + ~v(f) + ~v(g) ...
Single variable-based regions use one single decision variable for each a 2 A, represented by ~v 2 ZjAj. Expressing a single variable-based region r = (m; ~v) as a place p 2 P in a marked net (N; M0) with N = (P; A; W ) is straightforward. We have M0(p) = m, if ~v(a) > 0 then W (a; p) = ~v(a), if ~v(a) < 0 then W (p; a) = ~v(a) and if ~v(a) = 0 then W (a; p) = W (p; a) = 0. Consider place p2 depicted in Figure 1 which can be represented as a single variable-based region r = (m; (~v(a); ~v(b); :::; ~v(g))) = (0; (1; 1; 1; 0; 0; 0; 0)). Note that for each inequality generated by Equation 3.1, place p2 has a value of at least 0 and hence is a member of Rs(L).
Single variable-based regions only allow us to synthesize/discover pure Petri nets.
As a consequence we can not find self-loops, i.e. we can not find a place p in a resulting
net N = (P; A; W ) s.t. p 2 a\a , for any a 2 A. A lot of workflow patterns [
Definition 6 (Dual variable-based regions). Let L be an event log over a set of activities A. Let m 2 N and ~x; ~y 2 NjAj. A triple r = (m; ~x; ~y) is a dual variable-based region iff: 8 = 0 hai2L(m + p~( 0)|~x p~( )|~y 0) (3.2) Let Rd(L) denote the set of all possible dual variable-based regions of L. Like Definition 5, Definition 6 generates a set of linear inequalities. Applying Definition 6 on L1 yields: m m y~(a) + ~x(a) y~(a) + ~x(a) y~(b) + ~x(b) y~(c) + ~x(c) 2y~(e) + 2~x(e) 2y~(e) + 2~x(e) y~(f) + ~x(f) y~(f) + ~x(f) y~(g) y~(g) ... 0 hai 0 ha; bi 0 ha; ci
... 0 ha; b; d; e; f; e; gi 0 ha; c; d; e; f; e; gi m m
m y~(a) y~(a) + ~x(a) y~(a) + ~x(a)
... y~(d) + ~x(d) y~(d) + ~x(d) y~(b) y~(c)
Dual variable-based regions use two decision variables per a 2 A, represented by ~x; ~y 2 NjAj. The variables allow us to distinguish between incoming arcs and outgoing arcs when translating regions to Petri nets. Expressing a dual variable-based region r = (m; ~x; ~y) as a place p 2 P in marked net (N; M0) with N = (P; A; W ) is again straightforward. We have M0(p) = m, W (a; p) = ~x(a) and W (p; a) = ~y(a). Again consider place p2 depicted in Figure 1 which can be represented as a dual variable-based region r = (m; (~x(a); ~x(b); :::; ~x(g)); (~y(a); ~y(b); :::; ~y(g))) = (0; (1; 0; 0; 0; 0; 0; 0); (0; 1; 1; 0; 0; 0; 0)). Verify that for each linear in-equality generated by Definition 6, place p2 has a value of at least 0 and hence is a member of Rd(L). 4
Using dual variable-based regions allows us to express non-pure places, i.e, self-loops, milestones etc. However, this type of regions uses roughly twice as many variables compared with single variable-based regions. To balance the number of variables used, though still enhance the possibility of finding non-pure Petri net structures, we introduce the new concept of hybrid regions, capturing both single and dual variable-based regions.
Definition 7 (Hybrid variable-based regions). Let L be an event log over a set of activities A. Let As; Ad A be two sets of activities with As [ Ad = A and As \ Ad = ;. Let m 2 N, ~v 2 ZjAsj and ~x; ~y 2 NjAdj. A quadruple r = (m; ~v; ~x; ~y) is a hybrid variable-based region iff: (4.1) (4.2) 8 = 0 hai2L(m + p~As ( )|~v + p~Ad ( 0)|~x Equation 4.2 does not equal Equation 3.1, however, as p~( ) = ~0 and m 2 N, the equations are equivalent in this context.
Note that the set of hybrid variable-based regions, i.e. the set of variable assignments that adhere to Definition 7 depends on the hybrid partition of A into As and Ad. Therefore, we let As act as a parameter for the set of feasible hybrid variable-based regions. Let RAhs (L) denote the set of all possible hybrid variable-based regions of L where As represent a hybrid partition of A. Note RAh(L) = Rs(L) and Rh(L) = Rd(L). Region ; r = (0; ~0; ~0; ~0) is deemed the trivial region.
All three language-based region definitions, i.e. single, dual and hybrid variablebased regions, provide means to accept and/or reject potential places in a to be constructed Petri net. In classical Petri net synthesis approaches, one keeps looking for feasible places until either L = L(N ), or if this is impossible, L(N ) n L is minimized. Unfortunately, most models returned by classical Petri net synthesis techniques result in models that are unusable from a process discovery perspective. Hence, we need to relax the strict formal requirements posed on the relation between L and L(N ).
an event log over a set of activities A and let As; Ad A be a hybrid partition. Let Ms; Md; M0d be three matrices where Ms is an jLj n f g As matrix with Ms( ; a) = p~( )(a) and Md, M0d are two jLj n f g Ad matrices with Md( ; a) = p~( )(a) and M0d( ; a) = p~( 0)(a) (where = 0 ha0i 2 L). Let cm 2 R, c~v 2 RjAsj and c~x; c~y 2 RjAdj. The hybrid variable-based process discovery ILP-formulation, denoted ILPLh, is defined as: minimize z = cmm + c~v|~v + c~x|~x + c~y|~y objective function such that m~1 + Ms~v + M0d~x Md~y ~0 hybrid variable-based region and ~1 ~v ~1 i.e. ~v 2 f 1; 0; 1gjAsj ~0 ~x ~1 i.e. ~x 2 f0; 1gjAdj ~0 ~y ~1 i.e. ~y 2 f0; 1gjAdj 0 m 1 i.e. m 2 f0; 1g
The ILP-fromulation presented in Definition 8 uses the set of linear in-equalities
generated by Equation 4.1 within its constraint body. The formulation however binds
~v to f 1; 0; 1gjAsj and ~x; ~y to f0; 1gjAdj, i.e. the formulation only allows for
discovering Petri nets with arc weights restricted to f0; 1g. Additionally it defines an objective
function, i.e. z = cmm + c~v|~v + c~x|~x + c~y|~y, that maps each region to a real value,
i.e. z : RAhs (L) ! R. In general we are free to choose whatever objective function
we like, however, using different objective functions will lead to different process
discovery results. Choosing cm = 0 and ~cv = ~cx = ~cy = ~1 leads to arc minimization
whereas maximizing the same objective leads to arc maximization, resulting in
different places/regions found by the underlying ILP solver. The objective function proposed
in [
X(m + p~As ( )|~v + p~Ad ( )|(~x ~y)) (4.3) 2L 4.1
The objective function used within [
To relate the behavior in a given event log to the objective function defined in Definition 9 we instantiate the scaling function making use of the frequencies of the traces present in the event log, i.e. we let ( ) = L( ) leading to: zL(r) = X L( )(m + p~As ( )|~v + p~Ad ( )|(~x ~y)) (4.5)
To assess the difference between z1 and the newly proposed objective function zL, consider the Petri net depicted in Figure 2. Assume we are given some event log L = [ha; b; di5; ha; c; di3]. Let r1 denote the hybrid variable-based region corresponding to place p1, let r2 correspond to p2 and let r3 correspond to p3. In this case we have z1(r1) = 1, z1(r2) = 1 and z1(r3) = 2. On the other hand we have zL(r1) = zL(r2) = zL(r3) = 5 + 3 = 8. Thus, using z L leads to more intuitive objective values compared to using z1 as zL evaluates to the absolute number of discrete time-steps a token would remain in the corresponding place when replaying log L w.r.t. the place.
In [
2L 2L Fig. 2: A simple Petri net N with L(N ) = f ; hai; ha; bi; ha; ciha; b; di; ha; c; dig. X 2L X 2L
log over a set of activities A and let As; Ad A be a hybrid partition. Let r1 = (m1; ~v1; ~x1; ~y1), r2 = (m2; ~v2; ~x2; ~y2) and r3 = (m1 +m2; ~v1 +~v2; ~x1 +~x2; ~y1 +~y2) with r1; r2; r3 2 RAhs (L). Let z : RAhs (L) ! R where z is an instantiation of the generalized weighted objective function as defined in Definition 9, then z (r3) = z (r1) + z (r2). Proof (By definition of z ). Let us denote z (r3): ( )((m1 + m2) + p~As ( )|(v~1 + v~2) + p~Ad ( )|((x~1 + x~2) (y~1 + y~2))) ( )(m1 +p~As ( )|v~1 +p~Ad ( )|(x~1 y~1)+m2 +p~As ( )|v~2 +p~Ad ( )|(x~2 y~2)) ( )(m1 + p~As ( )|v~1 + p~Ad ( )|(x~1
y~1)) + ( )(m2 + p~As ( )|v~2 + p~Ad ( )|(x~2 y~2)) (4.6) (4.7) (4.8)
0: (4.9) Clearly z (r3) = z (r1) + z (r2).
Lemma 1 shows that the value of z for a non-minimal region equals the sum of the z values of the two regions it is composed of. If we additionally show that z can only evaluate to positive values, we show that z favors minimal hybrid variable-based regions.
ities A and let As; Ad A be a hybrid partition. Let r = (m; ~v; ~x; ~y) be a non-trivial region, i.e., r 2 RAhs (L). If we let z be any instantiation of the generalized weighted objective function as defined in Definition 9, then z : RAhs (L) ! R+. Proof (By showing z (r) > 0; 8r 2 RAhs (L)). Let r = (m; ~v; ~x; ~y) be a non-trivial hybrid variable-based region, i.e. r 2 RAhs (L). Because r 2 RAhs (L) we have 8 = 0 hai2Lnf g(m + p~As ( )|~v + p~Ad ( 0)|~x Using Equation 4.7 we can substitute p~Ad ( 0)|~x with p~Ad ( )|~x in Equation 4.6: 8 = 0 hai2Lnf g(m + p~As ( )|~v + p~Ad ( )|(~x ~y) 0) Combining rng( )
R+, p~( ) = ~0 and m 2 N with Equation 4.8 we find z (r) X 2L X 2L X 2L ( )(m + p~As ( )|~v + p~Ad ( )|(~x ~y))
0 If m > 0 then ( )(m+p~As ( )|~v+p~Ad ( )|(~x ~y)) > 0. Combined with Equations 4.8 and 4.9 leads to z (r) > 0.
Observe that if m = 0 then for r to be a non-trivial hybrid variable-based region, i.e. r 2 RAhs (L), either (I). 9a 2 As s.t. ~v(a) > 0 or (II). 9a 2 Ad s.t. ~x(a) > 0.
(I). Let m = 0 and a 2 As s.t. ~v(a) > 0. We know 9 = 0 hai 2 L. Because r 2 RAhs (L) (using Equation 4.8) we have: m + p~As ( )|~v + p~Ad ( )|(~x ~y) 0 If 0 = , we have p~Ad ( ) = ~0 and p~As ( )|~v = ~v(a) hence we deduce: m + p~As ( )|~v + p~Ad ( )|(~x ~y) > 0 Combining this with Equations 4.8 and 4.9 yields z (r) > 0.
If 0 6= we have (using Equation 4.8): m + p~As ( 0)|~v + p~Ad ( 0)|(~x ~y) 0 Observe that p~As ( )|~v = p~As ( 0)|~v + ~v(a), together with p~Ad ( 0) = p~Ad ( ) leads us to reformulate this to: m + p~As ( )|~v
~v(a) + p~Ad ( )|(~x m + p~As ( )|~v + p~Ad ( )|(~x ~y) ~y) ~v(a) Combining this with Equations 4.8 and 4.9 yields z (r) > 0.
(II) Let m = 0 and a 2 Ad s.t. ~x(a) > 0. We know 9 r 2 RAhs (L) (using Equation 4.6) we have: = 0 hai 2 L. Because m + p~As ( )|~v + p~Ad ( 0)|~x Observe that p~Ad ( )|~x = p~Ad ( 0)|~x + ~x(a) and thus: m + p~As ( )|~v + p~Ad ( )|(~x ~y) ~x(a) Combining this with Equations 4.8 and 4.9 yields z (r) > 0.
By combining Lemma 1 and Lemma 2 we can easily show that any instantiation of z favors minimal regions.
over a set of activities A and let As; Ad A be a hybrid partition. Let r1 = (m1; ~v1; ~x1; ~y1), r2 = (m2; ~v2; ~x2; ~y2) and r3 = (m1 + m2; ~v1 + ~v2; ~x1 + ~x2; ~y1 + ~y2) be three non-trivial regions, i.e., r1; r2; r3 2 RAhs (L). For any z : RAhs (L) ! R being an instantiation of the generalized weighted objective function as defined in Definition 9: z (r3) > z (r1) and z (r3) > z (r2).
Proof (By composition of Lemma 1 and Lemma 2). By Lemma 1 we know z (r3) = z (r1) + z (r2). By Lemma 2 we know that z (r1) > 0, z (r2) > 0 and z (r3) > 0. Thus we deduce z (r3) > z (r1) and z (r3) > z (r2). Consequently, any instantiation of the objective function as defined in Definition 9 favors minimal regions. 0 0 Both objective functions presented, i.e.z1 and zL, are expressible in terms of the more general objective function z as presented in Definition 9. As we have seen the two objective functions may favors different regions. Combining an objective function with the ILP-formulation presented in Definition 8 establishes means to find Petri net places. However, solving one ILP only yields one solution and hence we need means to find a set of places, which together form a Petri net that represents the input event log L. The most apparent technique to find multiple places is the use of causal relations within an event log. Within the context of this paper we define a causal relation as follows. Definition 10 (Causal relation). Let L be an event log over a set of activities A. A causal relation L is a function L : A A ! R where L(a; b) denotes the causality between activity a and b exhibited in L.
Several approaches exist to compute causalities hence we refer to [
L(a; b) can have different meanings w.r.t. the causality between a and b. Some approaches limit rng( L) to f0; 1g where L(a; b) = 1 means that there is a causal relation between a and b whereas L((a; b)) = 0 means there is no causal relation from a to b. Other approaches map rng( L) to the real-valued domain ( 1; 1) where a high positive L(a; b) value (close to 1) indicates a strong causal relation from a to b and a low negative value (close to 1) indicates a strong causal relation from b to a.
When adopting a causal-based ILP process discovery strategy, we try to find places which will be added in the resulting Petri net, each representing a causality found. A first step is to compute L values given some causal definition. Depending on the actual meaning of the L, whenever we find a causal relation from a to b (possibly because
L(a; b) , where is some threshold value), we enrich the constraint body for the given causal constraint as follows:
m = 0 and ~v(a) = 1 and ~v(b) = m = 0 and ~x(a) = 1 and ~v(b) = m = 0 and ~v(a) = 1 and ~y(b) = 1; if a 2 As; b 2 Ad m = 0 and ~x(a) = 1 and ~y(b) = 1; if a; b 2 Ad
1; if a; b 2 As 1; if a 2 Ad; b 2 As After the constraint body is enriched, we solve the ILP yielding a place having an optimal value for the specific objective function chosen. We repeat the procedure for every causal relation yielding a Petri net. 5
The hybrid variable-based ILP-formulation is implemented as a plug-in in the
ProMFramework (http://www.promtools.org) [
To test the performance of hybrid variable-based ILP process discovery we have used the basic implementation within an experimentation framework3. The framework allows for generating random process models and from these models generate event logs. We have generated 40 models containing a minimum of 2 activities and a maximum of 12 activities. For each model we have generated 10 event logs, each containing 5000 traces. For each log we ran three different instantiations of the process discovery formulation, one purely single variable-based, one hybrid variant and one purely dual variable-based. The distribution of event classes in A over As and Ad is depicted in Table 2. For the hybrid variant the size of As was kept constant and independent of the number of activities in A (as of jAj 3). We ran each instantiation 10 times per log using causal relations as a process discovery strategy. For each run of an instantiation we calculated the total time spend in solving all ILPs based on the causalities present in the event log. These times have been aggregated based on the number of activities present in an event log. The results of the experiment, plotted on a logarithmic scale, are depicted in Figure 34.
As shown in Figure 3, the average time to solve the hybrid formulation is in-between the single and dual formulation. We additionally note the hybrid formulation to get slightly closer to the dual formulation when jAj increases. This is as expected as the number of single variables within the hybrid formulation is constant and hence the average time of solving the ILPs within the formulation increases with respect to the single variable formulation. Figure 3 shows that reducing the number of variables used within the ILP-formulation has an impact on the average time of solving ILPs. The differences are however marginal, which is to be expected as solving ILPs is exponential by nature. Therefore the experiments show that using ILPs for the aim of process discovery in 3All framework files and results can be found at https://svn.win.tue.nl/repos/ prom/Packages/HybridILPMiner/Tags/papers/source_files/hybrid_ ilp_runtime_experiments.tar.gz
4The experiments where distributed over four servers (Dell PowerEdge R520, Intel Xeon E52407 v2 2.40GHz, 10M Cache, 8 8GB RDIMM, 1600MT/s Memory), on each server a total of 10 models and corresponding logs where generated. jAj 8 9 a practical setting might need incorporation of more advanced techniques in order to reduce the average time of solving the ILPs significantly. 6
The concept of hybrid variable-based regions originates from language-based region
theory, which in turn originates from the area of Petri net synthesis. We identify two
main branches of language-based region theory within Petri net synthesis being the
separating regions approach [
In [
An alternative approach is to use the concept of state-based regions for the purpose
of process discovery [
In [
A multitude of other Petri net-based process discovery approaches exist. For a
detailed description of these approaches we refer to [
We presented a new breed of language-based regions, i.e. hybrid variable-based regions, that captures the two existing region types being single and dual variable-based regions. Hybrid variable-based regions allow us to decide whether we want to use one or two variables for an activity present in the input event log. This allows us to achieve gains in terms of performance whilst maintaining the possibility to find complex (workflow) patterns. We have shown that within the hybrid variable-based ILP process discovery formulation, using only one variable per activity a 2 A performs optimal in terms of the average time spent in solving the ILPs constructed.
We presented a generalized weighted objective function and showed that any instantiation of the objective function leads to ILPs that favor minimal regions. As a result, practitioners may vary the scaling function within the objective function under the guarantee that the objective function favors minimal regions. We presented a logbased scaling function that exploits trace frequencies available in the input log. Using the log based scaling function within the objective function assigns an objective value to each region equal to the token throughput of the corresponding place, given the event log. Hence, as we have shown using the new objective function leads to more intuitive objective values.
As an interesting direction for future work we identify the assessment of the impact
of filtering, either a-priori or within the ILP itself, on the quality dimensions of the
resulting nets, i.e. are we able to leverage the perfect repaly-fitness property? Also,
an assessment of the impact of decomposition techniques [