Optimization Days 2019

HEC Montréal, May 13-15, 2019

JOPT2019

HEC Montréal, 13 — 15 May 2019

Schedule Authors My Schedule

TB4 Mathematical Modeling I

May 14, 2019 10:30 AM – 12:10 PM

Location: Gérard-Parizeau

Chaired by Bernard Gendron

4 Presentations

  • 10:30 AM - 10:55 AM

    É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, presenter, 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.

  • 10:55 AM - 11:20 AM

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

    • Moira MacNeil, presenter, 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

  • 11:20 AM - 11:45 AM

    Piecewise linear approximation with a performance guarantee for solving MINLPs

    • Julien Codsi, presenter, 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.

  • 11:45 AM - 12:10 PM

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

    • Léonard Ryo Morin, presenter, 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.

Back