Bug in distance calculation from flattened matrix about vrplib HOT 5 CLOSED

Hi @leonlan,
Just for reference: The original distance matrix for E-n13-k4 can be found in the paper of Dantzig and Ramser, Table 1 page 82. (https://andresjaquep.files.wordpress.com/2008/10/2627477-clasico-dantzig.pdf)
You can check the mentioned discrepancy between cvrplib distance matrix and original distance matrix.

from vrplib.

Hi @wgfiis, thanks for reporting the bug! I'm going to investigate it further in the new year and make sure it's fixed in V1 #18.

from vrplib.

The problem here is mainly with the way that the matrix in E-n13-k4 is given.

NAME : E-n13-k4
EDGE_WEIGHT_TYPE : EXPLICIT
EDGE_WEIGHT_FORMAT: LOWER_ROW 
(...)
EDGE_WEIGHT_SECTION
     9    14    21    23    22    25    32    36    38    42
    50    52     5    12    22    21    24    31    35    37
    41    49    51     7    17    16    23    26    30    36
    36    44    46    10    21    30    27    37    43    31
    37    39    19    28    25    35    41    29    31    29
     9    10    16    22    20    28    30     7    11    13
    17    25    27    10    16    10    18    20     6     6
    14    16    12    12    20     8    10    10
(...)
EOF

This array of numbers corresponds to the lower triangle of the distances matrix. Since it's not formatted like that, I assumed that this should be first put in an 1-D array, and then each element of the array corresponds to some index of the lower triangle matrix.

The TSPLIB specification describes the EXPLICIT_MATRIX edge weight type with LOWER_ROW edge weight format as:

Lower triangular matrix (row-wise including diagonal entries)

This reads as if the matrix should be parsed per row, so the entries are supposed to be parsed in order (1, 0), (2, 0), (2, 1), (3, 0), etc. But, as shown in the paper, the E-n13-k4 instance is parsed in order of columns instead.

Fortunately, I'm pretty sure this is the only edge case that needs to be parsed like this. But I need to double check this.

I'll think a bit about what I'll do here to fix this edge case!

from vrplib.

Alright, thank you. The E-n13-k4 was indeed the only instance I encountered this bug.

from vrplib.

@wgfiis Thanks for reporting this. I'll close this issue because it's a problem with the CVRPLIB and the instance they have provided. But I'll send them a message about it and ask if they can change it.

from vrplib.