4 Presentations

• 
  03:30 PM - 03:55 PM

  Unsatisfiability and Semidefinite Certificates of Infeasibility

  • Miguel F. Anjos, presenter, 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.

• 
  03:55 PM - 04:20 PM

  Finding Better Solutions to Nonconvex Quadratic Equilibrium Problems Using Semidefinite Programming

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

• 
  04:20 PM - 04:45 PM

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

  • Julio Goez, presenter, 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.

• 
  04:45 PM - 05:10 PM

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

  • Elspeth Adams, presenter, 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.