Quadratic Traveling Salesman Problem

[Neng-Fa Zhou]

During the tutorial at CP'24, Christopher Beck gave an interesting exercise, called QTSP. Here is my first attempt to model it using Picat's planner. The model is only illustrative, and can only handle small graphs. A heuristic could be introduce in order for it to handle middle-sized graphs.

Cheers,

Neng-Fa

/*
  A solution in Picat to the Quardratic Traveling Salesperson Problem, finding a cost minimal
  tour where the costs are associated to each triple of nodes that is traversed in succession.

  An exercise given by J Christopher Beck during his tutorial at CP'24.
*/

import planner, ordset.

main =>
    instance(Graph),
    N = length(Graph),   % number of nodes in Graph
    cl_facts(Graph,$[node(+,-)]),
    minof(search_plan(N,Plan,Cost),Cost),
    writeln(Plan),
    writeln(Cost).

search_plan(N,Plan,Cost) =>
    node(1, Arcs),
    member((V,ECostFrom1),Arcs),          % find the first edge
    Us = delete(2..N, V),                 % Us = unvisited vertices
    best_plan_unbounded({ECostFrom1,ECostFrom1,V,Us},Plan,Cost).
   
final({_,_,1,[]}) => true.

action({ECostFrom1,PreECost,V,[]}, NState, Action, Cost) =>
    NState = {ECostFrom1,ThisCost,1,[]},
    Action = (V,1),
    node(V,Neibs),
    member((1,ThisCost),Neibs),
    Cost is ECostFrom1+ThisCost.

action({ECostFrom1,PreECost,V,Us}, NState, Action, Cost) =>
    NState = {ECostFrom1,ThisCost,NextV,UsR},
    Action = (V,NextV),
    node(V,Neibs),
    member((NextV,ThisCost),Neibs),
    select(NextV,Us,UsR),
    Cost = PreECost+ThisCost.

instance(Graph) =>
    Graph = $[node(1,[(2,4),(5,7),(3,8),(4,10),(6,14),(7,15)]),
              node(2,[(1,4),(7,5),(3,7),(4,7),(5,10),(6,12)]),
              node(3,[(4,4),(5,6),(2,7),(1,8),(6,8),(7,10)]),
              node(4,[(5,2),(3,4),(6,5),(2,7),(7,8),(1,10)]),
              node(5,[(4,2),(3,6),(6,6),(1,7),(7,7),(2,10)]),
              node(6,[(4,5),(7,5),(5,6),(3,8),(2,12),(1,14)]),
              node(7,[(2,5),(6,5),(5,7),(4,8),(3,10),(1,15)])].