Discovering workflow nets using integer linear programming

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
68 Downloads (Pure)

Abstract

Process mining is concerned with the analysis, understanding and improvement of business processes. Process discovery, i.e. discovering a process model based on an event log, is considered the most challenging process mining task. State-of-the-art process discovery algorithms only discover local control flow patterns and are unable to discover complex, non-local patterns. Region theory based techniques, i.e. an established class of process discovery techniques, do allow for discovering such patterns. However, applying region theory directly results in complex, overfitting models, which is less desirable. Moreover, region theory does not cope with guarantees provided by state-of-the-art process discovery algorithms, both w.r.t. structural and behavioural properties of the discovered process models. In this paper we present an ILP-based process discovery approach, based on region theory, that guarantees to discover relaxed sound workflow nets. Moreover, we devise a filtering algorithm, based on the internal working of the ILP-formulation, that is able to cope with the presence of infrequent, exceptional behaviour. We have extensively evaluated the technique using different event logs with different levels of exceptional behaviour. Our experiments show that the presented approach allows us to leverage the inherent shortcomings of existing region-based approaches. The techniques presented are implemented and readily available in the HybridILPMiner package in the open-source process mining tool-kits ProM (http://promtools.org) and RapidProM (http://rapidprom.org).
Original languageEnglish
Pages (from-to)529-556
JournalComputing
Volume100
Issue number5
DOIs
Publication statusPublished - May 2018

Fingerprint

Integer Linear Programming
Linear programming
Work Flow
Inductive logic programming (ILP)
Process Mining
Process Model
Flow patterns
Acoustic waves
Overfitting
Flow Pattern
Business Process
Leverage
Open Source
Filtering
Industry
Model-based
Internal
Experiments
Formulation
Experiment

Cite this

@article{3d59e696da0645fcbea68bebca0fed90,
title = "Discovering workflow nets using integer linear programming",
abstract = "Process mining is concerned with the analysis, understanding and improvement of business processes. Process discovery, i.e. discovering a process model based on an event log, is considered the most challenging process mining task. State-of-the-art process discovery algorithms only discover local control flow patterns and are unable to discover complex, non-local patterns. Region theory based techniques, i.e. an established class of process discovery techniques, do allow for discovering such patterns. However, applying region theory directly results in complex, overfitting models, which is less desirable. Moreover, region theory does not cope with guarantees provided by state-of-the-art process discovery algorithms, both w.r.t. structural and behavioural properties of the discovered process models. In this paper we present an ILP-based process discovery approach, based on region theory, that guarantees to discover relaxed sound workflow nets. Moreover, we devise a filtering algorithm, based on the internal working of the ILP-formulation, that is able to cope with the presence of infrequent, exceptional behaviour. We have extensively evaluated the technique using different event logs with different levels of exceptional behaviour. Our experiments show that the presented approach allows us to leverage the inherent shortcomings of existing region-based approaches. The techniques presented are implemented and readily available in the HybridILPMiner package in the open-source process mining tool-kits ProM (http://promtools.org) and RapidProM (http://rapidprom.org).",
author = "{van Zelst}, S.J. and {van Dongen}, B.F. and {van der Aalst}, W.M.P. and H.M.W. Verbeek",
year = "2018",
month = "5",
doi = "10.1007/s00607-017-0582-5",
language = "English",
volume = "100",
pages = "529--556",
journal = "Computing",
issn = "0010-485X",
publisher = "Springer",
number = "5",

}

Discovering workflow nets using integer linear programming. / van Zelst, S.J.; van Dongen, B.F.; van der Aalst, W.M.P.; Verbeek, H.M.W.

In: Computing, Vol. 100, No. 5, 05.2018, p. 529-556.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Discovering workflow nets using integer linear programming

AU - van Zelst, S.J.

AU - van Dongen, B.F.

AU - van der Aalst, W.M.P.

AU - Verbeek, H.M.W.

PY - 2018/5

Y1 - 2018/5

N2 - Process mining is concerned with the analysis, understanding and improvement of business processes. Process discovery, i.e. discovering a process model based on an event log, is considered the most challenging process mining task. State-of-the-art process discovery algorithms only discover local control flow patterns and are unable to discover complex, non-local patterns. Region theory based techniques, i.e. an established class of process discovery techniques, do allow for discovering such patterns. However, applying region theory directly results in complex, overfitting models, which is less desirable. Moreover, region theory does not cope with guarantees provided by state-of-the-art process discovery algorithms, both w.r.t. structural and behavioural properties of the discovered process models. In this paper we present an ILP-based process discovery approach, based on region theory, that guarantees to discover relaxed sound workflow nets. Moreover, we devise a filtering algorithm, based on the internal working of the ILP-formulation, that is able to cope with the presence of infrequent, exceptional behaviour. We have extensively evaluated the technique using different event logs with different levels of exceptional behaviour. Our experiments show that the presented approach allows us to leverage the inherent shortcomings of existing region-based approaches. The techniques presented are implemented and readily available in the HybridILPMiner package in the open-source process mining tool-kits ProM (http://promtools.org) and RapidProM (http://rapidprom.org).

AB - Process mining is concerned with the analysis, understanding and improvement of business processes. Process discovery, i.e. discovering a process model based on an event log, is considered the most challenging process mining task. State-of-the-art process discovery algorithms only discover local control flow patterns and are unable to discover complex, non-local patterns. Region theory based techniques, i.e. an established class of process discovery techniques, do allow for discovering such patterns. However, applying region theory directly results in complex, overfitting models, which is less desirable. Moreover, region theory does not cope with guarantees provided by state-of-the-art process discovery algorithms, both w.r.t. structural and behavioural properties of the discovered process models. In this paper we present an ILP-based process discovery approach, based on region theory, that guarantees to discover relaxed sound workflow nets. Moreover, we devise a filtering algorithm, based on the internal working of the ILP-formulation, that is able to cope with the presence of infrequent, exceptional behaviour. We have extensively evaluated the technique using different event logs with different levels of exceptional behaviour. Our experiments show that the presented approach allows us to leverage the inherent shortcomings of existing region-based approaches. The techniques presented are implemented and readily available in the HybridILPMiner package in the open-source process mining tool-kits ProM (http://promtools.org) and RapidProM (http://rapidprom.org).

U2 - 10.1007/s00607-017-0582-5

DO - 10.1007/s00607-017-0582-5

M3 - Article

VL - 100

SP - 529

EP - 556

JO - Computing

JF - Computing

SN - 0010-485X

IS - 5

ER -