It’s time to give my neglected Traveling Salesman problem package some attention. One of the biggest issues: right now, all TSP problem instances are specified by a dense distance matrix, and no heuristics take advantage of problem specific structure.
I’d like to create one or more
TSPInstance types which contain information about the properties of the given instance, e.g. whether the problem is symmetric, metric, Euclidean, etc. Broadly I see two ways to do this:
- Have the
TSPInstancetype(s) contain fields indicating instance attributes. E.g. a field like
is_sym_instance(p::TSPInstance) = p.issymmetric. Then a user-facing function like
solve_tspcan do something like
if is_sym_instance(p) tsp_solution = _symmetric_heuristic(p) else tsp_solution = _generic_heuristic(p) end
- Use the type system more aggressively. Have
SymmetricTSPInstance <: AbstractTSPInstanceand
GeneralTSPInstance <: AbstractTSPInstance. Then define heuristic methods, as appropriate, for specialized types, and
solve_tspdoesn’t need to explicitly check the properties of a problem instance; dynamic dispatch takes care of that.
The second solution feels more Julian, but my concern is that the relevant attributes of TSP problem instances don’t naturally fit into a tree structure, which the type system enforces. For example, we might have big, medium, and small instances, symmetric/metric/Euclidean instances, nonnegative instances, etc. Creating a concrete type for each possible combination of instance attributes would seem to require a large number of types.
So, any suggestions for an elegant/idiomatic way to attach attributes to a TSP instance type without requiring a huge and intricate type hierarchy?