Augmentation methods in combinatorial optimization describe a large class of algorithms which operate by taking a feasible solution and repeatedly searching a large class of moves for an improving move to augment the solution with thereby improving the objective. In this talk, we will discuss a generalization of these approaches to arbitrary integer programs which makes use of a Graver Basis, a collection of moves so large as to ensure augmentation algorithms converge to the optimal solution but generally too large to be practical to work with. In spite of their size, just understanding the combinatorial structure of these Graver bases can lend itself to the development of simple efficient algorithms for solving the associated integer programs. We will discuss the structure of the Graver basis for two categories of nonlinear convex integer program, the first derived from a total variation-regularized image denoising problem and the second based on solving a matching problem on a graph. We then demonstrate how to use this structure to derive efficient exact augmentation routines for these nonlinear integer programs.

Bio: Dominic Yang is a postdoc in the MCS division at Argonne National Lab and is interested in efficient, scalable algorithms for discrete and combinatorial optimization, especially graph problems. He previously finished his Ph. D. at University of California, Los Angeles. 

See all upcoming talks at https://www.anl.gov/mcs/lans-seminars