Including an Industrial Optimization Day

HEC Montréal, May 7 - 9, 2012


HEC Montréal, May 7 — 9, 2012

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TB8 Optimisation discrète / Optimization Problems with Discrete Structure

May 8, 2012 10:30 AM – 12:10 PM

Location: Transat

Chaired by Miguel F. Anjos

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:30 AM - 10:55 AM

    The Width of 4-Prismatoids

    • Tamon Stephen, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:55 AM - 11:20 AM

    A Computational Framework for Determining Run-Maximal Strings

    • Andrew Baker, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:20 AM - 11:45 AM

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

    • Dilson Lucas Pereira, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:45 AM - 12:10 PM

    Semidefinite Programming Approaches for a Class of Complementarity Problems

    • Patricia Gillett, presenter, 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.