Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Bug in distance calculation from flattened matrix #40

Closed
Tracked by #18
wgfiis opened this issue Dec 6, 2022 · 5 comments
Closed
Tracked by #18

Bug in distance calculation from flattened matrix #40

wgfiis opened this issue Dec 6, 2022 · 5 comments
Labels
wontfix This will not be worked on

Comments

@wgfiis
Copy link

wgfiis commented Dec 6, 2022

Just found a bug in the distance calculation from flattened distance matrices.
The function 'from_flattened' (line 141 in cvrp.py) assumes that
" The numbers in a flattened list correspond the matrix element indices
(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), ..."
However, for the instance E-n13-k4 the flattened list correponds to indices
(0, 1), (0, 2), (0, 3), (0, 4), ... (11,12).
Changing line 150
indices = sorted([(i, j) for (j, i) in combinations(range(n), r=2)])
to
indices = sorted([(i, j) for (i, j) in combinations(range(n), r=2)])
resolves this issue.
However, I do not know whether the original sorting might be correct for some other instances.

@leonlan leonlan added the bug Something isn't working label Dec 6, 2022
@leonlan
Copy link
Member

leonlan commented Dec 6, 2022

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.

@leonlan leonlan mentioned this issue Dec 6, 2022
6 tasks
@wgfiis
Copy link
Author

wgfiis commented Dec 6, 2022

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.

@leonlan
Copy link
Member

leonlan commented Jan 12, 2023

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!

@wgfiis
Copy link
Author

wgfiis commented Jan 12, 2023

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

@leonlan
Copy link
Member

leonlan commented Feb 1, 2023

@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.

@leonlan leonlan closed this as completed Feb 1, 2023
@leonlan leonlan added wontfix This will not be worked on and removed bug Something isn't working labels Feb 1, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
wontfix This will not be worked on
Projects
None yet
Development

No branches or pull requests

2 participants