Efficient Algorithms for Hard Problems: Semidefinite Optimization for Binary Quadratic Programming

Abstract: Through three prominent combinatorial optimization problems (graph coloring, maximum cut, ordering) we will explain modelling techniques using semidefinite programming (as opposed to linear programming). We will derive relaxations that yield tight bounds and give rise to heuristics to obtain high-quality feasible solutions. We demonstrate how to combine these ingredients within a branch-and-bound framework, thus obtaining an exact solution method.

CV: Angelika Wiegele is a mathematician working in the field of combinatorial optimization and semidefinite optimization. She studied mathematics at the Alpen-Adria-Universit“at and at City University London where she was an Erasmus student

Please follow and like us:
Posted in TEWI-Kolloquium | Tagged , , , | Kommentare deaktiviert für Efficient Algorithms for Hard Problems: Semidefinite Optimization for Binary Quadratic Programming
RSS
EMAIL