A solver reports a QUBO objective value of −12,480. Another reports −12,510. For a minimization problem on the same model, the second answer is better. But how good is either one?
Without additional information, we cannot say. There may be a solution at −12,511, or an undiscovered one at −20,000. The best result found so far is an achievement, not a certificate that the search is complete.
That gap between a good answer and a known optimum is central to evaluating difficult optimization problems.
Best found is not necessarily best possible
A heuristic solver searches for promising assignments and returns the strongest one it discovers. It may improve rapidly and produce useful results long before any method can prove which assignment is globally optimal.
For a minimization problem, a feasible assignment gives an upper bound on the optimum: the true minimum can be no greater than the score already achieved. A mathematically established lower bound says the optimum cannot be smaller than a certain value. When the bounds meet, optimality is proven.
Suppose the best feasible score is 920 and a valid lower bound is 900. The unknown optimum lies somewhere between them. The remaining interval offers a rigorous statement about what is possible. Without a lower bound, even a record-setting answer may have an unknown distance from optimality.
Exact methods can sometimes produce such certificates through mathematical relaxations and systematic search. For larger or harder problems, a proof may remain computationally out of reach, while heuristic methods continue finding valuable solutions.
The difficulty of a percentage
Researchers often compare solvers through a gap relative to a reference solution. But a gap percentage has meaning only when we know the reference, the direction of optimization and the normalization being used.
A better record improves what we know how to achieve. A mathematical bound tells us what remains possible.
A result can be 0.5% from the best answer found by any tested solver. That is not the same as 0.5% from a proven optimum. The difference becomes especially important when a benchmark's best-known value changes.
For QUBO objectives, relative percentages can be awkward because scores may be negative, zero or altered by adding a constant to the objective. Adding the same constant to every assignment changes no optimization decision, yet it can change a naive percentage gap dramatically. A comparison should therefore state its reference and use a normalization that remains meaningful for the problem family.
One can compare absolute objective differences, benchmark-specific normalized gaps, or ratios to valid mathematical bounds when those are available. The right measure depends on the evidence the benchmark can genuinely support.
Check the answer before comparing it
The first scientific test is deceptively simple: take the returned binary assignment and independently recompute its objective value from the original coefficients. A solver's reported score is useful, but the assignment itself is the evidence.
Then compare like with like. Are the tools optimizing the same mathematical function? Do they use the same coefficient convention? Does one include a constant that the other omits? Are input transformations and returned assignments handled consistently?
Time also matters. A method that finds an excellent answer after an hour may be less useful to an interactive system than one that finds a slightly weaker answer after five seconds. A fair benchmark therefore compares performance against the same relevant wall-clock budgets and records setup time when it matters to the application.
A benchmark is convincing when its comparison survives another person's calculation.
Randomized solvers require repeated trials. One exceptional result does not describe consistency. Reporting medians, variation and the fraction of runs reaching a target quality can tell a more dependable story.
The progress curve
For an anytime solver, draw the best feasible objective found so far against elapsed time. Each downward step marks a new discovery. Several such curves, from different algorithms and repeated runs, reveal much more than a single final table.
They show who finds a useful answer quickly, who keeps improving, and how reliable the progress is across instances. For a researcher, they reveal the strengths of different search strategies. For a developer, they help choose execution budgets. For a planner, they help answer whether an additional period of computation is worth delaying a decision.
The same measurements can expose important differences between application classes. A solver might be excellent on sparse graph problems and less successful on dense spin-glass instances. That is information worth having, not a contradiction to hide.
What a strong result really tells us
The best scientific account combines the achieved objective, the reference used, the time required and the diversity of problems tested. Where mathematical bounds are available, it includes them. Where they are not, it says exactly what the benchmark established.
For buyers, this is a useful guide to evaluating optimization software. Ask how quickly a solver improves your models, how stable its performance is and how the answer is independently checked. For researchers, these disciplines create a cumulative record that other algorithms can improve.
A record can be meaningful without being optimal. What matters is knowing precisely which achievement has been demonstrated and why it matters to the decisions at hand.