# Method to check goodness of combinatorial optimization algorithm implementation

How do I check which algorithm solves my problem best?

Given a optimaization problem, I apply different well known optimization algorithms (genetic algorithm, simulated annealing, ant colony etc.) to solve my problem. However, how do I know if my implementation ( e.g. cost function) is working for every case? How can I compare the algorithms or their goodness in the context of my problem?

This is a very large question that could be answered in a variety of ways depending on the context.

For some optimization problems operating under specific conditions you can make theoretical guarantees that your optimization will solve your problem. A specific example of this is running the gradient descent algorithm on a convex function. If the function being optimized is convex then gradient descent is guaranteed to converge to the correct solution. Given the nice properties of convex functions, there are many types of optimization where you can make these theoretical guarantees.

When evolutionary algorithms (and many non-derivative based optimizations) are run, it's much harder to make these types of guarantees. Often in the literature I've seen people try their functions on several baseline optimization functions and report back the minimum or maximum found. Many of these are included in Facebook's nevergrad optimization library to be used for evaluation. An example of one of these functions is included below, Even if you can prove that your algorithm minimizes several objective functions you could be testing on, there could be other properties that should be considered. Some of these include the following: the speed at which the algorithm converges; the number of evaluations of the objective function (if not closed form), and even the amount of space in memory which is required for your optimization. All of these (and many more) factors could come into play when evaluating your algorithm.

Scientists may use functions like this one to evaluate their optimization and compare it to other algorithms that are similar. To answer your final question though, "How can I see if my optimization works for every problem", I would say that's a bit of a loaded question. Most of the time these optimizations need some sort of constraint to make a generalized guarantee. I would look at the constraints of your problem and go from there.

If you're interested, here's a good paper that goes much more in depth than I did here.