Learning F#: Case study with branch and bound - Part II (page 5)

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.

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.