ISE Welcomes Elspeth Adams

Posted: 

Projection based cuts for tightening semidefinite relaxations of the max-cut problem

Elspeth Adams, Post-Doctoral Fellow, Lehigh University

Wednesday, January 27, 2016 from 4:00 – 5:00 pm

120 Baker Systems, 1971 Neil Avenue

Semidefinite optimization (SDO) is an exciting and well developed branch of conic optimization. It is analogous to linear programming in many ways except optimizes over the cone of positive semidefinite matrices. Applications of SDO include problems in energy, engineering and physics. This talk will explore a brief background of SDO and then examine the popular maximum cut problem in which nodes are partitions into two sets to maximize the weighted connection between the sets. Starting with a semidefinite relaxation for the problem this talk will present a novel family of cuts used to tighten the relaxation. Two aspects of the cuts will be examined: a mathematical hierarchy that converges to global optimality and the practical components of a cutting plane method.

Elspeth Adams is a post doctoral fellow at Lehigh University. She received her Bachelors in Mathematics majoring in mathematical sciences from the University of Waterloo in Ontario, Canada. Her masters in applied science, also at the University of Waterloo, focused on a semidefinite relaxation for the 2-dimensional facility layout problem. She earned her PhD from École Polytechnique de Montréal in Quebec Canada. Her research interests include conic optimization, bilevel programming and combinatorial problems.