Complexity of branch-and-bound and cutting planes in mixed-integer optimization
From MaRDI portal
Publication:2687063
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
Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)
Related Items
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