Branch-and-bound solves random binary IPs in poly\((n)\)-time

DOI10.1007/s10107-022-01895-4zbMath1519.90119arXiv2007.15192OpenAlexW4306786755MaRDI QIDQ6041109

Marco Molinaro, Santanu S. Dey, Yatharth Dubey

Publication date: 25 May 2023

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

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

zbMATH Keywords

polynomial number of nodesrandom integer programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (2)

Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set} ⋮ Complexity of optimizing over the integers

Cites Work

• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Approximating polyhedra with sparse inequalities
• Factoring polynomials with rational coefficients
• Branching rules revisited
• Verifying integer programming results
• Lectures on Modern Convex Optimization
• Integer Programming with a Fixed Number of Variables
• Integer Programming
• An Automatic Method of Solving Discrete Programming Problems
• Smoothed analysis of algorithms
• Cube Slicing in R n
• Probabilistic Analysis of the Multidimensional Knapsack Problem
• Hard Knapsack Problems
• A Computational Study of Search Strategies for Mixed Integer Programming
• High-Dimensional Probability
• Trivial integer programs unsolvable by branch-and-bound
• Sparsity of Lift-and-Project Cutting Planes
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• Random knapsack in expected polynomial time
• On the integrality gap of binary integer programs with Gaussian data
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Branch-and-bound solves random binary IPs in poly\((n)\)-time