Continuous cutting plane algorithms in integer programming

DOI10.1016/J.ORL.2023.06.004MaRDI QIDQ6047699zbMATH OpenOpenAlexFDO

Authors Didier Chételat, Andrea Lodi

Publication date 12 September 2023

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.09122

zbMATH Keywords

integer programmingcutting planesneural networkssubadditive functions

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11)

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. Code for reproducing the experiments can be found at https://github.com/dchetelat/subadditive.

Recommendations

• Adaptive cut selection in mixed-integer linear programming
• Local cuts for mixed-integer programming
• Cutting planes in integer and mixed integer programming
• Primal cutting plane algorithms revisited

Cites work

• A comparison of heuristics and relaxations for the capacitated plant location problem
• Cutting-plane theory: Algebraic methods
• Discrete optimization with decision diagrams
• Duality for mixed-integer linear programs
• Integer programming duality: Price functions and sensitivity analysis
• MIR closures of polyhedral sets
• Maximum matching and a polyhedron with 0,1-vertices
• Minimal inequalities
• Mixed integer programming computation
• Mixed-integer cuts from cyclic groups
• Optimizing over the first Chvátal closure
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Subadditive periodic functions
• TSPLIB—A Traveling Salesman Problem Library
• Valid inequalities for mixed integer linear programs

Cited in

(5)

• Fenchel Cutting Planes for Integer Programs
• scientific article; zbMATH DE number 4133833 (Why is no real title available?)
• Presolving and cutting planes for the generalized maximal covering location problem
• A surrogate cutting plane algorithm for all-integer programming
• Computational Integer Programming and Cutting Planes

This page was built for publication: Continuous cutting plane algorithms in integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6047699)