Solving and benchmarking QUBO problems with Gurobi in Python

Overview

Gurobi is a state-of-the-art classical optimizer for Quadratic Unconstrained Binary Optimization (QUBO) problems.

Core gurobipy implementation

The core gurobipy implementation for QUBO is relatively compact:

model = gp.Model()
x = model.addMVar(n, vtype=GRB.BINARY)
model.setObjective(x @ Q @ x, GRB.MINIMIZE)
model.optimize()
solution = x.X.astype(int)
objective = model.ObjVal

Complete workflow in Python

The complete workflow in Python is:

1. Formulate a graph problem (weighted Max-Cut) as QUBO.
2. Solve it with Gurobi.
3. Benchmark increasingly large instances.
4. Understand what the solver is doing beyond the optimize() call.

Feedback

Interested in feedback on the modeling, benchmarking methodology, and which additional Gurobi metrics would make the comparison more rigorous.