The call-change problem is an instance of the symmetric, non-Euclidean travelling salesman problem.
The travelling salesman problem is a well known problem in computer science: what is the shortest circular tour between a set of cities, where every city is visited exactly once. There are many slight variations of the travelling salesman problem, in this case non-Euclidean means that although we know the distances between each city (target row), it is not necessarily possible to lay all the cities (target rows) on a plane. In other words, we cannot give a Cartesian coordinate for each city. Symmetric means that the distance from A to B is the same as the distance from B to A.
Neither of these have any bearing on the fact that the problem is NP-complete. Essentially, the only way to guarantee to find the best solution is to try all possible combinations.
The implication of this is that once the scale of the problem gets beyond
trivial, then the time taken to search all possibilities becomes infeasibly large. Indeed, even for a small number of 'cities', the execution time to explore all possible tours would be more load the would be sensible to place on a web server.
Still, all is not in vain. One approach is to not aim to guarantee to find the best solution, but just to find a good solution. There has been a vast amount of
research into finding good heuristics for the travelling salesman problem. Heuristic solutions can be executed in much shorter times and although they
cannot guarantee to find the best solution, modern heuristic algorithms very often do find the best solution.
Further, because there are many very good heuristics, all of which run very quickly, it is feasible to execute several algorithms, calculate several tours and choose the best. This is exactly what the Call Change composer does.
The first stage in the program is to provide a mapping from the call change problem to the travelling salesman problem. This is very simple to do using an equation based on one I posted to the CR mailing list. The result is the distance matrix which can be displayed by selecting that option in the program interface.
Internally, the program uses tsp_solve, a program by Chad Hurwitz (please see here
for contact details) which uses a number of heuristic solvers and picks
the best result. From the examples I have tested, it seems that the heuristics do actually find the best solution in the call-change problem.