Back to activities
GERAD seminar

Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints


Mar 13, 2024   11:00 AM — 12:00 PM

Qimeng (Kim) Yu Université de Montréal, Canada

Kim Yu

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.


Hybrid activity at GERAD
Zoom et salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour

Montréal Québec H3T 1J4

Research Axis