Invited Talk
in
Workshop: GroundedML: Anchoring Machine Learning in Classical Algorithmic Theory
Continuous cutting plane algorithms in integer programming
Andrea Lodi
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.
Chat is not available.