Skip to yearly menu bar Skip to main content


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.