Videos

Andrea Lodi - Continuous cutting plane algorithms in integer programming - IPAM at UCLA

Presenter
February 27, 2023
Abstract
Recorded 27 February 2023. Andrea Lodi of Cornell University presents "Continuous cutting plane algorithms in integer programming" at IPAM's Artificial Intelligence and Discrete Optimization Workshop. Abstract: Cutting planes for mixed-integer linear programs (MILPs) are typically computed in rounds by iteratively solving optimization problems, the so-called separation. Instead, we reframe the problem of finding good cutting planes as a continuous optimization problem over weights parametrizing families of valid inequalities. This problem can also be interpreted as optimizing a neural network to solve an optimization problem over subadditive functions, which we call the subadditive primal problem of the MILP. To do so, we propose a concrete two-step algorithm, and demonstrate empirical gains when optimizing generalized Gomory mixed-integer inequalities over various classes of MILPs. (Joint work with Didier Chételat.) Learn more online at: http://www.ipam.ucla.edu/programs/workshops/artificial-intelligence-and-discrete-optimization/