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

DOI10.1007/978-3-030-73879-2_28zbMATH Open1483.90087arXiv2011.06076OpenAlexW3160270652MaRDI QIDQ2061900FDOQ2061900

Authors: Matthias Walter 

Publication date: 21 December 2021

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Cites Work

• MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library
• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization.
• Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• On the \(0/1\) knapsack polytope
• Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs
• Aggregation and Mixed Integer Rounding to Solve MIPs
• The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs
• Algorithms to separate \(\{0,\frac{1}{2}\}\)-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)