Polynomial Programming Relaxations of Binary Quadratic Problems


21.04.2010, 10:00 - 11:00


Raum: N.2.01
Hauptgebäude, Nordtrakt West Ebene 2


Institut für Mathematik


We present a general framework for conic relaxations based on polynomial programming. Using this framework we can generalize ideas from binary programming to binary quadratic programming. We re-derive previous relaxation schemes and provide stronger ones for general binary quadratic programming. Also, using the same framework, we propose cutting schemes to generate valid quadratic inequalities. One of the advantages of our techniques is that they are based on second-order cones. This makes them computationally more efficient compared to those based on general semidefinite programming. Computational tests show that our approach is competitive in terms of bounds and time. This is joint work with Bissan Ghaddar and Juan Vera.


Miguel Anjos, Ph.D.


Anita Wachter [ Email: anita.wachter@uni-klu.ac.at ]