Bio: Thiago Serra is an assistant professor of analytics and operations management at Bucknell University's Freeman College of Management. Previously, he was a visiting research scientist at Mitsubishi Electric Research Labs from 2018 to 2019, and an operations research analyst at Petrobras from 2009 to 2013. He has a Ph.D. in operations research from Carnegie Mellon University's Tepper School of Business, and received the Gerald L. Thompson Doctoral Dissertation Award in Management Science in 2018. During his PhD., he was also awarded the INFORMS Judith Liebman Award and a best poster award at the INFORMS Annual Meeting. In 2021, he received a National Science Foundation (NSF) grant and the AAAI Outstanding Programming Committee award for scholarship and service at the intersection of optimization and machine learning. His work on decision diagrams has been published at the Mathematical Programming journal and at the CPAIOR conference.

Learning to bound using decision diagrams and reinforcement learning

Finding tight bounds on the optimal solution is a critical element of practical solution methods for discrete optimization problems. In the last decade, decision diagrams have brought a new perspective on obtaining upper and lower bounds that can be significantly better than classical bounding mechanisms, such as linear relaxations. However, the quality of the bounds achieved through this flexible bounding method is highly reliant on the ordering of variables chosen for building the diagram, and finding an ordering that optimizes standard metrics is an NP-hard problem, which is also difficult to model.

In this talk, I will present a generic approach based on deep reinforcement learning for obtaining an ordering for tightening the bounds obtained with approximate decision diagrams, and show that these bounds can be efficiently used to speed-up a branch-and-bound algorithm.

Bio: Quentin Cappart is an assistant professor in artificial intelligence at the Department of Computer and Software Engineering of Polytechnique Montréal. He obtained a Ph.D. in 2017 from Université catholique de Louvain (Belgium). After his Ph.D, he joined Polytechnique Montréal and CIRRELT as a postdoctoral fellow from 2018 to 2020. During these two years, he worked in the integration of machine learning and operations research. For instance, he showed that decision diagrams, thanks to their dynamic programming nature, can be a natural bridge between these two worlds.

Connections between column generation and decision diagrams with applications to graph coloring and vehicle routing

Column elimination: An alternative to column generation via relaxed decision diagrams

Column generation has been successfully applied for decades to solve large-scale linear programs. We discuss an alternative approach, based on relaxed decision diagrams, that can be viewed as `column elimination'. It produces increasingly stronger dual bounds via a process of iterative refinement of the diagram. Unlike column generation, column elimination produces a valid bound at each iteration, does not rely on linear programming duality, and does not require an embedding into branch-and-price to obtain integer optimality. We consider two applications, graph coloring and truck-drone routing, to demonstrate the promise of this approach.

Bio: Willem-Jan van Hoeve is the Carnegie Bosch Professor of Operations Research and Senior Associate Dean of Education at the Tepper School of Business, Carnegie Mellon University. His research focuses on developing new methodology for mathematical optimization with applications to network design, scheduling, vehicle routing, health care operations, and analytical marketing. He published over 60 academic articles, and co-authored the book "Decision Diagrams for Optimization." Van Hoeve’s research has been funded by the National Science Foundation, the Office of Naval Research, and two Google Faculty Research Awards. He has consulted for a variety of companies including FedEx Ground, Exxon Mobil, PNC Bank, Bosch/Siemens, Charter Steel, Kalibrate, and others. Van Hoeve received the Tepper School's MBA Teaching Award twice, as well as the MSBA Teaching Award.

Rectangular Decomposition of Mixed Integer Programs via Decision Diagrams

Over the past decade, decision diagrams (DDs) have been used to model and solve integer programming and combinatorial optimization problems. Despite successful performance of DDs in solving various discrete optimization problems, their extension to model mixed integer programs (MIPs) has been lacking. More broadly, the question on which problem structures admit a DD representation is still open in the DDs community. In this paper, we address this question by introducing a geometric decomposition framework based on rectangular formations that provides both necessary and sufficient conditions for a general MIP to be representable by DDs. As a special case, we show that any bounded mixed integer linear program admits a DD representation through a specialized Benders decomposition technique. The resulting DD encodes both integer and continuous variables, and therefore is amenable to the addition of feasibility and optimality cuts through refinement procedures. As an application for this framework, we develop a novel solution methodology for the unit commitment problem (UCP) in the wholesale electricity market. Computational experiments conducted on a stochastic variant of the UCP show a significant improvement of the solution time for the proposed method when compared to the outcome of modern solvers.

Bio: Danial Davarnia is an Assistant Professor in the Industrial Engineering Department at Iowa State University. Prior to this position, he was a postdoctoral fellow in the Tepper School of Business at Carnegie Mellon University. He obtained his Ph.D. from University of Florida in Industrial and Systems Engineering. His research interests include solution techniques for mixed-integer nonlinear programs, and statistical estimation in stochastic programming, with applications in finance, transportation, energy, and network interdiction.

Cut generation procedures via decision diagrams

Decision diagrams (DDs) are graphical structures that can encode complex combinatorial problems as network flow problems. This talk explains how to leverage this network flow reformulation to create valid inequalities for integer programming problems. We review the main components behind several cutting plane algorithms based on DDs and present recent advances in the field.

Bio: Margarita Castro is an Assistant Professor at the Industrial Engineering Department at Pontificia Universidad Católica de Chile. Margarita obtained her Ph.D. degree from the University of Toronto where she explored different ways to use DDs to solve discrete optimization problems. She has received several awards for her work on DDs, including the ACP Doctoral Research Award, first place at the Canadian OR Student Paper Competition, and runner-up at the ICS Student Paper Award.

A BDD approach to a special class of two-stage stochastic programs

Two-stage stochastic programs (2SPs) with binary recourse are challenging to solve and solution methods for such problems have been limited. We leverage the combinatorial nature of binary programs and convexify the the second-stage problems using binary decision diagrams. We generalize an existing approach of Lozano and Smith and propose a new solution method for a special class of 2SP with binary recourse. We also extend this work by incorporating Conditional Value-at-Risk and propose to our knowledge the first decomposition method for 2SP with binary recourse and a risk measure. Finally, we apply these methods to a novel stochastic dominating set program and present numerical results.

Bio: Merve Bodur is an Assistant Professor in the Department of Mechanical and Industrial Engineering at the University of Toronto. She also holds a Dean’s Spark Professorship in the Faculty of Applied Science and Engineering. Currently, she is the INFORMS Optimization Society Vice Chair of Integer and Discrete Optimization. She obtained her Ph.D. from University of Wisconsin-Madison and did a postdoc at Georgia Institute of Technology. She received her B.S. in Industrial Engineering and B.A. in Mathematics from Bogazici University, Turkey. Her research interests include stochastic programming, integer programming, multiobjective optimization and combinatorial optimization, with applications in a variety of areas such as scheduling, transportation, power systems, healthcare and telecommunications.

Decision diagram-based algorithms for discrete bilevel programs

Bilevel optimization considers two-player, two-level Stackelberg games in which a leader and a follower sequentially solve interdependent problems that optimize different objective functions. Bilevel optimization problems subsume a wide array of problems in robust optimization, network interdiction, and two-stage stochastic programming, which are known to be NP-hard in general. Discrete bilevel problems are particularly challenging as standard approaches for bilevel problems require the follower's problem to be convex. We proposed exact solution methodologies for discrete bilevel problems based on convexification techniques via decision diagrams. Our proposed algorithms outperform standard approaches from the literature on a collection of test problems from different application areas.

Bio: Leonardo Lozano is an assistant professor in the Operations, Business Analytics & Information Systems Department at University of Cincinnati. He received his B.Sc. degree from Universidad de los Andes, his M.Sc. degree from University of Florida, and his Ph.D. degree from Clemson University. His research focuses on exact algorithms for discrete optimization and has been published in Operations Research, Mathematical Programming, Transportation Science, and INFORMS Journal on Computing, among others.

Minimum Linearizations of Multilinear Programs

Multilinear Programs (MLPs) are a particular class of MINLPs which have multilinear functions in both the objective and the constraints. MLPs are typically solved by using Branch-and-Bound algorithms which rely on Linear Programming (LP) relaxations to obtain lower bounds. These LP relaxations are derived by introducing additional variables that represent bilinear products and by relaxing using McCormick envelopes. The size of the LP relaxation depends on the heuristic employed to identify the collection of variables to add. In this talk, we introduce the first approach for identifying the smallest size LP relaxation for a given MLP, by investigating an Integer Programming (IP) model that solves a specialized Decision Diagram representation where linearizations are encoded as in-trees. Our results on a collection of benchmarks indicate that the IP formulation can find smaller linearizations (up to 30% reduction in number of variables) and tighter relaxations (30% reduction in the root-node optimality gaps).

Bio: Arvind Raghunathan is currently a Senior Principal Research Scientist in the Data Analytics Group at Mitsubishi Electric Research Laboratories in Cambridge, Massachusetts, USA. His research focuses on algorithms for optimization of large-scale nonlinear and mixed integer nonlinear programs with applications in power grid, transportation systems and model-based control of processes. He serves on the editorial board of Optimization and Engineering, and Journal of Optimization Theory and Applications. He is a member of INFORMS and SIAM.

Multiobjective optimization with decision diagrams

This talk presents a novel framework for solving multiobjective discrete optimization problems with an arbitrary number of objectives. Our framework represents these problems as network models in that enumerating the Pareto frontier amounts to solving a multicriteria shortest path problem in an auxiliary network. We design techniques for exploiting network models to accelerate the identification of the Pareto frontier, most notably some operations to simplify the network by removing nodes and arcs while preserving the set of nondominated solutions. We show that the proposed framework yields orders-of-magnitude performance improvements over existing state-of-the-art algorithms on five problem classes containing both linear and nonlinear objective functions.

Bio: Carlos Cardonha is an assistant professor at the Department of Operations and Information Management at the University of Connecticut. His primary research interests are optimization, mathematical programming, and theoretical computer science, with a focus on the application of techniques in mixed-integer linear programming, combinatorial optimization, and algorithms design to operations research problems.