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.