09:00 AM - 09:25 AM
Merging combinatorial design and optimization: The Oberwolfach problem
The Oberwolfach Problem OP(F), posed by Gerhard Ringel in 1967, is a paradigmatic Combinatorial Design problem asking whether the complete graph K decomposes into edge disjoint copies of a 2-regular graph F of order v. In Combinatorial Design Theory, so-called difference methods represent a well-known solution technique and construct solutions in infinitely many cases exploiting symmetric and balanced structures. This approach reduces the problem to finding a well-structured 2-factor which allows us to build solutions that we call 1- or 2-rotational according to their symmetries. We tackle OP by modeling difference methods with Optimization tools, specifically Constraint Programming (CP) and Integer Programming (IP), and correspondingly solve instances with up to v=120 within 60s. In particular, we model the 2-rotational method by solving in cascade two subproblems, namely the binary and group labeling, respectively. A polynomial-time algorithm solves the binary labeling, while CP tackles the group labeling. Furthermore, we provide necessary conditions for the existence of some 1-rotational solutions which stem from computational results. This work shows thereby that both theoretical and empirical results may arise from the interaction between Combinatorial Design Theory and Operation Research.
09:25 AM - 09:50 AM
A decomposition approach to solve the selective graph coloring problem in perfect graphs
We study the The Selective Graph Coloring Problem, and present a decomposition-based solution approach to solve the problem in perfect graphs. We conduct computational experiments and compare our results to those of an integer programming formulation and a state-of-the-art branch-and-price algorithm from the literature.
Keywords: selective coloring, decomposition, perfect graphs
09:50 AM - 10:15 AM
Dealing with outliers in process discovery
Business process can be represented by Petri nets. Given its event log(set of sequences of activities), one wants to find corresponding net. A MIP formulates this synthesis. We show, on Process Discovery Contest instances, allowing a percentage of not enforced sequences leads to nets with increased precision, simpler, keeping high fitness.