Title: Solving the Hypergraph Partitioning Problem as an Integer Linear Program

Many technical fields, ranging from bioinformatics to databases to large scale integrated circuits deal with the interrelation between elementary objects. Objects are represented as vertices and the relationships between them are represented as hyperedges (these are edges that connect two or more vertices). We seek a layout that groups like objects and separates unlike objects--in our case, we will restrict ourselves to partitioning for integrated circuit layout. The hypergraph partitioning problem belongs to the class of NP-hard combinatorial problems so exact solutions for large problems are, at present, intractable. In this talk, we formulate hypergraph partitioning as an integer linear program (ILP) and solve it to optimality using a state-of-the-art ILP solver. Since this problem is NP-hard, we use a good starting solution and intelligent ILP solver parameter settings to be able to solve the problem in "reasonable" time. It turns out that if we formulate the model to take advantage of fixed vertices (that represent input/output terminals in a circuit), we can, in fact, solve fairly large problems.
Biography:
Dorothy Kucar is a Ph.D. student in Electrical and Computer Engineering at the University of Waterloo. She is currently wrapping up her studies and expects to be done by the end of this year. She obtained a BMATH in Applied Mathematics at the University of Waterloo in 1998, a MASc. in Systems Design Engineering, also at the University of Waterloo in 2000 and has since moved on into the exciting world of electrical engineering. Her current interests include integrated circuit computer-aided design, numerical solver technology and high performance computing.