December 22, 2014 at 11:20Solving the traveling salesman problem using the branch and bound method
Hello, Habr! Implementing various algorithms for finding the least-cost Hamiltonian cycle, I came across a publication offering its own version. After trying in practice, I got the wrong answer:
Further searches on the Internet did not bring the expected result: either a complicated theoretical description for non-mathematicians, or an understandable one, but with errors.
Under the cut you will be waiting for the corrected algorithm and online calculator.
The method itself, published by Little, Merty, Sweeney, Carel in 1963, is applicable to many NP-complete problems, and is a very theorized material, which without good knowledge of English and mathematics cannot be immediately applied to our traveling salesman problem.
Briefly about the method - this is a complete enumeration of all possible options with a screening of clearly non-optimal solutions.
There was only one mistake - one should choose a set with a minimum boundary from among all possible paths for splitting, and not from two children resulting from the last splitting.
And here is the solution with the corrected algorithm:
Answer: path: 3 => 4 => 2 => 1 => 5 => 3 length: 41
As you can see, including the 5: 2 edge in the solution will be an error. As required, the
graph Comparison of the branches and borders method and the time spent for a random table from 5x5 to 10x10: The
graph of the maximum and minimum time spent for matrices from 5x5 to 66x66.
You can try with a detailed solution here .
measurement data were obtained from 100 random matrices. not too good a number, but a general idea provides.
Sources on GitHub (updated).
Further searches on the Internet did not bring the expected result: either a complicated theoretical description for non-mathematicians, or an understandable one, but with errors.
Under the cut you will be waiting for the corrected algorithm and online calculator.
The method itself, published by Little, Merty, Sweeney, Carel in 1963, is applicable to many NP-complete problems, and is a very theorized material, which without good knowledge of English and mathematics cannot be immediately applied to our traveling salesman problem.
Briefly about the method - this is a complete enumeration of all possible options with a screening of clearly non-optimal solutions.
Corrected algorithm to find a truly minimal route
1. Calculate the smallest element in each row (cast constant for the row)
2. Go to the new cost matrix by subtracting its cast constant from each row
3. Calculate the smallest element in each column (cast constant for the column)
4. Go to the new cost matrix Subtracting from each column its constant of reduction.
As a result, we have a cost matrix in which in each row and in each column there is at least one zero element.
5. We calculate the boundary at this stage as the sum of the reduction constants for the columns and rows (this boundary will be the value less than which it is impossible to construct the desired route)
1. Calculation of the penalty for non-use for each zero element of the reduced cost matrix.
The penalty for not using an element with index (h, k) in the matrix means that this edge is not included in our route, which means that the minimum cost of not using this edge is the sum of the minimum elements in row h and column k.
a) We are looking for all zero elements in the given matrix
b) For each of them we consider its penalty for non-use.
c) Choose an element that corresponds to the maximum penalty (any, if there are several)
2. Now we divide our set S into sets containing the edge with the maximum penalty (S w ) and not containing this edge (S w / o ).
3. The calculation of cost estimates for routes included in each of these sets.
a) For the set S w / o, everything is simple: since we do not take the corresponding edge with the maximum penalty (h, k), then for it the cost estimate is equal to the cost estimate of the set S + penalty for not using the edge (h, k)
b) When calculating of costs for the set S w, we take into account that since the edge (h, k) enters the route, then the edge (k, h) cannot enter the route, therefore we write c (k, h) = infinity in the cost matrix, and since we have already “left” point h and “already arrived” at point k, then no edge coming out of h, and not one edge coming in k can be used, therefore we delete from cost matrices row h and column k. After that, we present the matrix, and then the cost estimate for S wequal to the sum of the cost estimates for S and r (h, k), where r (h, k) is the sum of the reduction constants for the changed cost matrix.
4. Of all the non-broken sets, one that has the smallest estimate is chosen.
So we continue until in the matrix of expenses there is not one crossed out row and one not crossed out column.
Small optimization - connect heuristics
Yes, true, why don't we introduce heuristics? Indeed, in the algorithm of branches and borders, we actually build a tree at whose nodes we decide to take an edge (h, k) or not, and hang two children - Sw (h, k) and Sw / o (h, k). But the best option for the next iteration is selected only by assessment. So let's choose the best not only by assessment, but also by depth in the tree, because the deeper the selected item, the closer it is to the end of the count. Thus, we can finally wait for an answer.
The algorithm consists of two stages:
First stage
Bringing the cost matrix and calculating a lower estimate of the cost of the route r.
1. Calculate the smallest element in each row (cast constant for the row)
2. Go to the new cost matrix by subtracting its cast constant from each row
3. Calculate the smallest element in each column (cast constant for the column)
4. Go to the new cost matrix Subtracting from each column its constant of reduction.
As a result, we have a cost matrix in which in each row and in each column there is at least one zero element.
5. We calculate the boundary at this stage as the sum of the reduction constants for the columns and rows (this boundary will be the value less than which it is impossible to construct the desired route)
The second (main) stage
1. Calculation of the penalty for non-use for each zero element of the reduced cost matrix.
The penalty for not using an element with index (h, k) in the matrix means that this edge is not included in our route, which means that the minimum cost of not using this edge is the sum of the minimum elements in row h and column k.
a) We are looking for all zero elements in the given matrix
b) For each of them we consider its penalty for non-use.
c) Choose an element that corresponds to the maximum penalty (any, if there are several)
2. Now we divide our set S into sets containing the edge with the maximum penalty (S w ) and not containing this edge (S w / o ).
3. The calculation of cost estimates for routes included in each of these sets.
a) For the set S w / o, everything is simple: since we do not take the corresponding edge with the maximum penalty (h, k), then for it the cost estimate is equal to the cost estimate of the set S + penalty for not using the edge (h, k)
b) When calculating of costs for the set S w, we take into account that since the edge (h, k) enters the route, then the edge (k, h) cannot enter the route, therefore we write c (k, h) = infinity in the cost matrix, and since we have already “left” point h and “already arrived” at point k, then no edge coming out of h, and not one edge coming in k can be used, therefore we delete from cost matrices row h and column k. After that, we present the matrix, and then the cost estimate for S wequal to the sum of the cost estimates for S and r (h, k), where r (h, k) is the sum of the reduction constants for the changed cost matrix.
4. Of all the non-broken sets, one that has the smallest estimate is chosen.
So we continue until in the matrix of expenses there is not one crossed out row and one not crossed out column.
Small optimization - connect heuristics
Yes, true, why don't we introduce heuristics? Indeed, in the algorithm of branches and borders, we actually build a tree at whose nodes we decide to take an edge (h, k) or not, and hang two children - Sw (h, k) and Sw / o (h, k). But the best option for the next iteration is selected only by assessment. So let's choose the best not only by assessment, but also by depth in the tree, because the deeper the selected item, the closer it is to the end of the count. Thus, we can finally wait for an answer.
Now, actually, about the errors in that publication
There was only one mistake - one should choose a set with a minimum boundary from among all possible paths for splitting, and not from two children resulting from the last splitting.
Evidence
Let's go back to the picture at the beginning of the post:
And here is the solution with the corrected algorithm:
Answer: path: 3 => 4 => 2 => 1 => 5 => 3 length: 41
As you can see, including the 5: 2 edge in the solution will be an error. As required, the
graph Comparison of the branches and borders method and the time spent for a random table from 5x5 to 10x10: The
graph of the maximum and minimum time spent for matrices from 5x5 to 66x66.
You can try with a detailed solution here .
measurement data were obtained from 100 random matrices. not too good a number, but a general idea provides.
Sources on GitHub (updated).
