Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

TB8 Optimisation discrète / Optimization Problems with Discrete Structure

8 mai 2012 10h30 – 12h10

Salle: Transat

Présidée par Miguel F. Anjos

4 présentations

  • 10h30 - 10h55

    The Width of 4-Prismatoids

    • Tamon Stephen, prés., Simon Fraser University

    Santos' recent construction of a counterexample to the Hirsch conjecture highlights a
    particular 5-dimensional "prismatoid" polytope. We use the Euler characteristic to prove
    that there is no analogous 4-dimensional prismatoid.

  • 10h55 - 11h20

    A Computational Framework for Determining Run-Maximal Strings

    • Andrew Baker, prés., McMaster University
    • Antoine Deza, McMaster University
    • Frantisek Franek, McMaster University

    We investigate the maximum runs in strings with fixed length and distinct characters. Exploiting
    the notion of an r-cover, we obtain all previously known values on binary strings and extend the
    computation to length 74. Noticeably, we exhibit a run-maximal string containing aaaa.

  • 11h20 - 11h45

    Lower Bounds and Exact Algorithms for the Quadratic Minimum Spanning Tree Problem

    • Dilson Lucas Pereira, prés., Universidade Federal de Minas Gerais
    • Michel Gendreau, Polytechnique Montréal
    • Alexandre Cunha, Universidade Federal de Minas Gerais

    In this work we address the Quadratic Minimum Spanning Tree Problem. Initially we develop a branch-and-bound algorithm using an RLT lower bound for the problem. Then, we propose a hierarchy of lower bounds of increasing strength. We present results concerning the strength and computational complexity of computing these bounds. A branch-and-bound algorithm is developed for one of the cases.

  • 11h45 - 12h10

    Semidefinite Programming Approaches for a Class of Complementarity Problems

    • Patricia Gillett, prés., Polytechnique Montréal
    • Miguel F. Anjos, GERAD, Polytechnique Montréal

    We consider a class of complementarity problems with non-convex quadratic objective functions. We discuss the difficulty of globally solving problems of this class and the potential for semidefinite programming relaxations to give tighter bounds. We present one such semidefinite programming relaxation in depth and discuss ongoing efforts to further strengthen the model.