Branch-and-bound solves random binary IPs in poly(n)-time
From MaRDI portal
Branch-and-bound solves random binary IPs in poly\((n)\)-time
Abstract: Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some variable to an integer value in one node and to in the other node. Even though modern MILP solvers are able to solve very large-scale instances efficiently, relatively little attention has been given to understanding why the underlying branch-and-bound algorithm performs so well. In this paper our goal is to theoretically analyze the performance of the standard variable branching based branch-and-bound algorithm. In order to avoid the exponential worst-case lower bounds, we follow the common idea of considering random instances. More precisely, we consider random integer programs where the entries of the coefficient matrix and the objective function are randomly sampled. Our main result is that with good probability branch-and-bound with variable branching explores only a polynomial number of nodes to solve these instances, for a fixed number of constraints. To the best of our knowledge this is the first known such result for a standard version of branch-and-bound. We believe that this result provides a compelling indication of why branch-and-bound with variable branching works so well in practice.
Recommendations
- A randomized parallel branch-and-bound algorithm
- The solution of some random NP-hard problems in polynomial expected time
- scientific article; zbMATH DE number 1334602
- An efficient approach to solving random \(k\)-SAT problems
- Randomized approximation of the constraint satisfaction problem
- scientific article; zbMATH DE number 1002207
- Optimization, randomized approximability, and Boolean constraint satisfaction problems
- scientific article; zbMATH DE number 2102760
- Randomized polynomial time protocol for combinatorial Slepian-Wolf problem
Cites work
- A Computational Study of Search Strategies for Mixed Integer Programming
- An Automatic Method of Solving Discrete Programming Problems
- Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
- Approximating polyhedra with sparse inequalities
- Basis reduction and the complexity of branch-and-bound
- Branching rules revisited
- Cube Slicing in R n
- Factoring polynomials with rational coefficients
- Hard Knapsack Problems
- High-dimensional probability. An introduction with applications in data science
- scientific article; zbMATH DE number 4057285 (Why is no real title available?)
- scientific article; zbMATH DE number 1342116 (Why is no real title available?)
- scientific article; zbMATH DE number 2086919 (Why is no real title available?)
- scientific article; zbMATH DE number 1416629 (Why is no real title available?)
- Integer Programming
- Integer Programming with a Fixed Number of Variables
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- On the integrality gap of binary integer programs with Gaussian data
- Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
- Probabilistic analysis of knapsack core algorithms
- Probabilistic Analysis of the Multidimensional Knapsack Problem
- Progress in computational mixed integer programming -- a look back from the other side of the tipping point
- Random knapsack in expected polynomial time
- Smoothed analysis of algorithms
- Sparsity of lift-and-project cutting planes
- Trivial integer programs unsolvable by branch-and-bound
- Verifying integer programming results
Cited in
(13)- Thinner is not always better: cascade knapsack problems
- Incumbent solutions in branch-and-bound algorithms: Setting the record straight
- On the complexity of finding shortest variable disjunction branch-and-bound proofs
- Further results on an abstract model for branching and its application to mixed integer programming
- Improving branch-and-cut performance by random sampling
- Lower bounds on the size of general branch-and-bound trees
- Early estimates of the size of branch-and-bound trees
- Predicting the solution time of branch-and-bound algorithms for mixed-integer programs
- Multivariable Branching: A 0-1 Knapsack Problem Case Study
- Basis reduction and the complexity of branch-and-bound
- On the integrality gap of binary integer programs with Gaussian data
- Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}
- Complexity of optimizing over the integers
This page was built for publication: Branch-and-bound solves random binary IPs in poly\((n)\)-time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041109)
