15h30 - 15h55
Unsatisfiability and Semidefinite Certificates of Infeasibility
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
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
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
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.