The previous two types of problems were similar in that the decisions for each involved either setting/selecting a variable or not. In this section, we consider the traveling salesman problem (TSP) in which we have a graph with weighted edges. We can think of the nodes of the graph as cities and the edges as distances between them, and we want to find a tour of the graph such that every node (city) is visited exactly once and the distance of the tour minimum. In this problem the decision variables are the selection of edges from the graph in order to meet the requirement; quite different than setting discrete variables.
So our first job is to consider how to represent the problem. In this type of graph, edges that go from one node (vertex) to another may have a weight/distance/metric (whatever you want to call it) or be absent, that is no edge these vertices. This suggests that we should use a discriminated union to represent edges, where one choice is NoEdge
and the other a floating point value as:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: |
type EdgeMetric = | NoEdge // edge does not exist | EdgeValue of float static member Zero with get() = EdgeValue(0.0) static member (+) (a,b) = match a,b with | EdgeValue(a),EdgeValue(b) -> EdgeValue(a+b) | _ -> NoEdge static member (-) (a,b) = match a,b with | EdgeValue(a),EdgeValue(b) -> EdgeValue(a-b) | _ -> NoEdge type TSPstate = { NodeList : (int * int) list Cost : float ReducedMatrix: EdgeMetric[,] } |
In the definition, we also defined a ‘zero’ element, which is required for using the sequence sum methods (a sum starts at zero, which must be defined for a custom type), as well as overloads for binary addition (+) and subtraction (-). These are defined such that they are the normal arithmetic operations when both arguments are EdgeValues
and NoEdge
otherwise. Sometimes we might think of NoEdge
as an edge with an ∞ value, which of course could never be part of a finite travel distance – that is why summing or subtracting a NoEdge
with a valid edge distance results in NoEdge
.
We also defined what will be our node in the search tree, but named it TSPstate
instead of TSPnode
to avoid confusion with a graph node. This state has a NodeList
which is a list of a pair of integers; the integers will be the indices of the nodes (graph vertexes) for our adjacency matrix representation of the graph. It has a Cost
which is the lower bound estimate of the tour cost given the selections made so far and a ReducedMatrix
. Without getting into the details, the way a bound for the cost is found is by considering the minimum costs of entering and exiting each node of the graph (see the appendix here if interested); this will be computed in the function TSPreduce
below.
Importantly, note that for TSP we want to minimize the objective function (tour length) which is reverse of what our BandB
method does (for knapsack and Max-Sat we are maximizing). If all we had was an objective function (f
) then we could maximize -f
in order to minimize it. But in branch and bound we also have the comparison of f
against g
(i.e., this appears on lines 22 and 29 of the BandB
listing on the prior page). So simply negating f
and g
values will not work. So this will call for further changes to our BandB
function, but first let’s look at the TSP
module.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: |
namespace BandBapplication type EdgeMetric = | NoEdge // edge does not exist | EdgeValue of float static member Zero with get() = EdgeValue(0.0) static member (+) (a,b) = match a,b with | EdgeValue(a),EdgeValue(b) -> EdgeValue(a+b) | _ -> NoEdge static member (-) (a,b) = match a,b with | EdgeValue(a),EdgeValue(b) -> EdgeValue(a-b) | _ -> NoEdge type TSPstate = { EdgeList : (int * int) list Cost : float ReducedMatrix: EdgeMetric[,] } module TSP = let TSPreduce matrix = let mutable total = 0.0 let nRows = Array2D.length1 matrix // assume 1 row at least let nCols = Array2D.length2 matrix // assume 1 col at least let mutable estimate = 0.0 let mutable newMatrix = Array2D.copy matrix // row (outbound limit) for row in 0..nRows-1 do // get row min let mutable minVal = System.Double.PositiveInfinity for col in 0..nCols-1 do match newMatrix.[row,col] with | EdgeValue(e) -> if e < minVal then minVal <- e | _ -> () if minVal < System.Double.PositiveInfinity then total <- total + minVal // set newMatrix ... for col in 0..nCols-1 do newMatrix.[row,col] <- newMatrix.[row,col] - EdgeValue(minVal) // OK now col (inbound limit) for col in 0..nCols-1 do let mutable minVal = System.Double.PositiveInfinity for row in 0..nRows-1 do match newMatrix.[row,col] with | EdgeValue(e) -> if e < minVal then minVal <- e | _ -> () if minVal < System.Double.PositiveInfinity then total <- total + minVal for row in 0..nRows-1 do newMatrix.[row,col] <- newMatrix.[row,col] - EdgeValue(minVal) (total, newMatrix) let TSPselect row col state = let matrix = Array2D.copy state.ReducedMatrix let nRows = Array2D.length1 matrix // assume 1 row at least let nCols = Array2D.length2 matrix // assume 1 col at least let arcCost = match matrix.[row,col] with | EdgeValue(e) -> e | _ -> failwith "Illegal Edge Select" // shouldn't happen // remove edges to or from node 'row' for coli in 0..nCols-1 do matrix.[row,coli] <- NoEdge for rowi in 0..nRows-1 do matrix.[rowi,col] <- NoEdge //nMatrix.[row,col] <- NoEdge matrix.[col,row] <- NoEdge let ntotal,nMatrix = TSPreduce matrix let nList = (row,col) :: state.EdgeList // return a new TSPstate record {EdgeList = nList; Cost = state.Cost + arcCost + ntotal; ReducedMatrix = nMatrix} let branchTSP state = let mutable nodes = [] let matrix = state.ReducedMatrix let nRows = Array2D.length1 matrix // assume 1 row at least let nCols = Array2D.length2 matrix // assume 1 col at least let lastNode = if state.EdgeList.Length = 0 then 0 // start at node indexed at 0 else snd (state.EdgeList.[0]) // last edge at front if state.EdgeList.Length = nRows-1 then do // last edge, the return edge let newNode = {state with EdgeList = (lastNode, 0) :: state.EdgeList} nodes <- [newNode] // just add the return link else do for col in 0..nCols-1 do if not (matrix.[lastNode,col] = NoEdge) then let newNode = TSPselect lastNode col state nodes <- newNode :: nodes nodes let TSPmoreToDo state = let matrix = state.ReducedMatrix let nRows = Array2D.length1 matrix // assume 1 row at least nRows > state.EdgeList.Length let TSPg state = state.Cost let TSPcost (startMatrix:EdgeMetric[,]) state = let nodeListCost = state.EdgeList |> List.map (fun elem -> let fromIndex = (fst elem) let toIndex = (snd elem) match startMatrix.[fromIndex,toIndex] with | EdgeValue(ev) -> ev | _ -> 0.0 ) |> List.sum nodeListCost let TSPcreateStartState matrix = let estCost,reducedMatrix = TSPreduce matrix // remove incoming edges to node 0 since that will only happen as last selection for row in 0..(Array2D.length2 matrix)-1 do reducedMatrix.[row,0] <- NoEdge {EdgeList = []; Cost = estCost; ReducedMatrix = reducedMatrix } |
The TSPreduce
and TSPselect
functions implement the matrix reduction for selecting nodes and determining bounds. As edges are explored, the Cost
which is actally a lower-bound estimate for any tour given edges selected so far, is computed and stored in the search tree. Since subsequent bounds need the prior bound as part of their computation, this is the approach needed here (unlike for the other two problem types done earlier).
The branchTSP
function takes a search tree state and considers selecting each outgoing edge from the end of the list of nodes determined so far for that state. Since edges are pushed onto the EdgeList
from the front, the second element of the front of this list is the last node of the tour for that state. If the EdgeList is empty then we start the tour at node (index) 0, this is seen the the code on lines 89-92. Hmmm, instead of an if
experession there I probably could have used pattern matching. Also note that the final link back to the start is handled as a special case, in lines 95 and 96, there all we need to do is link back to node at index 0 (since that is where we started). Note that TSPmoreTodo
can determine if a tour is complete by checking the length of the tour, for n nodes (vertices) there should be n edges in the tour (hop to each vertex and then back to the start); the design of the TSPselect
with TSPreduce
prevents looping back to a repeated node.
These functions introduce the Array2D type from F#. As might be expected this is a matrix of data, in our case of EdgeMetric
. Why Array2D and not an array of array? Either would work, but (1) since we are using an adjacency matrix representation for the graph, this exactly fits a 2D array and (2) it has a nice Array2D.copy function that we need (to reproduce ReducedMatrices). You will later notice that we create the Array2D data from the array of array content for the examples. A downside of using Array2D is that you lose the Array functions that could operate on a row. For example, finding the minimum on lines 34-39 could be done in a functional way. However, column operations would not be any better. So ultimately I went with Array2D.
Next we need to deal with the changes to BandB
to allow finding minimums in addition to maximums. The thoughts I had (refer to the BandB
listing on the prior page):
- pass a ‘compare’ function to
BandB
that implements the comparisons needed on lines 22 and 29, it would essentially be(<)
for minimizing and(>)
for maximizing (as it is now). - pass a boolean value that determines if we are minimizing for maximizing
I selected the latter and thought that I could bake the min or max choice for branch and bound into some simple, new functions like:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: |
let BandB maximize f g branch unFinished node initLowestValue = let compareFunc x y = if maximize then x > y else x < y (* OTHER CODE *) let BandBmaximize = BandB true let BandBmiminize = BandB false |
But then I ran into error FS0030 when defining BandBmaximize
and BandBminimize
, to wit:
“The compiler performs automatic generalization only on complete function definitions that have explicit arguments, and on simple immutable values”
I believe that the problem stems from mutability of the !bestUtility
value in the return for BandB
but am not 100% sure. But I went with the simplest solution redefining these as:
1: 2: 3: 4: 5: |
let BandBmaximize f g branch unFinished node initLowestValue = BandB true f g branch unFinished node initLowestValue let BandBminimize f g branch unFinished node initLowestValue = BandB false f g branch unFinished node initLowestValue |
This style can be used whenever you need to set parameters other than the first one — well here we are setting the first one and expected to use our curried, partial function evaluation to handle it but ran into the error so we had to expand the definition.
The nodes or states in the search tree for 0-1 knapsack and Max-Sat are simple, its just the variables themselves with their settings ‘unset’, but the nodes (states) in the TSP search tree are a bit more complex, so it seemed prudent to create a special function that creates the initial (everything undecided) state for TSP, given an adjacency matrix defining the graph:
1: 2: 3: 4: 5: 6: |
let TSPcreateStartState matrix = let estCost,reducedMatrix = TSPreduce matrix // remove incoming edges to node 0 since that will only happen as last selection for row in 0..(Array2D.length2 matrix)-1 do reducedMatrix.[row,0] <- NoEdge {EdgeList = []; Cost = estCost; ReducedMatrix = reducedMatrix } |
There is one other thing in BandB
that needs to be addressed. We took care of the min or max issue by passing a bool
that is then used to define the compareFunc
for either greater than or less than, but we should also address the best-first idea in the sorting of the queue. This will be an opportunity to use type extensions. I mentioned that there is a standard list ‘sort decscending’ method starting in F# v4.0, but we implemented a reverse sort by explicitly sorting (ascending) and then reversing the list. However, type-extension allows you to add new functionality to existing types including those provided in standard libraries. Consider the following for implementing a reverse sort:
1: 2: 3: 4: |
(* This is a type extension that extends the standard List type to include a reverse sort *) module List = let reverseSort x = x |> List.sort |> List.rev // List now has a reverseSort method! let reverseSortBy f x = x |> List.sortBy f |> List.rev // List now has a reverseSortBy method! |
This adds a reverseSort
and reverseSortBy
method to List
, defined as we had before. I added it to the BandB
file as that is where it is used, but as it’s a general capability it might be better placed in a utility module. But type extension saves one from having to derive a subclass in order to add functionality as would be the case in object-oriented languages. Here is the full BandB
code now (we’ll still be making one more change before we’re done):
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: |
namespace BandBapplication (* This is a type extension that extends the standard List type to include a reverse sort *) module List = let reverseSort x = x |> List.sort |> List.rev // List now has a reverseSort method! let reverseSortBy f x = x |> List.sortBy f |> List.rev // List now has a reverseSortBy method! module BandB = let BandB maximize f g branch unFinished node initLowestValue = let compareFunc x y = if maximize then x > y else x < y let bestUtility = ref initLowestValue; // update: queue elements are now a 2-tuple (pair) of g-upperbound estimate and node let mutable queue = [ (g node, node) ] let mutable bestNode = node // best var settings found, nothing so far. // these are only informational, not needed in the routine let mutable numberOfQueues = 1 // we just queued the start, so 1 let mutable numberOfEvals = 0 // number of times we evaluated the function with all vars set while not queue.IsEmpty do match queue with | (gNode,curNode) :: restOfQueue -> if unFinished curNode then // guard against search nodes that are already ruled out ... if not (compareFunc gNode !bestUtility) then do queue <- restOfQueue // this node can't be better than what we have, toss it else do // update: apply `g` here instead, simplifying branch, and allows sorting the queue let toQueueAll = branch curNode let toQueueAugmented = toQueueAll |> List.map (fun elem -> ((g elem), elem)) let toQueue = toQueueAugmented |> List.filter (fun elem -> compareFunc (fst elem) !bestUtility) // sort only using the first tuple value (g) so the curNode type doesn't need compare if maximize then do queue <- (toQueue @ restOfQueue) |> List.reverseSortBy (fun elem -> (fst elem)) else queue <- (toQueue @ restOfQueue) |> List.sortBy (fun elem-> (fst elem)) numberOfQueues <- numberOfQueues + toQueue.Length else let util = f curNode numberOfEvals <- numberOfEvals + 1 if compareFunc util !bestUtility then bestUtility := util bestNode <- curNode queue <- restOfQueue // we've processed curNode, take it off the queue | _ -> () // queue isempty, do nothing printfn "\nBandB: total settings queued = %d, total number of evals: %d" numberOfQueues numberOfEvals (!bestUtility, bestNode) let BandBmaximize f g branch unFinished node initLowestValue = BandB true f g branch unFinished node initLowestValue let BandBminimize f g branch unFinished node initHighestValue = BandB false f g branch unFinished node initHighestValue |
Even though we could use the sort
and reverseSort
methods on the queue tuple, we instead use sortBy
and reverseSortBy
methods so that we don’t require comparison functions for the search state component of the queue (snd
element). There is one other minor optimization that was made, on lines 30-31 we test to make sure the node at the front of the queue is not already ruled out. Before we went ahead and did the branch and would have then ruled out the branches as unqualified. This doesn’t change the number of search states queued, but does save a bit of work.
Next, let’s look at the main program, Program.fs
with the knapsack and Max-Sat examples omitted (they are included in the code download).
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: |
namespace BandBapplication (* Part II page 5 *) //open DiscreteVarTypes open Knapsack01 open MaxSat open TSP open BandB module Main = [<EntryPoint>] let main argv = (* *************************************************************************************** *) (* KNAPSACK EXAMPLE 1 *) (* OMITTED *) (* *************************************************************************************** *) (* MAXSAT EXAMPLE 1 *) (* OMITTED *) (* *************************************************************************************** *) (* TSP EXAMPLE 1 *) (* data format EdgeValue wher: row is from index, column is to index. *) let matrix3_aa = [| [| NoEdge; EdgeValue(20.0); EdgeValue(30.0); EdgeValue(10.0); EdgeValue(11.0) |]; [| EdgeValue(15.0); NoEdge; EdgeValue(16.0); EdgeValue(4.0); EdgeValue(2.0) |]; [| EdgeValue(3.0); EdgeValue(5.0); NoEdge; EdgeValue(2.0); EdgeValue(4.0) |]; [| EdgeValue(19.0); EdgeValue(6.0); EdgeValue(18.0); NoEdge;EdgeValue(3.0) |]; [| EdgeValue(16.0); EdgeValue(4.0); EdgeValue(7.0); EdgeValue(16.0); NoEdge |]; |] let matrix3 = Array2D.init 5 5 (fun i j -> matrix3_aa.[i].[j]) // create as Array2D // TSP node let start3 = TSPcreateStartState matrix3 let tspCost3 = TSPcost matrix3 // bake in the matrix let (bestValue3, solution3) = BandBminimize tspCost3 TSPg branchTSP TSPmoreToDo start3 System.Double.PositiveInfinity printfn "Solution 3:" printfn "tour cost = %f" (bestValue3) printfn "%A" solution3.EdgeList (* data format EdgeValue wher: row is from index, column is to index. *) (* from https://parallel-tsp.googlecode.com/files/teamDharmaPresentation.pdf *) let matrix4_aa = [| [| NoEdge; EdgeValue(755.0); EdgeValue(687.0); EdgeValue(936.0); EdgeValue(721.0) |]; [| EdgeValue(755.0); NoEdge; EdgeValue(310.0); EdgeValue( 43.0); EdgeValue(729.0) |]; [| EdgeValue(687.0); EdgeValue(310.0); NoEdge; EdgeValue(390.0); EdgeValue(478.0) |]; [| EdgeValue(936.0); EdgeValue( 43.0); EdgeValue(390.0); NoEdge; EdgeValue(643.0) |]; [| EdgeValue(721.0); EdgeValue(729.0); EdgeValue(478.0); EdgeValue(643.0); NoEdge |]; |] let matrix4 = Array2D.init 5 5 (fun i j -> matrix4_aa.[i].[j]) // create as Array2D // TSP node let start4 = TSPcreateStartState matrix4 let tspCost4 = TSPcost matrix4 let (bestValue4, solution4) = BandBminimize tspCost4 TSPg branchTSP TSPmoreToDo start4 System.Double.PositiveInfinity printfn "Solution 4:" printfn "tour cost = %f" (bestValue4) printfn "%A" solution4.EdgeList let matrix4_15_aa = [| [| NoEdge; EdgeValue(29.0); EdgeValue(82.0); EdgeValue(46.0); EdgeValue(68.0); EdgeValue(52.0); EdgeValue(72.0); EdgeValue(42.0); EdgeValue(51.0); EdgeValue(55.0); EdgeValue(29.0); EdgeValue(74.0); EdgeValue(23.0); EdgeValue(72.0); EdgeValue(46.0) |]; [| EdgeValue(29.0); NoEdge; EdgeValue(55.0); EdgeValue(46.0); EdgeValue(42.0); EdgeValue(43.0); EdgeValue(43.0); EdgeValue(23.0); EdgeValue(23.0); EdgeValue(31.0); EdgeValue(41.0); EdgeValue(51.0); EdgeValue(11.0); EdgeValue(52.0); EdgeValue(21.0) |]; [| EdgeValue(82.0); EdgeValue(55.0); NoEdge; EdgeValue(68.0); EdgeValue(46.0); EdgeValue(55.0); EdgeValue(23.0); EdgeValue(43.0); EdgeValue(41.0); EdgeValue(29.0); EdgeValue(79.0); EdgeValue(21.0); EdgeValue(64.0); EdgeValue(31.0); EdgeValue(51.0) |]; [| EdgeValue(46.0); EdgeValue(46.0); EdgeValue(68.0); NoEdge; EdgeValue(82.0); EdgeValue(15.0); EdgeValue(72.0); EdgeValue(31.0); EdgeValue(62.0); EdgeValue(42.0); EdgeValue(21.0); EdgeValue(51.0); EdgeValue(51.0); EdgeValue(43.0); EdgeValue(64.0) |]; [| EdgeValue(68.0); EdgeValue(42.0); EdgeValue(46.0); EdgeValue(82.0); NoEdge; EdgeValue(74.0); EdgeValue(23.0); EdgeValue(52.0); EdgeValue(21.0); EdgeValue(46.0); EdgeValue(82.0); EdgeValue(58.0); EdgeValue(46.0); EdgeValue(65.0); EdgeValue(23.0) |]; [| EdgeValue(52.0); EdgeValue(43.0); EdgeValue(55.0); EdgeValue(15.0); EdgeValue(74.0); NoEdge; EdgeValue(61.0); EdgeValue(23.0); EdgeValue(55.0); EdgeValue(31.0); EdgeValue(33.0); EdgeValue(37.0); EdgeValue(51.0); EdgeValue(29.0); EdgeValue(59.0) |]; [| EdgeValue(72.0); EdgeValue(43.0); EdgeValue(23.0); EdgeValue(72.0); EdgeValue(23.0); EdgeValue(61.0); NoEdge; EdgeValue(42.0); EdgeValue(23.0); EdgeValue(31.0); EdgeValue(77.0); EdgeValue(37.0); EdgeValue(51.0); EdgeValue(46.0); EdgeValue(33.0) |]; [| EdgeValue(42.0); EdgeValue(23.0); EdgeValue(43.0); EdgeValue(31.0); EdgeValue(52.0); EdgeValue(23.0); EdgeValue(42.0); NoEdge; EdgeValue(33.0); EdgeValue(15.0); EdgeValue(37.0); EdgeValue(33.0); EdgeValue(33.0); EdgeValue(31.0); EdgeValue(37.0) |]; [| EdgeValue(51.0); EdgeValue(23.0); EdgeValue(41.0); EdgeValue(62.0); EdgeValue(21.0); EdgeValue(55.0); EdgeValue(23.0); EdgeValue(33.0); NoEdge; EdgeValue(29.0); EdgeValue(62.0); EdgeValue(46.0); EdgeValue(29.0); EdgeValue(51.0); EdgeValue(11.0) |]; [| EdgeValue(55.0); EdgeValue(31.0); EdgeValue(29.0); EdgeValue(42.0); EdgeValue(46.0); EdgeValue(31.0); EdgeValue(31.0); EdgeValue(15.0); EdgeValue(29.0); NoEdge; EdgeValue(51.0); EdgeValue(21.0); EdgeValue(41.0); EdgeValue(23.0); EdgeValue(37.0) |]; [| EdgeValue(29.0); EdgeValue(41.0); EdgeValue(79.0); EdgeValue(21.0); EdgeValue(82.0); EdgeValue(33.0); EdgeValue(77.0); EdgeValue(37.0); EdgeValue(62.0); EdgeValue(51.0); NoEdge; EdgeValue(65.0); EdgeValue(42.0); EdgeValue(59.0); EdgeValue(61.0) |]; [| EdgeValue(74.0); EdgeValue(51.0); EdgeValue(21.0); EdgeValue(51.0); EdgeValue(58.0); EdgeValue(37.0); EdgeValue(37.0); EdgeValue(33.0); EdgeValue(46.0); EdgeValue(21.0); EdgeValue(65.0); NoEdge; EdgeValue(61.0); EdgeValue(11.0); EdgeValue(55.0) |]; [| EdgeValue(23.0); EdgeValue(11.0); EdgeValue(64.0); EdgeValue(51.0); EdgeValue(46.0); EdgeValue(51.0); EdgeValue(51.0); EdgeValue(33.0); EdgeValue(29.0); EdgeValue(41.0); EdgeValue(42.0); EdgeValue(61.0); NoEdge; EdgeValue(62.0); EdgeValue(23.0) |]; [| EdgeValue(72.0); EdgeValue(52.0); EdgeValue(31.0); EdgeValue(43.0); EdgeValue(65.0); EdgeValue(29.0); EdgeValue(46.0); EdgeValue(31.0); EdgeValue(51.0); EdgeValue(23.0); EdgeValue(59.0); EdgeValue(11.0); EdgeValue(62.0); NoEdge; EdgeValue(59.0) |]; [| EdgeValue(46.0); EdgeValue(21.0); EdgeValue(51.0); EdgeValue(64.0); EdgeValue(23.0); EdgeValue(59.0); EdgeValue(33.0); EdgeValue(37.0); EdgeValue(11.0); EdgeValue(37.0); EdgeValue(61.0); EdgeValue(55.0); EdgeValue(23.0); EdgeValue(59.0); NoEdge |] |] let matrix4_15 = Array2D.init 15 15 (fun i j -> matrix4_15_aa.[i].[j]) // create as Array2D // TSP node let start4_15 = TSPcreateStartState matrix4_15 let tspCost4_15 = TSPcost matrix4_15 let (bestValue4_15, solution4_15) = BandBminimize tspCost4_15 TSPg branchTSP TSPmoreToDo start4_15 System.Double.PositiveInfinity printfn "Solution 4_15:" printfn "tour cost = %f" (bestValue4_15) printfn "%A" solution4_15.EdgeList printfn "DONE" System.Console.ReadKey() |> ignore // don't close the output window until a key is hit 0 |
The first example is a made up example that looks like:
TSP problem, solution shown with red line
The graph shows the solution found with a total tour cost of 28 (solution 3 in the code). The next example comes from here which is also a 5 node graph, the optimum solution length is 2387 (its solution4
in the code), the link shows the graph image for this problem. The next example comes from the TSPLIB (image at link) a fifteen node example with optimal tour cost of 291. Running this will generate:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: |
BandB: total settings queued = 19, total number of evals: 4 Best Utility = 14.000000 {Name = "map"; Weight = 0.5; Utility = 3.0; Setting = One;} {Name = "gps"; Weight = 1.0; Utility = 3.0; Setting = One;} {Name = "food"; Weight = 5.0; Utility = 8.0; Setting = One;} {Name = "tent"; Weight = 14.5; Utility = 5.0; Setting = Zero;} BandB: total settings queued = 23, total number of evals: 4 Solution 2: #clauses satisfied = 9 out of 9 v1 = false v2 = true v3 = true v4 = true v5 = false v6 = false BandB: total settings queued = 12, total number of evals: 1 Solution 3: tour cost = 28.000000 [(2, 0); (4, 2); (1, 4); (3, 1); (0, 3)] BandB: total settings queued = 24, total number of evals: 5 Solution 4: tour cost = 2387.000000 [(1, 0); (3, 1); (2, 3); (4, 2); (0, 4)] BandB: total settings queued = 1184, total number of evals: 2 Solution 4_15: tour cost = 291.000000 [(12, 0); (1, 12); (14, 1); (8, 14); (4, 8); (6, 4); (2, 6); (11, 2); (13, 11); (9, 13); (7, 9); (5, 7); (3, 5); (10, 3); (0, 10)] DONE |
All of these TSP examples are fully connected, but by placing NoEdge
in the input matrix edges can be eliminated and arbitrary graphs can be defined, they don’t need to be fully connected.
The download for the code also contains a commented out FRI26 26 node example from TSPLIB as well, but I omitted it from the listing for two reasons, it only bloats the listing without adding anything and also since it most like is not feasible to do with our code (try it overnight if you wish).
On to the end of Part II.