3
$\begingroup$

I built a solver for a classic scheduling problem. It has some exact methods and some heuristics methods.

I want to judge the quality of the work beyond time efficiency and solution quality.

For example, I have found those slides on consistency in solvers. Since they are just slides, it's not elaborate enough.

So, what should I consider as quality "measures" and why? Don't hesitate to point me to some articles on the subject.

Improve this question
$\endgroup$
1
  • $\begingroup$ What do you mean about "solver for a classic scheduling problem"? Does it mean to solve a specific scheduling problem or it was developed to solve the general mathematical programming (e.g. LP, MIP, etc)? $\endgroup$
    – A.Omidi
    Commented Aug 6, 2020 at 19:04

1 Answer 1

Reset to default
3
$\begingroup$

In the order of importance (my opinion):

  • Solution quality/optimality
  • Speed
  • Robustness towards numerically challenging problems
  • API and model creation speed

The first three you can do through benchmarks (see e.g. the famous Mittelmann benchmarks), while the last one is a matter of taste (although you can measure the model creation speed).

I think a point that deserves special mention is the numerical robustness: I would get some numerically challenging problems, solve them with your solver and then compare that solution to existing problems. Because any KPI that you can come up with only makes sense if it is compared to an existing product, so that people can judge whether the new product is indeed good.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Okay so, here is a problem: If I run the solver 20 times with a heuristic approach, the best results are far from the median. Is this problem related to the robustness ? $\endgroup$
    – Joffrey L.
    Commented Aug 5, 2020 at 17:32
  • $\begingroup$ I'd say it's more related to solution quality. With a heuristic, you don't expect an optimal solution each time, but you also don't want to judge it on the best of a series of runs. I would be inclined to judge it on median performance and also perhaps on the quartiles of performance, or the 10th and 90th percentiles, or some other measure of spread. $\endgroup$
    – prubin ♦
    Commented Aug 6, 2020 at 18:04
  • 1
    $\begingroup$ I agree with @prubin: this falls into the category of solution quality. It is key that a solver is reliable and provides a high quality solution. This is why I find mathematical solvers so appealing, since the optimality gap gives an unambiguous metric for the quality. $\endgroup$
    – Richard
    Commented Aug 7, 2020 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.