This bound is not very good, specially considering that most (if not all) data sets we currently have contain a 0 cost between 2 cities. Nevertheless, the idea is to start with something really simple and improve it overtime.
This bound works by relaxing the constraints:
we get the smallest path between 2 cities
we ignore that a path may not be repeated within the solution (relaxation of the constraints)
we multiply that smallest path by the number of cities (eg. dimension)
The idea is that the best possible solution will never be better than all cities having the shortest path among all of the possible paths.
In the future we can implement the bound discussed in class:
get shortest incoming path (for every city)
get shortest outgoing path (for every city)
perform necessary calculations
This was created based on the changes of #23, it should be merged before this PR.
This bound is not very good, specially considering that most (if not all) data sets we currently have contain a 0 cost between 2 cities. Nevertheless, the idea is to start with something really simple and improve it overtime.
This bound works by relaxing the constraints:
dimension)The idea is that the best possible solution will never be better than all cities having the shortest path among all of the possible paths.
In the future we can implement the bound discussed in class:
This was created based on the changes of #23, it should be merged before this PR.
Closes #24