Compu ing Alignmen s wi h Cons ain
P og amming: The Acyclic Case
Ma ´ıa Te esa G´omez-L´opez1, Diana Bo ego1, Josep Ca mona2, Ra ael M.
Gasca1
1Uni e sidad de Se illa, Se ille, Spain,
{may egomez,dianabn,gasca}@us.es
2Uni e si a Poli `ecnica de Ca alunya, Ba celona, Spain,
[email p o ec ed]
Abs ac . Con o mance checking con on s p ocess models wi h eal
p ocess execu ions o de ec and measu e de ia ions be ween modelled
and obse ed beha iou . The co e echnique o con o mance checking
is he compu a ion o an alignmen . Cu en app oaches o alignmen
compu a ion ely on a sho es -pa h echnique o e he p oduc o he
s a e-space o a model and he obse ed ace, hus suffe ing om he
well-known s a e explosion p oblem. This pape p esen s a esh al e na-
i e o alignmen compu a ion o acyclic p ocess models, ha encodes
he alignmen p oblem as a Cons ain Sa is ac ion P oblem. Since mod-
e n sol e s o his amewo k a e capable o dealing wi h la ge ins ances,
his con ibu ion has a clea po en ial. Rema kably, ou p o o ype imple-
men a ion can handle ins ances ha ep esen a eal challenge o cu en
echniques. Main ad an ages o using Cons ain P og amming pa adigm
lie in he possibili y o adap pa ame e s such as he maximum sea ch
ime, o he maximum misalignmen allowed. Mo eo e , using sea ch and
p opaga ion algo i hms inco po a ed in Cons ain P og amming Sol e s
pe mi s o find solu ions o p oblems unsol able wi h o he echniques.
Keywo ds: Con o mance Checking, Cons ain P og amming
1 In oduc ion
Nowadays o ganiza ions analyze and use he huge amoun o da a ha hei
in o ma ion sys ems gene a e. This da a ep esen s an impo an sou ce o in-
o ma ion, since i con ains many o he e idences an o ganiza ion may need o
know in o de o each i s (business) goals. Among o he s pe spec i es, he ocus
on he p ocess dimension is o pa amoun impo ance.
P ocess mining has e ol ed in he las decade o ac as a mee ing poin be-
ween da a and p ocess science. Techniques in p ocess mining enable he disco -
e y o e idence-based p ocess models, he con o mance analysis and he enhance-
men o p ocess models. Con o mance analysis, which is he opic conside ed in
his pape , s udies he adequacy o a p ocess model in desc ibing he eal beha -
io obse ed as a collec ion o aces deno ing he oo p in s o he execu ion o
96
a p ocess. While he e exis se e al echniques o disco e y and enhancemen
o p ocess models, he cu en ew echniques a ailable o con o mance analysis
a e no ye sa is ac o y.
In his pape we ackle a cen al p oblem in con o mance analysis: he com-
pu a ion o an alignmen be ween a p ocess model and an e en log. In o mally,
an alignmen is a wo- ow ma ix whe e he fi s ow deno es he s eps in he
obse ed ace, while he second ow desc ibes he s eps pe o med by he model
in o de o fi as much as possible he ace. Alignmen s a e c ucial o e alua e
he impo an me ics in con o mance, i.e., fi ness and gene aliza ion [2] and
p ecision [3].
We de ia e om he cu en app oaches o alignmen compu a ion, which
a e based on s a e-space explo a ions o models. Ins ead, we encode he p oblem
o compu ing alignmen s as a Cons ain Sa is ac ion P oblem (CSP), and use a
CSP sol e o compu e alignmen s. The CSP amewo k b ings many ad an ages
when compa ed o he s a e-o - he-a app oaches o con o mance analysis: a
po olio o a ailable sea ch echniques, na u al encoding o ce ain model con-
s uc s, capabili y o handling la ge ins ances, abili y o in e ac wi h he sol e
o ob ain alid solu ions, e c.
In his pape we conside he compu a ion o alignmen s o acyclic p o-
cess models. In spi e o his model es ic ion, cu en echniques may s ill ha e
p oblems o handle ce ain ins ances, as i was demons a ed in [14]. In ou
p o o ype implemen a ion, we show how he app oach p esen ed in his pape
may be a solid al e na i e when cu en app oaches ail a de i ing an alignmen .
This pape is o ganized as ollows: in Sec ion 2 a b ie in oduc ion o Con-
s ain P og amming is p o ided, since i is he basis o he encoding p esen ed
in he es o he pape . Then in Sec ion 3 he encoding is shown, oge he wi h
u he ex ensions o op imize he compu a ion o alignmen s. Then in Sec ion 4
some he esul s on some ins ances om he li e a u e a e epo ed. Finally,
Sec ion 6 p o ides he cu en con ex o con o mance analysis and Sec ion 7
concludes and discusses cu en esea ch di ec ions.
2 Cons ain P og amming
A CSP ep esen s a easoning amewo k consis ing o a iables, domains and
cons ain s, whe e he model is desc ibed decla a i ely. Fo mally, i is defined as
a uple X,D,C,whe eX={x1,...,xn}is a fini e se o a iables, D={d(x1),
...,d(xn)}is a se o domains o he alues o he a iables, and C={C1,...,
Cm}is a se o cons ain s. Each cons ain Ciis defined as a ela ion Ron a
subse o a iables V={xi,xj,...,xl}, called he cons ain scope.The ela ion
Rmay be ep esen ed as a subse o he Ca esian p oduc d(xi)×d(xj)×...
×d(xl). A cons ain Ci=(Vi,Ri) simul aneously specifies he possible alues
o he a iables in V ha sa is y R.Le Vk={xk1,...,xkl}be a subse o X,
and an l- uple (xk1,...,xkl) omd(xk1), ...,d(xkl) can he e o e be called an
97
ins an ia ion o he a iables in Vk. An ins an ia ion is a solu ion i and only i
i sa isfies he cons ain s C.
In o de o sol e a CSP, a combina ion o sea ch and consis ency echniques
is commonly used [8][4]. The consis ency echniques emo e inconsis en alues
om he domains o he a iables du ing o be o e he sea ch. Du ing he sea ch,
a p opaga ion p ocess is execu ed which analyses he combina ion o alues o
a iables whe e he cons ain s a e sa isfiable. Se e al local consis ency and op-
imiza ion echniques ha e been p oposed as ways o imp o ing he efficiency o
sea ch algo i hms.
When i is no only necessa y o asce ain i a solu ion can be ound, and i is
impo an o find he bes solu ion, a Cons ain Op imiza ion P oblem (COP)
can be c ea ed and sol ed. A COP is a CSP wi h an op imiza ion unc ion whe e
only he uple o possible alues ha op imize his unc ion is de e mined as he
solu ion o he COP. Cons ain P og amming has al eady been used o compa e
expec ed and obse ed beha iou o diagnose models acco ding obse a ions, and
i has also been applied o business p ocess models [9, 11, 5].
A simple example o illus a e he usage o a CSP can be ound o ep esen
he possible execu ion o de o he ac i i ies o a model. Imagine a model whe e
ac i i y A mus be execu ed fi s , and ac i i ies B o C mus be execu ed a e ,
bu no bo h. Va iables modA,modB,modCcan be used o ob ain he possible
execu ion momen s. And he cons ain s should ep esen ha (1) A mus be
execu ed, (2) B o C mus be execu ed (bu only one), and (3) i B o C a e
execu ed, his will happen a e he execu ion o A.
modA,modB,modCin he domain {0..n}//{0..model.size()}
modA>0 AND (modB>0XORmodC>0) AND
i (modB=0) hen (modB>modA)
i (modC=0) hen (modC>modA)
Wi h his CSP, some solu ions p o ided by a cons ain sol e would be:
sol1: modA=1, modB=2, modC=0
sol2: modA=1, modB=0, modC=2
sol3: modA=1, modB=3, modC=0
...
An example o op imiza ion unc ion can be o minimize(modA+modB+
modC). In his case only sol1 is ob ained.
3 Alignmen Compu a ion wi h Cons ain P og amming
In his pape we p opose o encode by means o a CSP he cons ain s ha de-
sc ibe he possible execu ion o de o he ansi ions in a Pe i ne ( he expec ed
beha iou ), and he o de o he ansi ion in he logs (obse ed beha iou ) ol-
lowing model-based diagnosis pa adigm [10]. The COP will find he minimum
misalignmen be ween he obse ed and he expec ed ansi ions. The encoding
consis s in he c ea ion o wo se s o a iables ha ep esen , espec i ely, he
98
Pe i ne model (se called Va -Model), and he eal obse ed beha iou eg-
is e ed in each case o he e en log (se called Va -Log). These wo se s ha e
he same numbe o a iables, since hey a e composed o all ac i i ies in he
model, plus all ac i i ies appea ing in he e en log bu no in he model. Fo he
alignmen compu a ion, he cons ain s ha ep esen he model a e de e mined
once, while he cons ain s ha ep esen he e en log depend on each case.
Conside ing all hese ac i i ies, hese wo se s o a iables ep esen he s ep
o de whe e each ac i i y ( ansi ion in he Pe i ne ) can be execu ed ollow-
ing he model (Va -Model) o in acco dance o he e en log (Va -Log ). I i is
possible o assign he same alue o e e y a iable in Va -Model and Va -Log,i
implies ha he e is a o al alignmen be ween he model and he eali y. This
way, in o de o model bo h sequences o ac i i ies (i.e. modelled and obse ed
beha iou ), each a iable is modelled as an in ege ha is e alua ed in acco -
dance wi h he posi ion ha i akes in he execu ion o de . Then, he posi ions
assigned o each ac i i y in he modelled (Va -Model) and expec ed (Va -Log )
beha iou s a e compa ed o de e mine whe he some e en wi hin a case in he
e en log is misaligned.
3.1 Modelling he Va iables o ep esen he Pe i Ne
As men ioned, he expec ed and obse ed occu ences o ac i i ies should be
modelled wi hin he CSP, so ha he modelled and obse ed sequences o exe-
cu ion o ac i i ies can be compa ed. The e o e, ce ain se s o a iables should
be pa o he CSP, wi h he ollowing meanings:
–Va -Model: Se o decision a iables {moda,modb,...,modn} ep esen ing
he posi ion ha all ac i i ies a,b,...,n ake in he expec ed execu ion o de ,
whose domains a e In ege s in 0..n,beingn he numbe o ansi ions plus
he log size -i.e. he wo s possible alue o alignmen -.
–Va -Log: Se o decision a iables {loga,logb,...,logn}, ep esen ing he s ep
o de o he ansi ions in he obse ed ace, and whose domains a e equal
o he a iables in Va -Model.
–Va -Diffe ence:Se o nin ege a iables {di a,di b,...,di n}, one o
each ansi ion, whose domains a e {0, 1, 2}, o ep esen ha : he e is
alignmen be ween he obse ed and expec ed beha iou o he ansi ion
(modx== logx→di x= 0); he ansi ion is in he modelled ace bu no
in he eal ace o ice e sa (modx== 0 XOR logx== 0 →di x=1);
o he ansi ion is in bo h aces bu in diffe en posi ions in he execu ion
o de (else →di x= 2). I holds whe he he e is alignmen be ween he
n- h alues o Va -Model and Va -Log.
–Va -Alignmen : In ege ha ep esen s he sum o all alues in Va -Diffe ence,
ep esen ing he wo s possible alue o alignmen . This alue is used in he
op imiza ion unc ion, since i his alue can be se o 0, i means ha he
model and he e en log a e o ally aligned.
In o de o acili a e a clea unde s anding o he c ea ed COP, we use he
example in Figu e 1 o show he model and solu ions ob ained.
99
Fig. 1. Simple Pe i Ne
3.2 Modelling he Cons ain s o ep esen he Pe i Ne
The COP mus include he fi e necessa y pa s: defini ion o a iables, con-
s ain s o ela e he o de o he ansi ions in he model, cons ain s o desc ibe
he o de o he log, cons ain s o de e mine he misalignmen o each ac i i y,
and he objec i e unc ion.
The modelling o he cons ain s in he COP is based on he ans o ma ion o
he Pe i ne model in o nume ical cons ain s. Fo his eason, e e y place (and
hence, he s uc u e o he flow su ounding i ) is analysed, and he ollowing
cons ain s a e included in o he COP o ep esen he con ol flow be ween he
ansi ions. To diffe en ia e he cons ain s ha o m he c ea ed COP, om
he p og amming s uc u es used o co e he Pe i ne o ob ain he ela ions
be ween he ansi ions, i alic le e s a e used o dis inguish cons ain s.
– S a place (i.e. place wi h no inpu a cs): Being o 1... o
m he ou -
pu ansi ions (as shown in Figu e 2), he ollowing cons ain is pa o he
COP:
(modo 1=0+... +modo m=0) =1
Fo he example:
(modA=0) = 1
– In e media e place (i.e. place wi h some inpu and ou pu a cs):
Being i 1...i
n he inpu ansi ions, and o 1...o
m he ou pu ansi ions
(as shown in Figu e 3), he ollowing cons ain s a e pa o he COP:
FOR EACH pai i i,o
j
i (modo j=0) hen (modo j>mod
i i)
END FOR
(modi 1=0+...+modi n=0) ≤1 AND (modo 1=0+...+modo m=0)
≤1
(modi 1=0+... +modi n=0) =(modo 1=0+... +modo m=0)
Fig. 2. S a place
100

Fig. 3. In e media e place
Meaning ha :
• o each ou pu ansi ion o j, ei he i is no pa o he execu ion,
o i should be execu ed a e he execu ed inpu ansi ion (modo j>
modi i);
•and, i an inpu ansi ion is execu ed, one and only one o he ou pu
ansi ions can be execu ed. O he wise, none o hem is execu ed.
Applied o he example:
//A→B//in e media e places
i (modB=0) hen (modB>modA)
(modA=0)≤1 AND (modB=0)≤1 AND (modA=0)=(modB=0)
// he modelling o B→D,D→E,E→I,A→C,H→Iis
equi alen
//C→(F xo G)
i (modF=0) hen (modF>modC)
i (modG=0) hen (modG>modC)
(modC=0)≤1 AND (modF=0 + modG=0)≤1
(modC=0)=(modF=0 + modG=0)
// he modelling o I→J xo K is equi alen
//(F xo G) →H
i (modH=0) hen (modH>modF)
i (modH=0) hen (modH>modG)
(modF=0 + modG=0)≤1 AND (modH=0)≤1
(modF=0 + modG=0)=(modH=0)
// he modelling o J xo K →Lis equi alen
– End place (i.e. place wi h no ou pu a cs): Being i 1... i
n he inpu
ansi ions (as shown in Figu e 4), he ollowing cons ain is pa o he
COP:
(modi 1=0+... +modi n=0) =1
Fig. 4. End place
101
Applied o he example:
(modL=0)=1
–E e y ansi ion aiappea ing in he case ( om he e en log) o check, bu
no in he model, is included as a a iable modaiin he se Va -Model,wi h
he cons ain :
modai=0
3.3 Modelling he Cons ain s o ep esen he E en Log
As i was a o emen ioned, he a iables in he se Va -Log a e c ea ed o s udy
he posi ions in he execu ion o de o bo h he elemen s appea ing in a ce ain
case and in he model. The e o e, diffe en se s a e c ea ed o each case in he
e en log, and hen a diffe en CSP is c ea ed o each case.
Fo e e y case in he e en log, composed o ac i i ies p esen ed as an o -
de ed lis a1,a
2,...,a
q, he cons ains ha should be c ea ed and included in
he COP a e:
loga1>0 AND loga2>log
a1AND ... AND logaq>log
aq−1
Meaning ha , since all e en s in he log we e execu ed, hey should ha e a
alue g ea e han 0, keeping he execu ion o de eco ded in he case.
Likewise, o each ac i i y aiappea ing in he model bu no in he log, he
ollowing cons ain is included:
logai=0
3.4 Modelling a COP o find he alignmen be ween model and
e en log
The alignmen can be desc ibed by he dis ance be ween he obse ed and he
expec ed beha iou . The obse ed ac i i y execu ions a e ep esen ed by he
a iables in he se Va -Log while he expec ed beha iou is modelled by he
se Va -Model. The minimiza ion o he diffe ence be ween hem is he aim o
he alignmen . In ou solu ion, i is modelled using he a iables in he se
Va -Diffe ence, whe e each a iable di ai ep esen s he diffe ence be ween he
expec ed and he obse ed beha iou o ac i i y ai(0, 1 o 2 as explained be-
o e). The sum o all a iables in he se Va -Diffe en is s o ed in he a iable
Va -Alignmen , which is he alue o minimize, objec i e o he op imiza ion
unc ion.
102
FOR EVERY ac i i y aiDO:
i (logai==modai) hen(di ai=0)
else i (logai==0 ∨modai==0) hen (di ai=1)
else (di ai=2)
END
Following he heo y o alignmen o p ohibi ha wo diffe en ac i i ies
can be execu ed in he same ins an o ime, he ollowing cons ain s mus be
included:
FOR EACH pai o a iables modiand logjin Va -Model DO:
i (modi=0) hen (modi=logj)
END
Finally, o include he objec i e unc ion ha minimize he summa ion o
diffe ences, he ollowing cons ain s a e included:
Va -Alignmen = di i∈Va −Di e ence di i
minimize(Va -Alignmen )
3.5 Some E alua ions o he example
Likewise, and depending on he case o check, he es o he COP is defined.
To illus a e his, h ee cases in he e en log, and hei esul ing cons ain s,
a e shown as examples in he ollowing:
–A fi ing case: {A, C, B, F, D, E, H, I, J, L}
//Ac i i ies in he case
logA>0 AND logC>logAAND
logB>logCAND logF>logBAND
logD>logFAND logE>logDAND
logH>logEAND logI>logHAND
logJ>logIAND logL>logJ
//Ac i i ies in he model bu no in he case
logG=0 AND logK=0
–Unfi ing case 1, since he e is an ac i i y in he model ha should appea
in he case (ac i i y l): {A, C, B, F, D, E, H, I, J}
//Ac i i ies in he case
logA>0 AND logC>logAAND
logB>logCAND logF>logBAND
logD>logFAND logE>logDAND
logH>logEAND logI>logHAND
logJ>logI
//Ac i i ies in he model bu no in he case
logL=0 AND logG=0 AND logK=0
103
–Unfi ing case 2, since he e is an ac i i y in he log ha does no appea in
a co ec ace o he model al hough i is in he model (o de o D and E):
{A, C, B, E, D, F, H, I, J, L}
//Ac i i ies in he case
logA>0 AND logC>logAAND
logB>logCAND logF>logBAND
logG>logFAND logD>logGAND
logE>logDAND logH>logEAND
logI>logHAND logJ>logIAND
logL>logJ
//Ac i i ies in he model bu no in he case
logK=0
The au oma ic compu a ion o hese h ee examples ob ains he esul ing
se s Va -Model,Va -Log,Va -Diffe ence and he alue o Va -Aligmen shown
in Figu e 5.
Fig. 5. Resul s o h ee case examples
104