Complexity of branch-and-bound and cutting planes in mixed-integer optimization

DOI10.1007/s10107-022-01789-5OpenAlexW4220883578MaRDI QIDQ2687063

Hongyi Jiang, Amitabh Basu, Marco Di Summa, Michele Conforti

Publication date: 1 March 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

branch-and-boundcutting planescomplexity boundsmixed integer nonlinear optimization

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

Equalizer zero-determinant strategy in discounted repeated Stackelberg asymmetric game

Cites Work

• On the complexity of cutting-plane proofs
• Chvátal closures for mixed integer programming problems
• Bounds on the size of branch-and-bound proofs for integer knapsacks
• On the complexity of cutting-plane proofs using split cuts
• On cutting-plane proofs in combinatorial optimization
• A class of facet producing graphs for vertex packing polyhedra
• A combinatorial analysis of topological dissections
• On certain polytopes associated with graphs
• Bounds on the Chvatal rank of polytopes in the 0/1-cube
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\). II: Application of \(K\)-convexity
• Cutting planes, connectivity, and threshold logic
• On the Chvátal rank of polytopes in the 0/1 cube
• Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
• Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
• Edmonds polytopes and a hierarchy of combinatorial problems
• Gomory cuts revisited
• On the Matrix-Cut Rank of Polyhedra
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• Outline of an algorithm for integer solutions to linear programs
• Reverse Chvátal--Gomory Rank
• The traveling salesman problem on a graph and some related integer polyhedra
• Hard Knapsack Problems
• Faces for a linear inequality in 0–1 variables
• Facets of the knapsack polytope
• Discretely ordered modules as a first-order extension of the cutting planes proof system
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds for resolution and cutting plane proofs and monotone computations
• On the Width of Semialgebraic Proofs and Algorithms
• Halin graphs and the travelling salesman problem
• Properties of vertex packing and independence system polyhedra
• Trivial integer programs unsolvable by branch-and-bound
• 0/1 Polytopes with Quadratic Chvátal Rank
• The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
• Split Cuts in the Plane
• On the facial structure of set packing polyhedra
• Paths, Trees, and Flowers
• Solution of a Large-Scale Traveling-Salesman Problem
• On a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem
• Maximum matching and a polyhedron with 0,1-vertices
• Edmonds polytopes and weakly hamiltonian graphs
• Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
• Partition of Space
• A disjunctive cutting plane procedure for general mixed-integer linear programs
• On the power and limitations of branch and cut
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item