Learning F#: Case study with branch and bound – Part II (page 6)

So we’ve come a long way and can now bring it all together. The final code includes everything we’ve done and allows the branch and bound method to be applied to 0-1 knapsack, MAX-SAT and TSP. We could readily add other NP-hard types as well to our general framework. The generalized solution was built up starting from the special case of 0-1 knapsack. Could we have done a top-down approach instead? Yes, but the approach taken here was to show an incremental learning process to tackle a non-trivial problem. With the experience gained, one could probably start at the end state we have here and then develop the problem specific code.

We’ve seen how powerful first-class functions and partial function application can be, particularly as we defined the f and g functions for each problem instance. We were able to ‘build in’ data particular to a problem instance into these functions allowing the generalized BandB function to basically follow the uncluttered, pseudo-code version of the method. We did that by making the type used in the search tree the last argument and leveraging currying 1, 2. Could we even build the search tree elements into f and g? Well, not easily as we need to keep track of the best solution along with upperbound estimates for nodes in the search tree in the course of executing BandB.

Next we look more closely at the type for both the BandBminimize or BandBmaximize functions. Remember that we have changed it since the image shown on page 4.

Problem ‘a ‘b
0-1 knapsack KnapDiscreteVar array float
MAX-SAT MaxSatDiscreateVar array int
TSP TSPstate float

So we read the type signature for the first argument f of BandB, for example, as a function that takes an 'a and produces a 'b, where 'a and ‘b‘ vary depending on which invocation we applied (see table). The 'a‘s are the types that appear as the nodes in the search tree, and the 'b‘s are the value type to be optimized.

Don’t be afraid of generic types in function signatures, as named 'a, 'b, etc. they just mean that the function is more flexible, not being constrained to a particular type. On the otherhand, when you have problems with types examine all the code to see what is forcing a type that maybe you aren’t expecting or don’t want. This reference has some useful tips. As reference, in C++ or C# you would have to create this function using a template (auto function arguments ala F# are being considered for C++17) but in F# generic types are used automatically, unless there is something constraining them.

Final tweaks

Another thought I had was to remove the initial value setting (initLowestValue which since we are minimizing too now would be better named just initValue but I will leave it) needed for BandBminimize or BandBmaximize functions. For our cases, this is typed as either an int or a float, so we could set the initial value to either the minimum or maximum possible value for these depending if we are maximizing or mininizing. F# does allow a generic zero and generic one value that can be either an int, float or big int (as far as I see), but there isn’t a similar generic for max or min values of the respective type. We have the same issue as brought up here, and it looks like we could use the Bounded package for this purpose. We could also think about using Double.MaxValue or MinValue and converting int result types (as for Max-Sat) to doubles; there is also a Double.PositiveInfinity and Double.NegativeInfinity value provided, which could be used assuming this conversion. But in principle, any sortable value (that is one that is subject to (<) and (>) operations) would be a valid candidiate for the BandB function. But then perhaps any of these types could always be converted double and then we would restrict the type of the 'b type to double.

But instead, its an opportunity to think about the option feature of F#. Basically an option type just means that the variable might be None meaning it doesn’t exist. I was thinking of changing the BandB code to:

 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: 

    let BandB maximize f g branch unFinished state =
        
        let compareFunc x y = if maximize then
                                x > y
                              else
                                x < y

        let bestUtility = ref None
        let mutable bestNode = None    // best var settings found, nothing so far. 

        let mutable queue = [ (g state, state) ]

        // 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
                        match !bestUtility with
                        | None ->
                            queue <- (toQueue @ restOfQueue)  // no sorting, just descend to get a first DFS
                        | Some(v) -> 
                            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)

??? What is the best suggestion for this, using generic min/value values or option types?

which is OK, but this then cascaded into many changes to all the problem domain functions since now many of their return types would have to be an option type as well (since, for example, bestNode is an option type). I will have to think about this more.

But to wrap up this section, I also added a function to create randomized MAX-SAT instances:

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 

// new function to generate a random MAX SAT case
let genMaxSat nVars nClauses =
    // embedded function
    let getRandom = 
        let rnd = System.Random(100)    // use a seed so that everytime we run we get the same values
        fun maxNum ->
            let e = rnd.Next(1, maxNum+1)
            let s = rnd.Next(0,2)
            if s = 0 then e else -e        // return Plus or Minus the int
        
    let vars = Array.init nVars (fun index -> {Name = (sprintf "v%i" (index+1)); Setting = Unset })
    // generate random 3-clause
    let clauses = Array.init nClauses (fun _ -> [| getRandom nVars; getRandom nVars; getRandom nVars |] )
    (vars, clauses)

The complete final BandB code is:

 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: 

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 !bestUtility = initLowestValue then do
                            queue <- (toQueue @ restOfQueue)  // no sorting, just descend to get a first DFS
                        else 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

On lines 42-43 code was added to ensure that the queue does not get sorted until after at least 1 full solution is found. The idea of this is that this would establish an early bound for better search pruning. We will see mixed results later on from this.

We added a random 15 variable, 120 clause problem for Max-Sat to create a larger problem size as well sp that finally, here is the full main code:

  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: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 
144: 
145: 
146: 
147: 
148: 
149: 
150: 
151: 

namespace BandBapplication

(* Part II page 6 *)

open Knapsack01
open MaxSat
open TSP
open BandB

module Main =

    [<EntryPoint>]
    let main argv = 
        (* *************************************************************************************** *)
        (* KNAPSACK EXAMPLE 1 *)
        let vars1 = [|{Name = "food"; Setting = ZeroOneVarSetting.Unset; Weight = 5.0; Utility = 8.0}; 
                      {Name = "tent"; Setting = ZeroOneVarSetting.Unset; Weight = 14.5; Utility = 5.0}; 
                      {Name = "gps"; Setting = ZeroOneVarSetting.Unset; Weight = 1.0; Utility = 3.0}; 
                      {Name = "map"; Setting = ZeroOneVarSetting.Unset; Weight = 0.5; Utility = 3.0} |]
        let weightLimit1 = 16.0
        let vars1Sorted = (Array.sortBy (fun elem -> -elem.Utility / elem.Weight) vars1)  // still have this

        let gknap1 = knapestimator weightLimit1
        let knapAnyUnset = Array.exists (fun (elem:KnapDiscreteVar) -> ZeroOneVarSetting.isUnset elem.Setting) 
        let branchKnap1 = branchknap weightLimit1

        (* Invoke *)
        let (solutionUtility, solutionVars) = BandBmaximize knapmultiplySumUtility gknap1 branchKnap1 knapAnyUnset vars1Sorted -1.0
        printfn "Best Utility = %f" solutionUtility
        for var in solutionVars do
            printfn "%14s -> %s  [weighs = %f]" var.Name (match var.Setting with
                                                          | One -> "take "
                                                          | _ -> "leave") var.Weight 

        (* *************************************************************************************** *)
        (* MAXSAT EXAMPLE 1 *)
        let vars2 = [|
                     {Name = "v1"; Setting = Unset};
                     {Name = "v2"; Setting = Unset};
                     {Name = "v3"; Setting = Unset};
                     {Name = "v4"; Setting = Unset};
                     {Name = "v5"; Setting = Unset};
                     {Name = "v6"; Setting = Unset}
                     |]
        let clauses2 = [|   [|-1;  2; -4|];   // positive = var at that index; negative means not var at index
                            [|-1;  3;  4|];
                            [|-2;  3;  4|];
                            [|-2; -4; -5|];
                            [| 2;  3;  6|];
                            [| 3;  5; -6|];
                            [|-4; -5;  6|];
                            [|-2;  5; -6|];
                            [| 3; -5;  6|];
                         |]

        let f2 = clausefulleval clauses2    // partial func application
        let g2 = clauseNumFalseFunc clauses2
        let maxsatAnyUnset = Array.exists (fun elem -> elem.Setting = ZeroOneVarSetting.Unset) 

        let (bestValue2, solution2) = BandBmaximize f2 g2 maxsat_branch maxsatAnyUnset vars2 -1
        printfn "Solution 2:"
        printfn "# clauses satisfied = %d out of %d" bestValue2 clauses2.Length
        solution2 |> Array.iter (fun elem -> printfn "%s = %s" elem.Name (match elem.Setting with 
                                                                          | ZeroOneVarSetting.Unset -> "<ERR:UNSET>" 
                                                                          | ZeroOneVarSetting.Zero -> "false" 
                                                                          | _ -> "true"))

        // Max Sat random
        let vars2_rand,clauses2_rand = genMaxSat 15 120
        let f2_rand = clausefulleval clauses2_rand    // partial func application
        let g2_rand = clauseNumFalseFunc clauses2_rand

        let (bestValue2_rand, solution2_rand) = BandBmaximize f2_rand g2_rand maxsat_branch maxsatAnyUnset vars2_rand -1
        printfn "Solution 2_rand:"
        printfn "# clauses satisfied = %d out of %d" bestValue2_rand clauses2_rand.Length
        solution2_rand |> Array.iter (fun elem -> printfn "%s = %s" elem.Name (match elem.Setting with 
                                                                               | ZeroOneVarSetting.Unset -> "<ERR:UNSET>" 
                                                                               | ZeroOneVarSetting.Zero -> "false" 
                                                                               | _ -> "true"))

        (* *************************************************************************************** *)
        (* 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 "\nDONE"

        System.Console.ReadKey() |> ignore  // don't close the output window until a key is hit
        0

Running all of these examples with and without the ‘DFS” (depth first search) option (lines 42-43 of BandB) results in:

Name of solution Without DFS With DFS
Problem in code Queue Size Num Evals Queue Size Num Evals
0-1 knapsack solutionVars 19 4 13 1
MaxSat 6 solution2 23 4 16 3
MaxSat 15 solution2_rand 6105 70 5954 69
TSP 3 solution3 12 1 20 2
TSP 5 solution4 24 5 27 6
TSP 15 solution4_15 1184 2 1265 3

As can be seen the DFS option doesn’t always help. The MaxSat 15 problem has 15 (binary) varaibles, so there are 215 = 32,768 possible combinations and 216 – 1 = 65,535 nodes in the search tree, however the branch and bound method found the solution with a fraction of these numbers. The savings for TSP are more impressive. As TSP is basically a weighted Hamiltonian cycle, so we can consider this number of possible cycles as the number of possible TSP solutions. We know there are (n-1)!/2 Hamilitonian cycles in a complete graph of n nodes (vertices) [see this]. For TSP 15, which is a complete graph of 15 nodes, this is 653,837,184,000 but again we solved this evaluating and searching much more effectively.

There are other things that could be done with the core method but we will leave it here. But one additional observation is that if the sorting option is used, then there should be better ways to insert the new items (toQueue) into it. Right now the new items are added to the front of the queue (which simply a list) and then a sort (or reverseSort) is employed, but an available heap/priority queue could be used to get better average performance. As queue sizes are not excessive, this is also left for another time.

Well we now have a generalized branch and bound routine that can either minimize of maximize. It can be used for any problem as long as one can define the f, g, branch and unFinished functions for the domain. We encountered uses for many of F#’s features along the way but there are some things in F# we didn’t cover:

  • option types (mentioned breifly)
  • units of measure
  • Sequences and lazy evaluation
  • Annotations and reflection
  • Code quotations
  • Exceptions
  • Code documentation
  • some things not covered yet, but will be by the end
    • Testing
    • Performance analysis
    • Mailboxes (in Part IV)
    • Object-oriented programming and classes
    • Coupling to the .NET libraries

Download final Part II code

In this final version, I changed some variable and types names as alluded to before that were not necessarily shown here, but the important changes have been discussed.

We’ve created a lot of code and it looks like it works, but we need to test it … on to Part III