Type hierarchy for TSP instances?

General Usage
1

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 TSPInstance type(s) contain fields indicating instance attributes. E.g. a field like issymmetric::Bool and define is_sym_instance(p::TSPInstance) = p.issymmetric. Then a user-facing function like solve_tsp can 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 <: AbstractTSPInstance and GeneralTSPInstance <: AbstractTSPInstance. Then define heuristic methods, as appropriate, for specialized types, and solve_tsp doesn’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?

1 Like
2

Then don’t use it. It is also Julian to write a simple user-facing API for a polyalgorithm, eg that’s how \(::Matrix, ::Matrix) & friends are implemented. The internal functions called by this can be type-stable, and heavily optimized for some special cases, and it will work fine.

I know little about the TSP, but given your description, I would just

  1. store the relevant information in slots of a struct that has enough information to select the relevant specialized algorithm, or generate it on demand if that is an alternative (eg checking symmetry),
  2. implement those algorithms in separate functions,
  3. have a user-facing function (eg solve_tsp) select the relevant one.

In general, I think that concocting elaborate parametric type hierarchies is something that most Julia users go through at some point as part of the learning process, then realize that it is more of a constraint without any benefits. I regret most instances of doing something like this, and go back to duck typing when I refactor code, mostly keeping the types when I need them for dispatch.

1 Like
3

A third way might be to define traits, that can apply to multiple (sub)types? That way, one is not bound to a tree structure, but does not have to specify the attributes per instance, only per instance-type.

2 Likes