idea
After some meditation I was able to improve the lower bound considerably.

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.

Cheers Rolf

( addicted to the Perl Programming Language)

¹) 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]

In reply to Re: Travelling problem (lower bound >= 79593) (+ example) by LanX
in thread Travelling problem by Dirk80

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.