Skip to content

Inconsistent behavior for EXACT and FLOOR distance types compared to LKH conventions #11

@CarlossShi

Description

@CarlossShi

According to LKH's TYPE conventions (e.g., see LKH3/SRC/ReadProblem.c):

 * CEIL_2D      Weights are Euclidean distances in 2-D rounded up
 * CEIL_3D      Weights are Euclidean distances in 3-D rounded up
 * EUC_2D       Weights are Euclidean distances in 2-D
 * EUC_3D       Weights are Euclidean distances in 3-D
 * EXACT_2D     Weights are EUC_2D distances (SCALE = 1000 as default)
 * EXACT_3D     Weights are EUC_3D distances (SCALE = 1000 as default)
 * EXPLICIT     Weights are listed explicitly in the corresponding section
 * FLOOR_2D     Weights are Euclidean distances in 2-D rounded down
 * FLOOR_3D     Weights are Euclidean distances in 3-D rounded down

Given these definitions, the expected behavior for EXACT and FLOOR types should be something like:

exact = lambda start, end: utils.nint(math.dist(start, end) * 1000)
distances.TYPES.update({
    'EXACT_2D': exact,
    'EXACT_3D': exact,
	'FLOOR_2D': functools.partial(euclidean, round=math.floor),
	'FLOOR_3D': functools.partial(euclidean, round=math.floor),
})

However, the current implementation appears to differ from these expectations:

pylkh/lkh/problems.py

Lines 7 to 12 in 1f3bfb4

distances.TYPES.update({
'EXACT_2D': math.dist,
'EXACT_3D': math.dist,
'FLOOR_2D': distances.euclidean,
'FLOOR_3D': distances.euclidean,
})

My opinions:

  • For EXACT type, trully there's needs to define a type to handle nodes within unit square, but different behaviors on EXACT type may cause inconsistent results and confusion.
  • For FLOOR type, the default round function of euclidean - tsplib95/distances.py is utils.nint - tsplib95/utils.py, which I think behaviors like standard rouding, not floor.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions