Continuous Cutting Plane Algorithms in Integer Programming

4/21/22 | 4:15pm | E25-111





Andrea Lodi

Andrew H. and Ann R. Tisch Professor
Cornell Tech

Abstract: Cutting planes for mixed-integer linear programs (MILPs) are typically computed in rounds by iteratively solving optimization problems. Instead, we reframe the problem of finding good cutting planes as a continuous optimization problem over weights parametrizing families of valid inequalities. We propose a practical two-step algorithm, and demonstrate empirical gains when optimizing Gomory mixed-integer inequalities over various families of MILPs. Finally, a reinterpretation of our approach as optimization of the subadditive dual using a deep neural network is provided.

Bio: Andrea Lodi is an Andrew H. and Ann R. Tisch Professor at the Jacobs Technion-Cornell Institute at Cornell Tech and the Technion. He is a member of the Operations Research and Information Engineering field at Cornell University. He received his PhD in System Engineering from the University of Bologna in 2000 and he was a Herman Goldstine Fellow at the IBM Mathematical Sciences Department, NY in 2005–2006. He was a full professor of Operations Research at DEI, the University of Bologna between 2007 and 2015. Between 2015 and 2022, he has been the Canada Excellence Research Chair in “Data Science for Real-time Decision Making” at Polytechnique Montréal. His main research interests are in Mixed-Integer Linear and Nonlinear Programming and Data Science, having a significant publication record in the most prestigious journals and conferences of those fields. Andrea Lodi's work has received several recognitions including the IBM and Google faculty awards. Andrea is the recipient of the INFORMS Optimization Society 2021 Farkas Prize. He serves in leading editorial positions, most notably, he is a co-Editor for Mathematical Programming and an Area Editor for INFORMS Journal on Computing. He has been the network coordinator and principal investigator of two large EU projects/networks, and, in the period 2006-2021, consultant of the IBM CPLEX research and development team. Andrea Lodi is the co-principal investigator of the project “Data Serving Canadians: Deep Learning and Optimization for the Knowledge Revolution,” 2017-2022, and the scientific co-director of IVADO, the Montréal Institute for Data Valorization.

Event Time: 

2022 - 16:15