Solving QUBO with Gurobi: branch-and-bound, heuristics…
0 reactions
Solving QUBO with Gurobi: branch-and-bound, heuristics, and optimality gaps
QUBO is frequently discussed in the context of quantum optimization, but it is fundamentally a classical combinatorial optimization formulation. Any meaningful evaluation of an alternative computing approach therefore requires comparison against strong classical algorithms.
I created a technical walkthrough of solving Quadratic Unconstrained Binary Optimization problems with Gurobi and Python.
The video begins by formulating weighted Max-Cut as a QUBO, representing the objective using a symmetric matrix and binary vector, and implementing the model with gurobipy.
It then investigates what happens beyond calling optimize():
\- the distinction between exact and heuristic solution methods;
\- how branch-and-bound uses mathematical bounds to prune the search space;
\- why runtime depends on instance structure rather than only variable count;
\- why dense QUBO matrices are generally more difficult than sparse ones;
\- how primal heuristics can find strong feasible solutions early;
\- why proving optimality may take considerably longer than finding the final solution;
\- how MIPGap controls the termination condition;
\- and why deterministic classical solvers are useful for reproducible benchmarking.
One experiment produced the initially surprising result that a 38-variable instance required more time than a 39-variable instance. Changing the random seed changed that relationship, illustrating why isolated problem-size measurements are insufficient for characterizing solver performance.
The larger motivation is benchmarking. Before discussing whether a new algorithm or computing architecture provides an advantage, we need to establish what state-of-the-art classical software can already achieve.
Video: https://youtu.be/TB1ny8o4ImQ
I’d be interested in thoughts on designing rigorous QUBO benchmarks. Besides runtime and objective value, which instance characteristics and solver metrics should be reported?
#technology
QUBO is frequently discussed in the context of quantum optimization, but it is fundamentally a classical combinatorial optimization formulation. Any meaningful evaluation of an alternative computing approach therefore requires comparison against strong classical algorithms.
I created a technical walkthrough of solving Quadratic Unconstrained Binary Optimization problems with Gurobi and Python.
The video begins by formulating weighted Max-Cut as a QUBO, representing the objective using a symmetric matrix and binary vector, and implementing the model with gurobipy.
It then investigates what happens beyond calling optimize():
\- the distinction between exact and heuristic solution methods;
\- how branch-and-bound uses mathematical bounds to prune the search space;
\- why runtime depends on instance structure rather than only variable count;
\- why dense QUBO matrices are generally more difficult than sparse ones;
\- how primal heuristics can find strong feasible solutions early;
\- why proving optimality may take considerably longer than finding the final solution;
\- how MIPGap controls the termination condition;
\- and why deterministic classical solvers are useful for reproducible benchmarking.
One experiment produced the initially surprising result that a 38-variable instance required more time than a 39-variable instance. Changing the random seed changed that relationship, illustrating why isolated problem-size measurements are insufficient for characterizing solver performance.
The larger motivation is benchmarking. Before discussing whether a new algorithm or computing architecture provides an advantage, we need to establish what state-of-the-art classical software can already achieve.
Video: https://youtu.be/TB1ny8o4ImQ
I’d be interested in thoughts on designing rigorous QUBO benchmarks. Besides runtime and objective value, which instance characteristics and solver metrics should be reported?
#technology
| 3,000 mlx | |
| 6 | |
| 0 |