Optimization Days 2019

HEC Montréal, May 13-15, 2019


HEC Montréal, May 13 — 15, 2019

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

WA9 Mathematics and Graphs

May 15, 2019 09:00 AM – 10:15 AM

Location: TD Assurance Meloche Monnex

Chaired by Marcus Poggi

3 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    09:00 AM - 09:25 AM

    Merging combinatorial design and optimization: The Oberwolfach problem

    • Fabio Salassa, Politecnico di Torino
    • Gabriele Dragotto, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    09:25 AM - 09:50 AM

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

    • Oylum Seker, presenter, 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

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    09:50 AM - 10:15 AM

    Dealing with outliers in process discovery

    • Marcus Poggi, presenter, 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.