Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
From MaRDI portal
Publication:2061899
DOI10.1007/978-3-030-73879-2_27zbMath1483.90083arXiv2011.05474OpenAlexW3162501176MaRDI QIDQ2061899
Hongyi Jiang, Michele Conforti, Amitabh Basu, Marco Di Summa
Publication date: 21 December 2021
Full work available at URL: https://arxiv.org/abs/2011.05474
Mixed integer programming (90C11) Abstract computational complexity for mathematical programming problems (90C60)
Related Items
On the complexity of finding shortest variable disjunction branch-and-bound proofs, An abstract model for branch-and-cut, Compressing branch-and-bound trees, On polytopes with linear rank with respect to generalizations of the split closure, A theoretical and computational analysis of full strong-branching, Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Achieving MILP feasibility quickly using general disjunctions
- Branching on general disjunctions
- On the complexity of cutting-plane proofs
- Improved strategies for branching on general disjunctions
- Approximating polyhedra with sparse inequalities
- On the complexity of cutting-plane proofs using split cuts
- On cutting-plane proofs in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Bounds on the Chvatal rank of polytopes in the 0/1-cube
- Some lower bounds on sparse outer approximations of polytopes
- Cutting planes, connectivity, and threshold logic
- On the Chvátal rank of polytopes in the 0/1 cube
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
- On the Matrix-Cut Rank of Polyhedra
- Integer Programming
- A Note on Gamma Functions
- Constraint Orbital Branching
- Mixed Integer Programming Computation
- Solving Real-World Linear Programs: A Decade and More of Progress
- Hard Knapsack Problems
- A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases
- A Block-$LU$ Update for Large-Scale Linear Programming
- 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
- Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances
- On the Width of Semialgebraic Proofs and Algorithms
- Trivial integer programs unsolvable by branch-and-bound
- 0/1 Polytopes with Quadratic Chvátal Rank
- Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
- Computational Complexity
- Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
- Experimental results on using general disjunctions in branch-and-bound for general-integer linear programming
