Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer\n Linear Programs

2020/11/11 by Matthias Walter, Walter, Matthias
Decision Sciences · Engineering · #90C11 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.0 #Optimization and Control (math.OC) #Scheduling and Optimization Algorithms #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.2011.06076

openalex publication_date 2020/11/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• On the depth of cutting planes
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization -- II
• Theoretical challenges towards cutting-plane selection
• Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts