David Bergman

When and where: Friday, March 2, 2018, 2PM-3:30PM, Lindner Hall 608

Speaker: David Bergman from the University of Connecticut

Title: Discrete Nonlinear Optimization by State-Space Decompositions

Abstract: Motivated by optimization problems arising in revenue management, portfolio optimization, and healthcare, this talk describes a decomposition approach for binary optimization problems with nonlinear objectives and linear constraints. This methodology relies on the partition of the objective function into separate low-dimensional dynamic programming (DP) models, each of which can be equivalently represented as a shortest-path problem in an underlying state transition graph. We will discuss how the associated transition graphs can be related by a mixed-integer linear program (MILP) so as to produce exact solutions to the original nonlinear problem. To address DPs with large state spaces, we present a general relaxation mechanism which dynamically aggregates states during the construction of the transition graphs. The resulting MILP provides both lower and upper bounds to the nonlinear function and may be embedded in branch-and- bound procedures to find provably optimal solutions. Large-scale numerical studies indicate that the proposed technique often outperforms state-of-the-art approaches by orders of magnitude in the applications tested.

Bio: David Bergman is an Assistant Professor of Operations and Information Management at the University of Connecticut. He received his Ph.D. in 2013 from Carnegie Mellon University in Algorithms, Combinatorics, and Optimization. The focus of his research is on investigating innovative applications of decision diagrams in discrete optimization, and his work, more generally, is on developing optimization algorithms to advance the state of the art in computational optimization. David’s research has appeared in top business journals, including Management Science, Operations Research, and INFORMS Journal on Computing, and he currently serves on the editorial board for Constraints. David has active ties to industry, working as an External Advisor to McKinsey & Company, and as an External Consultant to Mitsubishi Electric Research Laboratories, Westchester Management, and BlueVoyant.