TSP in OML (MS Solver Foundation)

In theory it is easy to formulate a TSP when the all-different constraint is present. Let x[i] be the i^th city visited, an OML-like formulation could look like:

Model[

  Parameters[Integers,N=14],

  Parameters[Sets[Integers],city],

  Parameters[Reals,dist[city,city]],

  Decisions[Integers[0,N-1],x[city]],

  Constraints[

     Unequal[Foreach[{i,city},x[i]]]

  ],

  Goals[

    Minimize[Sum[{i,city},dist[x[i],x[i++1]]]]

  ]

]

This does not work completely. First, bounds can not contain a symbolic constant. Yuck: we need to write [0,13] as bounds:  Decisions[Integers[0,13],x[city]]. The objective has  a few more difficulties. There is no circular lead/lag operator in OML (like the -- or ++ operator in GAMS).  This can be solved by introducing a parameter next[city]. This can be calculated in Excel and imported in the OML model. Furthermore, we cannot use a variable as an index, so dist[x[i],x[next[i]]] is not a valid construct (some languages geared towards solving CSP problems allow this; it adds concise expressiveness to the language that may help the modeler). The error message indicates this is not related to OML per se but rather to solver support. Also it is not allowed to use something like FilteredSum[{j,city},j==x[i],...] (a condition in a FilteredSum cannot depend on a decision variable). The only thing I could think of was:

Minimize[Sum[{i,city},{j,city},{k,city},AsInt[j==x[i]]*AsInt[k==x[next[i]]]*dist[j,k]]]

Note that I used integers as set elements. I started with using data-binding through tables, using set elements {'city0','city1',...,'city13'}. This made the model somewhat more complicated, as x[i] is an integer. So the CSP formulation uses the simpler set {0,1,...,13} allowing us to operate on indices. (Some consider this bad modeling: in GAMS arithmetic on sets is actually discouraged, and needs a function ord()to convert the element — always a string in GAMS — to an integer). Unfortunately I was not able to solve the small 14 city example with the CSP solver using this formulation. (Even after adding City[0]==0 as constraint). To check the input, I also tried a MIP formulation with Gurobi. That solved this small instance just fine.

In the MIP formulation we needed to formulate:

FilteredSum[{i,city},i != 'city0', x['city0',i]]==1

From what I can see this is not possible: a set element not being an integer can not be used in OML. As a workaround I created sets by binding to some dummy parameters:

Sum[{i0,city0},{i,city2},x[i0,i]]==1

where city0 is a set containing only a single element 'city0', and city2 is a set {'city1',...,'city13'}.  The constraint

FilteredSum[{i,city},{j,city},i != j,x[i,j]] <= N

did not work as i and j are not numeric. A workaround could be to have a parameter num[city] which can be calculated in Excel and then imported. Then the condition can read: num[i]!=num[j]. I just used dist[i,j]>0 as condition, as that also can be used to exclude the diagonal (the Excel spreadsheet makes sure all diagonal distances dist[i,i] are zero). A more general approach would be to be able to introduce sparse 2-d sets (like one could do in AMPL and GAMS), but OML has only one dimensional sets as far as I know.

This exercise was really meant to explore the expressiveness of OML. The little model actually shows some interesting issues with OML and some possible workarounds. I do not want to suggest this is a good way to solve TSP's. Obviously these approaches are not suited for large problems. A cutting plane algorithm often is quite effective for slightly larger problems (see this 42 city problem). The excel plugin does not allow us to to implement such an algorithm: an OML model can only contain a single model and has no looping facilities. For the real large problems, you need to look elsewhere, such as Concorde.