Applications that involve risk aversion or economies of scale are ubiquitous, such as investment portfolio management and concave cost facility location. In such applications, our task is typically to select items from a given collection to minimize risk/cost, or equivalently, negative utility. We use binary decision variables to represent whether an item is chosen or not, resulting in a discrete optimization problem. Commonly, due to a limited budget, our decision is cardinality-constrained; that is, a pre-specified parameter upper bounds the number of items that we may select. The objective functions that arise from these applications are a class of submodular functions. Finding a tractable convex hull description for the epigraph of any such function under a cardinality constraint has been an open problem. We make significant progress toward tackling this open problem and showcase the practical contributions of our theoretical results on mean-risk optimization, a powerful modeling tool in financial applications. Our experiments demonstrate that our proposed approach leads to significant computational improvement compared to available benchmarks.

Bio: Qimeng (Kim) Yu is an assistant professor in the Department of Computer Science and Operations Research (DIRO) at Université de Montréal. She completed her Ph.D. in Industrial Engineering and Management Sciences at Northwestern University in 2023, and she obtained her undergraduate degree in Mathematics at Carleton College in 2018. In her research, she develops theory and algorithms for mixed-integer nonlinear programming to facilitate the solution of complex models with real-world applications.