idea

The idea is simple, in an undirected graph each edge appears twice in the incidence matrix.²

Taking the OP's data structure that means 2 values from each row¹!

Except the first and the last row, since it's not a closed Hamilton circle (otherwise we would additionally have an edge (0,23) (or (23,0) respectively) to close the path )

So if we sum up all these values we get exactly the double of the path length. (see also Double_counting_(proof_technique))

So taking the first and second shortest edge, we can estimate for each inner row

edge1 + edge2 >= shortest1 + shortest2

for the start and stop row we get edge1 >= shortest1

Including shortest2 improves the bound considerably and we get 79592.5.

That is an optimal solution must be bigger or equal 79593

code

here the code if someone needs to reproduce it:

sub lower_bound1 {
  my @sorted;
  for my $idx ($start..$stop) {
    my $x=0;
    my @order = sort { $a->[1] <=> $b->[1] } map { [$x++,$_] } @{ $dat
+a[$idx] };
    push @sorted,\@order;
  }
  #pp \@sorted;
  my $min=0;
  for my $idx ($start..$stop) {
    my $shortest1=$sorted[$idx][1][1];         # 1. shortest
    my $shortest2=$sorted[$idx][2][1];         # 2. shortest
    $min+=$shortest1;
    unless ($idx==$start or $idx == $stop) {
      $min+=$shortest2;
    }
    #pp $min,$shortest1,$shortest2, $sorted[$idx];
  }
  return $min/2;
}
[download]

I hacked also a lower_bound2() routine taking advantage of more constraints, but this didn't improve the result that much (about 150). I doubt that this complicated approach is of much interest.

what for

Good lower bound estimations are important to cut of subtrees in branch-and-bound algorithms!

If you know that e.g. the remaining 22 edges have a length of at least 76000 and you know already a temporary optimum of 84000, it doesn't worth it to check starting edges of length 8000 or more. And so on.

Since for each generation differences to the rows shortest sum up, the possible subtree get constantly smaller and a full solution comes into reach.

immediate consequence

The OP's specific problem is not a very hard example of the TSP.

hdb was able to produce a temporary solution of 84860 within 30 seconds, which is how we know now within a 5% margin of the optimum, if not already the optimum.

For practical use this is more than acceptable.

¹) starting indexing with 0

update

²) contrived example

     0    1    2    3    4      min1          min2
0    0    1   (2)   3    1      1                
1    1    0  (10)  (7)   1      1+1           10+7 
2   (2) (10)   0   15    3      2+3          10+15
3    3   (7)  15    0   (2)     2+3           7+15
4    1    1    3   (2)   0      1                
                             
shortest0-4:     length:21
0--2--1--3--4
  2 10  7  2   

lower_bound1: sum(min1)/2  =  14/2  =  7

lower_bound2: 19 = sum(min2)/2 - 15 + 1 + 1
   (excluding col 0 and 4 for double rows, striking the maximum)
[download]