3 présentations

• 
  09h00 - 09h25

  Merging combinatorial design and optimization: The Oberwolfach problem

  • Fabio Salassa, Politecnico di Torino
  • Gabriele Dragotto, prés., Polytechnique Montreal
  • Tommaso Traetta, Università di Brescia
  • Marco Buratti, Università degli Studi di Perugia
  • Federico Della Croce, Politecnico di Torino

  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.
• 
  09h25 - 09h50

  A decomposition approach to solve the selective graph coloring problem in perfect graphs

  • Oylum Seker, prés., University of Toronto
  • Tinaz Ekim, Bogazici University
  • Z. Caner Taskin, Bogazici University

  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
• 
  09h50 - 10h15

  Dealing with outliers in process discovery

  • Marcus Poggi, prés., Pontifícia Universidade Católica do Rio de Janeiro
  • Georges Spyrides, PUC-RIo
  • Helio Lopes, PUC-Rio

  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.