0 cost solution

[raunakbh92]

The following adjacency matrix results in a solution that has 0 cost and is inconsistent with allowed connections in the graph.

6×6 Matrix{Int64}:
   0  153  151    0    0    0
 153    0    0  147    0    0
 151    0    0  152  147    0
   0  147  152    0    0  152
   0    0  147    0    0  152
   0    0    0  152  152    0

Here is the resulting solution:

opt_tour, opt_len = solve_tsp(M)
([1, 6, 3, 2, 5, 4], 0)

[chkwon]

0 means cost is zero. The input is the cost matrix, not the adjacency matrix. So use a large number for those links not connected.

[raunakbh92]

Yes, that seemed to work. Thank you for the prompt response. I will close this issue now.

[raunakbh92]

As a follow up, is there a guidance on how large the number should be for the links that are not connected? For example, for a 6 node problem, the following cost matrix results in the solver not returning any solution (it kept running overnight).

6×6 Matrix{Int64}:
        0       153       151  10000000  10000000  10000000
      153         0  10000000       147  10000000  10000000
      151  10000000         0       152       147  10000000
 10000000       147       152         0  10000000       152
 10000000  10000000       147  10000000         0       152
 10000000  10000000  10000000       152       152         0

A smaller value of 10000 for the unconnected links ended up giving a result within less than a second.

However, for a bigger problem involving 12 nodes, if I use a cost of 10000, the resulting solution is quick (less than a second) but incorrect (involves an edge that actually is unconnected in the original problem). However, if I use a larger cost (10^7), the solver again does not finish executing.

So, for the unconnected links, I need to use a cost that is high but not too high. Could you please suggest how to go about that?

[chkwon]

If

C = [    
          0  153  151    0    0    0;
        153    0    0  147    0    0;
        151    0    0  152  147    0;
          0  147  152    0    0  152;
          0    0  147    0    0  152;
          0    0    0  152  152    0
]

I believe your big constant could be M = Int(sum(C)/2).

[raunakbh92]

Thank you for the suggestion. However, it still does not seem to work. As an example, here is the original matrix 20x20:

[[0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0]]

According to your guidance above, the big constant is 23 so I replaced the 0 with 23. The resulting matrix is

20×20 Matrix{Int64}:
 23   1  23  23   1  23  23  23  23  …  23  23  23  23  23  23  23  23  23
  1  23   1  23  23  23  23  23  23     23  23  23  23  23  23  23  23  23
 23   1  23   1  23  23  23  23  23     23  23  23  23  23  23  23  23  23
 23  23   1  23  23  23  23   1  23     23  23  23  23  23  23  23  23  23
  1  23  23  23  23   1  23  23   1     23  23  23  23  23  23  23  23  23
 23  23  23  23   1  23   1  23  23  …  23  23  23  23  23  23  23  23  23
 23  23  23  23  23   1  23   1  23     23  23  23  23  23  23  23  23  23
 23  23  23   1  23  23   1  23  23      1  23  23  23  23  23  23  23  23
 23  23  23  23   1  23  23  23  23     23   1  23  23  23  23  23  23  23
 23  23  23  23  23  23  23  23   1     23  23  23  23  23  23  23  23  23
 23  23  23  23  23  23  23  23  23  …   1  23  23  23  23  23  23  23  23
 23  23  23  23  23  23  23   1  23     23  23  23  23   1  23  23  23  23
 23  23  23  23  23  23  23  23   1     23  23   1  23  23   1  23  23  23
 23  23  23  23  23  23  23  23  23     23   1  23   1  23  23  23  23  23
 23  23  23  23  23  23  23  23  23     23  23   1  23   1  23  23  23  23
 23  23  23  23  23  23  23  23  23  …   1  23  23   1  23  23  23  23   1
 23  23  23  23  23  23  23  23  23     23   1  23  23  23  23   1  23  23
 23  23  23  23  23  23  23  23  23     23  23  23  23  23   1  23   1  23
 23  23  23  23  23  23  23  23  23     23  23  23  23  23  23   1  23   1
 23  23  23  23  23  23  23  23  23     23  23  23  23   1  23  23   1  23

However, the tsp solution is

([1, 15, 14, 13, 17, 18, 19, 20, 16, 12, 11, 10, 9, 5, 6, 7, 8, 4, 3, 2], 42)

The edge from 1,15 should not exist as the world does not allow diagonal edges and only aisles.

[chkwon]

I think for a given example, it is impossible to traverse all vertices without using diagonal edges. Please check again.

[raunakbh92]

Thank you for your help and guidance. However, diagonal edges are not allowed.

The figure below shows the nodes and the allowed edges including the distance between the nodes (the cost matrix in my previous post above represents this, I have just rounded the distances to ensure the cost matrix has integer values).

I want to find a TSP solution for this problem. As you can see, diagonal edges are not allowed in the problem so I need my TSP solution to also not give any diagonal edges. Could you please suggest how to proceed?

[chkwon]

In TSP, each node can only be visited exactly once. In your example, it is impossible to visit all nodes exactly once. If visiting each node multiple times is allowed, you may need to reformulate your problem somehow, which I'm not sure how.

Since this is not related to the package, I'll close the issue. You may seek help for solving your problem from https://or.stackexchange.com

[chkwon]

If you are open to use optimization solvers like CPLEX, Gurobi, or Cbc, you can introduce dummy nodes to represent multi-visits and formulate the problem as a mixed-integer programming problem as done in the vehicle routing problem (VRP) literature. Manual formulations and coding will be necessary. I don't think there exists any package solves your problem in particular.