Discrete Optimization Talks (DOTs)

Constrained submodular maximization has a wide range of applications in multiple fields such as computer science, operations research, economics and machine learning. Nemhauser, Wolsey and Fisher introduced the standard greedy algorithm in 1978 and since then it has played an important role to obtain provable guarantees for different variants of the problem. Moreover, researchers have focused not only on providing improved quality and efficiency guarantees, but also on adapting it to related submodular optimization models. In this talk, I will address two questions: (1) Why does it perform so well in practice despite its worst-case guarantee? (2) How do we adapt it to a robust model that looks to simultaneously optimize several objective functions?

This talk is based on joint works with M. Singh, S. Pokutta, N. Haghtalab, J. Naor and N. Anari.

Bio: Alfredo Torrico is a postdoctoral researcher at the CERC in Data Science, Polytechnique Montreal. He obtained his Ph.D. in Operations Research in the School of Industrial and Systems Engineering at Georgia Tech in 2019. His main interest is the design of theoretical tools at the interface between discrete and continuous optimization for resource allocation and subset selection problems. Other topics of interest include fairness and diversity, spread of misinformation, and in general, topics on Operations Research/Machine Learning for social good.

Optimization models with binary decisions are nonconvex and thus lack strong duality, which limits the usefulness of tools such as shadow prices and the KKT conditions. For example, in convex markets, shadow (dual) prices are associated with market equilibrium, and for convex games the existence and uniqueness of Nash equilibrium can be proved via fixed-point theorem and KKT conditions. Those results are lacking in their nonconvex counterparts.

We use copositive programming to formulate discrete problems in applications including nonconvex energy markets and nonconvex games, to leverage its convexity and strong duality features. We obtain several novel theoretical and numerical results for those applications, including a new revenue-adequate pricing scheme for energy markets, and existence, uniqueness, and KKT conditions for the pure-strategy Nash equilibrium in discrete games. We also propose a novel and easy-to-implement cutting-plane algorithm for mixed-integer copositive programs, and employ it in our applications.

Bio: Cheng Guo is a fourth-year Ph.D. student advised by Prof. Merve Bodur in the Department of Mechanical and Industrial Engineering at University of Toronto. She received her B.A. in Economics and B.S. in Mathematics from Wuhan University, China and M.S. in Operations Research from Columbia University. Her research interests are in the intersection of optimization and economics, with a focus on integer/stochastic programming modeling, energy markets, and decomposition methods.

Optimization problems arise in different areas of Process Systems Engineering (PSE), and solving these problems efficiently is essential for addressing important industrial applications. Quantum computers have the potential to efficiently solve challenging nonlinear and combinatorial problems. However, available quantum computers cannot solve practical problems; they are limited to small sizes, and do not handle nonlinearities well. In this talk, we propose hybrid classical-quantum algorithms to solve mixed integer nonlinear problems (MINLP) and apply decomposition strategies to break down MINLPs into subproblems that can be solved by quantum computers. We will cover different approaches to solving Quadratic Unconstrained Binary Optimization (QUBO) problems through unconventional computation methods, including Quantum algorithms, and discuss how these approaches lead to algorithms able to outperform classical solution approaches.

Bio:

David obtained his bachelor's degrees in Chemical Engineering and Physics from Universidad de los Andes, in Colombia. He also completed his M.Sc. at the same university in Chemical Engineering with focus on optimal control. He is enrolled in the PhD Program of the Chemical Engineering Department at Carnegie Mellon University under the guidance of Prof. Ignacio Grossmann since 2017 as part of the Center for Advanced Process Decision Making (CAPD).

His research focus is on software and algorithms for Mixed-Integer Nonlinear Programming and Generalized Disjunctive Programming. With a focus on Applications to Process Systems Engineering. More recently he has been working on the proposal of Quantum Algorithms for addressing nonlinear combinatorial optimization. He did an internship at ExxonMobil Research and Engineering in 2018, at the Process Technology Department, and 2020, at the Corporate Strategic Research division, and at NASA Quantum and Artificial Intelligence laboratory in 2019. He was part of the Feynman Quantum Academy program from the University Space Research Association in 2019 and received the Mark Dennis Karl Teaching Assistant Award in Chemical Engineering at CMU that same year.