Journées de l'optimisation 2019

HEC Montréal, 13-15 mai 2019

JOPT2019

HEC Montréal, 13 — 15 mai 2019

Horaire Auteurs Mon horaire

WA9 Mathematics and Graphs

15 mai 2019 09h00 – 10h15

Salle: TD Assurance Meloche Monnex

Présidée par Marcus Poggi

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.

Retour