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

TB4 Mathematical Modeling I

14 mai 2019 10h30 – 12h10

Salle: Gérard-Parizeau

Présidée par Bernard Gendron

4 présentations

  • 10h30 - 10h55

    Élimination du treillis engendré par les contraintes d'égalité d'un problème d'optimisation linéaire en nombre entier par la construction d'un problème-nain.

    • Stéphane Rouillon, prés., UdeM (IVADO)

    La technique présentée consiste à traiter initialement les contraintes d'égalité d'un problème d'optimisation linéaire afin de construire un "problème-nain". Celui-ci peut ensuite être résolu par les méthodes classiques ou par des heuristiques adaptées à la nouvelle structure. Mots-clés: contraintes d'égalité, treillis, problème-nain, nombre entier.

  • 10h55 - 11h20

    Integer and constraint programming approaches to the discretizable molecular distance geometry problem

    • Moira MacNeil, prés., University of Toronto
    • Merve Bodur, University of Toronto

    We present the first Constraint Programming (CP) formulations for the Discretizable Molecular Distance Geometry Problem. We present infeasibility checks, symmetry breaking constraints, and domain reduction strategies for the CP models. Computational experiments show CP outperforms existing integer programming formulations, especially on large instances.

    Keywords: constraint programming, distance geometry problem, vertex order

  • 11h20 - 11h45

    Piecewise linear approximation with a performance guarantee for solving MINLPs

    • Julien Codsi, prés., Université de Montréal
    • Sandra Ulrich Ngueveu, LAAS-CNRS / Université de Toulouse - INPT
    • Bernard Gendron, Université de Montréal, CIRRELT

    We present an efficient algorithm that approximates any arbitrary univariate non linear function by a piecewise linear function with a guaranteed relative epsilon-tolerance. Using this algorithm, we show how to approximate as a MILP with a guaranteed relative gap, any MINLP with separable non linear terms in the objective function.
    Computational results on a congested multicommodity network design problem will be presented.

  • 11h45 - 12h10

    Arc-based MILP reformulations of a flow capture bi-level program

    • Léonard Ryo Morin, prés., Université de Montréal
    • Bernard Gendron, Université de Montréal, CIRRELT
    • Emma Frejinger, DIRO and CIRRELT

    We discuss a traffic control application where a transportation network manager allocates traffic flow controlling resources. Traffic flows can be antagonistic or cooperative. We present a bi-level programming formulation with an arc-based random utility model that we reformulate in several mixed integer linear programs which we then compare.

Retour