A hybrid branch-and-bound approach for exact rational mixed-integer programming

DOI10.1007/s12532-013-0055-6zbMath1305.90310OpenAlexW2079258636MaRDI QIDQ744213

William Cook, Kati Wolter, Thorsten Koch, Daniel E. Steffy

Publication date: 6 October 2014

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-013-0055-6

zbMATH Keywords

branch-and-boundmixed integer programmingexact computation

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

A Safe Computational Framework for Integer Programming Applied to Chvátal’s Conjecture, Theoretical challenges towards cutting-plane selection, A review of computation of mathematically rigorous bounds on optima of linear programs, Characterizing 3-Sets in Union-Closed Families, Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates, Numerically Safe Lower Bounds for the Capacitated Vehicle Routing Problem, Safe and Verified Gomory Mixed-Integer Cuts in a Rational Mixed-Integer Program Framework, Automating weight function generation in graph pebbling, QMaxSATpb: a certified MaxSAT solver, Certificates of optimality for mixed integer linear programming using generalized subadditive generator functions, Cutting planes for families implying Frankl’s conjecture, A computational status update for exact rational mixed integer programming, A computational status update for exact rational mixed integer programming, The covering radius and a discrete surface area for non-hollow simplices, New complexity results for Łukasiewicz logic, Towards an Accurate Solution of Wireless Network Design Problems, Backdoors to tractable answer set programming

Uses Software

• gmp
• SCIP
• SoPlex
• Zimpl
• MIPLIB
• CPLEX
• Netlib
• Benchmarks for Optimization Software
• QSopt_ex
• Concorde
• QSopt-Exact
• MIPLIB2003
• NEOS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• QSopt_ex
• SCIP: solving constraint integer programs
• Condition measures and properties of the central trajectory of a linear program
• Some perturbation theory for linear programming
• On the complexity of linear programming under finite precision arithmetic
• The final NETLIB-LP results
• Solving linear programs with finite precision. I: Condition numbers and random programs
• Safe bounds in linear and mixed-integer linear programming
• Linear programming, complexity theory and elementary functional analysis
• Exact solutions to linear programming problems
• Conflict analysis in mixed integer programming
• Solving linear programs with finite precision. II: Algorithms
• Combinatorial Auctions: A Survey
• Numerically Safe Gomory Mixed-Integer Cuts
• An Exact Rational Mixed-Integer Programming Solver
• Computational Experience and the Explanatory Value of Condition Measures for Linear Optimization
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Computation of condition numbers for linear programming problems using Peña’s method
• Unifying Condition Numbers for Linear Programming
• A new condition number for linear programming
• Benchmarking optimization software with performance profiles.