MaxSAT Evaluation 2021
Affiliated with SAT 2021   ·   July 5-9   ·   Barcelona, Spain

Incomplete Track Score

The current scoring scheme used in the incomplete track is a relative score---each solver’s score depends on the other solvers that participate. The score gives a reasonable idea of solver ranking in the evaluation, but it is difficult to apply when solver writers run their own tests.

Hence, this year we propose to use the best known cost for each instance, which is the cost of the currently best known solution for the instance. The score a solver obtains will be computed by the same expression, but this time the “cost of the best solution for i found by any solver + 1” will become the “benchmark cost + 1”:

Previous Incomplete score for a solver s on instance i:
   ∑i ∈ instances solved by some solver (cost of best solution for i found by any solver + 1)
                      / (cost of solution for i found by solver + 1)

New incomplete score:
   ∑i ∈ instances solved by some solver (cost of best known cost for i + 1)
                      / (cost of solution for i found by solver + 1)

If a solver in the evaluation finds a solution with better cost than the current best known cost, the best known cost will be updated to that value and used in the evaluation scoring.

The best known solution costs will be published along with the evaluation results. The current best known costs for all instances will be posted to the website http://www.cs.toronto.edu/maxsat-lib/

In future work we encourage researchers to use the following methodology in their experiments with incomplete solvers.
  • Use the most recent best known cost obtained from maxsat-lib in computing scores for each solver.
  • If some solver in your experiments finds a better solution than the posted best known cost, then:
    • Use that better solution cost in your scores so that each score is never greater than one.
    • Please inform the organizers of the evaluation so that the best known cost can be updated. (Please include a v-line verifying your new better solution).
    • Include in the description of your results a discussion of any new best solutions found.