  Heuristic-based methods are among the most popular methods in the process
discovery area. This category of methods is composed of two main steps: 1)
discovering a dependency graph 2) determining the split/join patterns of the
dependency graph. The current dependency graph discovery techniques of
heuristic-based methods select the initial set of graph arcs according to
dependency measures and then modify the set regarding some criteria. This can
lead to selecting the non-optimal set of arcs. Also, the modifications can
result in modeling rare behaviors and, consequently, low precision and
non-simple process models. Thus, constructing dependency graphs through
selecting the optimal set of arcs has a high potential for improving graphs
quality. Hence, this paper proposes a new integer linear programming model that
determines the optimal set of graph arcs regarding dependency measures.
Simultaneously, the proposed method can eliminate some other issues that the
existing methods cannot handle completely; i.e., even in the presence of loops,
it guarantees that all tasks are on a path from the initial to the final tasks.
This approach also allows utilizing domain knowledge by introducing appropriate
constraints, which can be a practical advantage in real-world problems. To
assess the results, we modified two existing methods of evaluating process
models to make them capable of measuring the quality of dependency graphs.
According to assessments, the outputs of the proposed method are superior to
the outputs of the most prominent dependency graph discovery methods in terms
of fitness, precision, and especially simplicity.
