Journées de l'optimisation 2014

                             Incluant une Journée industrielle de l'optimisation

                                              HEC Montréal, 5 - 7 mai 2014


HEC Montréal, 5 — 7 mai 2014

Horaire Auteurs Mon horaire

MD7 Optimisation conique / Conic Optimization

5 mai 2014 15h30 – 17h10

Salle: St-Hubert

Présidée par Elspeth Adams

4 présentations

  • 15h30 - 15h55

    Unsatisfiability and Semidefinite Certificates of Infeasibility

    • Miguel F. Anjos, prés., GERAD, Polytechnique Montréal
    • Manuel V.C. Vieira, Universidade Nova de Lisboa

    The satisfiability problem can be formulated using semidefinite programming. If the semidefinite problem is infeasible, then the satisfiability instance is unsatisfiable, and a proof of unsatisfiability follows from the dual certificate of infeasibility. We show that this certificate can provide information about minimal unsatisfiable subformulas.

  • 15h55 - 16h20

    Finding Better Solutions to Nonconvex Quadratic Equilibrium Problems Using Semidefinite Programming

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

    For nonconvex problems, many nonlinear solvers can return suboptimal solutions. We solve SDP relaxations to bound QPECs and also derive warmstarting points for use with a nonlinear solver. In many cases, the solutions found using warmstarting can be confirmed to be at least near-optimal by comparison with the SDP bounds.

  • 16h20 - 16h45

    Disjunctive-Conic-Cuts and Mixed Integer Second Order Cone Pptimization

    • Julio Goez, prés., Polytechnique Montréal
    • Pietro Belotti, FICO
    • Imre Pólik, SAS Institute
    • Ted Ralphs, Lehigh University
    • Tamás Terlaky, Lehigh University

    Mixed integer second order cone optimization (MISOCO) problems have a increasing number of engineering applications including supply chain, finance, and networks design. In this talk we analyze the derivation of Disjunctive-Conic-Cuts (DCCs) for MISOCO problems. We present a full characterization of the DCCs when the disjunctive set considered is defined by parallel hyperplanes.

  • 16h45 - 17h10

    Separating Hierarchical Cuts to Strengthen Semidefinite Relaxations of Max-Cut Problems

    • Elspeth Adams, prés., Polytechnique Montréal
    • Miguel F. Anjos, GERAD, Polytechnique Montréal
    • Franz Rendl, Alpen-Adria Universitaet Klagenfurt
    • Angelika Wiegele, Alpen-Adria Universitaet Klagenfurt

    The max-cut problem can be closely approximated using the basic semidefinite relaxation and iteratively refined by adding valid inequalities. We propose a projection polytope as a new way to improve the relaxations and a separation algorithm to identify which of these are valid cuts. Theoretical and computational results will be presented.