Gap plots

[dharabor]

This is a new chart proposal.

It would be good to understand where the opportunities are; i.e., which instances have the largest gap between their current best-known solution and a best-known lower-bound. Similarly, knowing the gap allows us to compare algorithms in terms of solution quality.

As input, we need to compute and import the trivial bound (sum of individual optimal path costs) for every instance which is not already closed.

[dharabor]

Some more details.

I think the measure we want is AUC: Area Under the Curve. For a given instance, we can measure the area as C^ / C, where C^ is the best known solution cost and C is the solution cost computed by a given algorithm. Notice as C gets larger, the area gets smaller, reaching zero in the limit (i.e., failing to solve a problem is equivalent to infinite cost and thus zero area).

We can measure AUC at the scenario level. At the map level there's probably too many points. But we can similarly calculate a single point representing a whole scenario as {AUC}^ / AUC, where {AUC}^ = 100% is the SOTA for a given scenario and {AUC} is the percentage of that area under the curve of a given algorithm. A similar approach lets us compute AUC for the entire benchmark set, with one single point representing each map.