Question about testing ATSP

[wzever]

Thank you for the insightful work! I have questions when running the ATSP solver, i.e., the GLOP-empowered MatNet to evaluate more ATSP instances:

1. There seems mismatch between the output tour and cost of your random insertion algorithm. I replace the result with manually calculated cost from the tour (to my conventional understanding) and find them different (specifically the following printed cost1 and cost2 are different. Based on eval_atsp/test_glop.py), though the improved amount remain almost stable.

def calc_len(tour, dist):
    cost = 0
    tour = tour.tolist()
    tour.append(tour[0])
    assert sorted(tour[:-1]) == [i for i in range(len(dist))], tour
    for i in range(len(tour) - 1):
        cost += dist[tour[i], tour[i + 1]]
    return cost

def main(n):   
    ...
    for inst in dataset:
        tour, cost = random_insertion_non_euclidean(inst, order)
        print(f'cost1: {cost}')

        cost = calc_len(tour, inst).item()
        print(f'cost2: {cost.item()}')

        original_costs.append(cost)
        improved_cost = revision(torch.tensor(tour.astype(np.int64)), inst, tester)
        revised_cost = cost - improved_cost
        revised_costs.append(revised_cost) 
    ...

Here are the outputs on ATSP150 using the two different original costs, with all other setting and data identical to your instructions.

Using cost1 (which matches the reported results in Table 4 of your paper)
initial costs:  2.2909360318757233
revised costs:  1.8663635640717682
improvement:  0.4245724678039551

Using cost2
initial costs:  4.3610200643539425
revised costs:  3.966040094693502
improvement:  0.3949799696604406

I checked your Cpp code of RI algorithm and find it somewhat complicated with the part of calculating total distance, thus wondering if there's any important design that I miss in either your implementation or the paper that may cause the above discrepancy.

2. Could you please further explain the modelling scheme you implemented for equivalent ATSP of each ASHPP (Line 134-139 in eval_atsp/test_glop.py)? Because I find the result changes as I adjust L. So, should I change the value of L for my customized evaluation on different problem sizes/distributions? And how can I get a complete revised tour upon the MatNet-solved sub-results, for better clarity and reliability of evaluation?

L = 1.5
for sub_inst in sub_insts: # equivalent ATSP of each ASHPP
    sub_inst[:, 0] += L
    sub_inst[:, -1] += L
    sub_inst[0, :] += L
    sub_inst[-1, :] += L
    sub_inst[0, 0] = sub_inst[0, -1] = sub_inst[-1, 0] = sub_inst[-1, -1] = 0

Thanks again! Looking forward to your reply.

[Furffico]

Hi, @wzever! Thank you for your interest in our paper.

In terms of Q1, unfortunately it turned out to be a bug in my code for random insertion. (Sorry for the messy code. 😣) We are still evaluating its impact on the results reported in our paper. As for now, I'm sure that only the ATSP results (Table 4) can be affected by the bug.
I have just published a bugfix in the insertion-bugfix branch. You may recompile insertion.so and try testing with the fixed version of our code. (I don't have the environment for compiling and testing yet, but I'll do it ASAP.) It won't be difficult to see what happened from the comparison here. I can also explain it later if you need.

[henry-yeh]

Regarding the modeling scheme for the equivalent ATSP of each ASHPP.

We define the ATSP as follows:

• The first node is the starting node of SHPP, and the last node is the terminating node of SHPP.
• The starting and terminating nodes are (1) placed very far from the rest of the nodes and (2) placed very close to each other. This ensures that in any reasonable solution to the equivalent ATSP, the starting and terminating nodes are connected.
• The optimal solution to the ATSP defined above is also the optimal solution to the original ASHPP.

You can also refer to how POPMUSIC utilizes the above modeling scheme to solve its subproblems [1].

In this case, L shouldn't influence the results as long as (1) L is large enough and (2) the neural model well generalizes.

[1] POPMUSIC for the travelling salesman problem

[henry-yeh]

We are fixing the bug, and we anticipate better performance after that.

[wzever]

Thanks for your prompt response and helpful explanation. Anticipating your updates!

[henry-yeh]

We have fixed the bug and now the function returns the complete revised tour. Thank you @wzever !