Face dimensions of general-purpose cutting planes for mixed-integer linear programs

DOI10.1007/978-3-030-73879-2_28MaRDI QIDQ2061900zbMATH OpenOpenAlexFDO

Authors Matthias Walter

Publication date 21 December 2021

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

zbMATH Keywords

dimensions of faces, state-of-the-art solver

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Abstract: Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they are facet-defining for the corresponding mixed-integer hull. In this paper we experimentally investigate the dimensions of faces induced by general-purpose cutting planes generated by a state-of-the-art solver. Therefore, we relate the dimension of each cutting plane to its impact in a branch-and-bound algorithm.

Recommendations

• Cutting planes for integer programs with general integer variables
• Cutting plane algorithms for the inverse mixed integer linear programming problem
• A cutting plane theory for mixed integer optimization
• A disjunctive cutting plane procedure for general mixed-integer linear programs
• Fenchel Cutting Planes for Integer Programs
• Computational Integer Programming and Cutting Planes
• On cutting planes for cardinality-constrained linear programs
• The mixed cutting plane algorithm for all-integer programming
• Cutting planes from extended LP formulations

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• Aggregation and Mixed Integer Rounding to Solve MIPs
• Algorithms to separate \(\{0,\frac{1}{2}\}\)-Chvátal-Gomory cuts
• Geometric algorithms and combinatorial optimization.
• Lifted flow cover inequalities for mixed 0-1 integer programs
• MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library
• On the \(0/1\) knapsack polytope
• Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
• The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts

Cited in

(1)

• Theoretical challenges towards cutting-plane selection

This page was built for publication: Face dimensions of general-purpose cutting planes for mixed-integer linear programs

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