Ben Knueven
PhD Candidate
ISE, University of Tennessee
Friday, September 30th 2:20-3:20pm
John Tickle Building 410
Abstract:
Symmetry detection and exploitation has had a significant impact on our ability to solve combinatorial problems such as SAT, constraint programming, and integer optimization. Current methods of computing symmetries for combinatorial problems depend on algorithms for computing symmetries of graphs. Further, it is hypothesized that near-symmetries may induce many of the same computation issues as exact symmetries for combinatorial problems. In this talk, we present a branch-and-bound framework for detecting near-symmetries of graphs. More formally, given a graph G and an integer k, find the symmetries on subgraphs of G formed by removing no more than k edges. We call such symmetries “k-almost symmetries” of G. We specialize the framework and implement a branch-and-bound algorithm to find the best such subgraph for a given k. Computational results are reported, showing that for some popular graphs, few edges need be removed to induce additional symmetry.
Bio:
Ben Knueven is a PhD candidate in the Department of Industrial & Systems Engineering at the University of Tennessee. Prior to his studies at UTK, he was an instructor in the Department of Mathematics at Miami University, where he also received his MS in Mathematics in 2012. In addition to near- and exact-symmetry in integer programming, Ben’s current research interests also include optimization in power systems, with an emphasis on the unit commitment problem.