3 June – Thomas McCormick: Why Should You Care About Submodularity?
Many real-world problems are discrete, in that the natural decision variables can take only integer values. They are also combinatorial, in that the number of possible solutions grows exponentially in their size. This makes them challenging to solve unless one can identify some special structure to take advantage of. One special structure that turns out to have many applications is submodularity. A submodular function gives a value to each possible subset of a finite set as a sort of joint upper bound on using that subset, or as the cost or value of the subset. McCormick will define submodularity and survey some of its applications in a variety of areas, and eventually outline what advantages it brings to the associated optimization problems. It will then be outlined how to extend it from subsets to the integer lattice, using an “assemble to order” application as motivation. This extension will demonstrate both the strengths and weaknesses of submodularity in getting efficient algorithms as the problem size grows.
S. Thomas McCormick is the W.J. Van Dusen Professor of Management at the Sauder School of Business at the University of British Columbia. His research interests include combinatorial optimization, polyhedral combinatorics, network flows, submodularity, and parametric optimization, and the applications of these tools in operations management. He has given plenary talks and short courses on submodularity in Göttingen, Montréal, Cargèse, Clermont-Ferrand, Kyoto, and Vancouver.
