Learning F#: Case study with branch and bound – Part I (page 2)

Before implementing a full branch and bound method, let’s start by first developing an exhaustive searcher, that is one that simply elaborates all possible variable settings, and selects the best solution from those. Rather than use a recursive approach, we will use a queueing approach since that is what we’ll need for the branch and bound later. Consider this 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: 

let exhaustiveSearcher vars initLowestValue =
    let mutable bestUtility = initLowestValue;
    let mutable queue = [vars]      // queue is a list of vars, where vars are an array of DiscreteVar (assume all Unset)
    let mutable numberOfQueues = 1  // we just queued the start, so 1
        
    (* find an unset var *)    
    let findUnsetVarIndex vars =
        Array.findIndex (fun var -> var.Setting = Unset) vars   // will raise exception if not found

    (* any var unset ? *)    
    let anyUnsetVars vars =
        Array.fold (fun acc var -> acc || var.Setting = Unset) false vars   // will raise exception if not found

    while not queue.IsEmpty do
        match queue with
        | queueHead :: restOfQueue -> if anyUnsetVars queueHead then
                                         let varIndex = findUnsetVarIndex queueHead // queueHead is an array of DiscreteVar
                                         let tvar = Array.get queueHead varIndex

                                         let zeroVar = { tvar with Setting = Zero }  // change the unset var to One and Zero
                                         let varArrayZero = Array.copy queueHead  // copy the array so we can change element
                                         Array.set varArrayZero varIndex zeroVar

                                         let oneVar = { tvar with Setting = One }
                                         let varArrayOne = Array.copy queueHead  // copy the array so we can change element
                                         Array.set varArrayOne varIndex oneVar
                                         queue <- varArrayZero :: varArrayOne :: restOfQueue
                                         numberOfQueues <- numberOfQueues + 2    // added two the queue
                                      else
                                         // all vars have a setting! evaluate it
                                         let util = multiplySumUtility queueHead
                                         if util > bestUtility then
                                            bestUtility <- util
                                      
                                         queue <- restOfQueue // we've processed queueHead, take it off the queue
                                      
                                      ()    
        | _ -> ()  // queue isempty, do nothing
       
    printfn "Total settings queued = %d" numberOfQueues
    bestUtility

In F# mutable variables are reassigned using the <- syntax. ref variables are reassigned using the := syntax

The function takes as arguments the DiscreteVar array and an initial value which is presumed to be less than all possible valid utility evaluations; it is used to initialize bestUtility. Since we will be altering bestUtility, queue, and numberOfQueues during the algorithm, they are defined as mutable (i.e., changeable). We next define two useful functions, findUnsetVarIndex and anyUnsetVars each taking an argument of DiscreteVar array. findUnsetVarIndex searches the var array to find the index of a variable using the Array.find function that is Unset, it will throw an exception if there is no such element found. The anyUnsetVars method returns true if there are any vars in the input array that are Unset. Starting with a value of false the Array.fold function applies the given (lambda, unnamed) function to the accumulated value (acc) and each element; in this case the boolean value of testing each elem for Unset.

The empty match pattern at the end of the pattern match is unnecessary as the loop conditional test ensures that the queue is not empty, but all patterns must be matched

Next comes the main loop involving the queue. While the queue is not empty, we use pattern matching to get the head of the queue queueHead and the remainder of the queue restOfQueue (otherwise we do nothing as in the default pattern match). We first test the queueHead (which is an array of DiscreteVar) to see if any of its member variables are Unset, if so we are effectively taking the unset variable and creating two copies of the array, one of which changes the unset variable to Zero and the other to One. These new arrays, along with the restOfQueue become the new queue. If, on the otherhand, all the variables are set, we use our multiplySumUtility function from the last page to evaluate the setting. If this utility value is better than the one we currently have we update the current best found. Being able to change an element using Array.set is why we chose to use arrays, rather than lists, for our variable input.

If we apply the exhaustiveSearcher function like so:

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 

    let vars = [|{Name = "food"; Setting = Unset; Weight = 5.0; Utility = 8.0}; (* These are deduced to be DiscreteVar record types *) 
                 {Name = "tent"; Setting = Unset; Weight = 14.5; Utility = 5.0}; 
                 {Name = "gps"; Setting = Unset; Weight = 1.0; Utility = 3.0}; 
                 {Name = "map"; Setting = Unset; Weight = 0.5; Utility = 3.0} |]
    let weightLimit = 16.0

    let totalUtility = exhaustiveSearcher vars -1.0
    printfn "Best utility (ignores weight restriction): %f" totalUtility

We will get the following output:

1: 
2: 

Total settings queued = 31
Best utility (ignores weight restriction): 19.000000

First of all, we notice that the total utility is 19.0, which is the sum of all the utilities — makes sense as there is nothing in the elaborator that limits the best value in regard to weights, so it finds the solution where every value is set to One — bingo maximum utility. We also note that the queue count is 31 for n = 4, which is exactly 2n+1 – 1 which is what it should be. We have queued all the nodes in the search tree.

We are not very focussed on algorithmic efficiency here, except where it provides an opportunity to explore F#.

Let’s make some improvements, first we want to get the actual solution, not just the total utility of the maximum. Secondly notice that both findUnsetVarIndex and anyUnsetVars are basically running through the vars, one determining if all the vars are unset and the other finding an index for an unset variable. They seem like they could be combined into a single fucntion, but we need to return two values from the function. Returning multiple values is done using a tuple.

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

    (* return tuple of: (any-var-unset, index-of-unset-var) *)
    let unsetVar vars =
        let mutable index = 0   // we can't use Array.find since when all the vars are set it would throw exception
        let mutable retValue = (false, -1)
        for var in vars do      // still go through the whole array after finding the one we want.
            match var.Setting with
            | Unset -> retValue <- if not (fst retValue) then (true, index) else retValue
            | _ -> ()  // do nothing

            index <- index + 1
        
        retValue

In this code, we created the function unsetVar which returns the tuple of ‘are any vars unset’ (bool) and ‘index of unset var’ (int). It works by iterating through the vars matching any that have a setting of Unset. If a var does, and its the first one found then we set our return tuple to (true, index). Note that just as in the Array.fold and Array.findIndex methods before, we scan through the whole array everytime, even after finding what we want. If we did this in a more traditional way, we would exit the loop with (true, index) as soon as we found it. We could also just return a single int value where we interpret -1 as Unset variable not found. And we could do this with the Array.findIndex function as well as long as we catch the exception for no unset varaibles in the array. We will consider this issue later, but at least now we only go through the variable array once and see how a tuple might be used as a return value.

Next is the revised code that makes use of this new function, and also declares the bestVars mutable variable to hold the best setting found. In the revised code for the while loop below, the let statement on line 22 is used to capture the return tuple from unsetVar, placing each into a local variable. These are then used just as before.

 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: 

let exhaustiveSearcher wlimit vars initLowestValue =
    let mutable bestUtility = initLowestValue;
    let mutable queue = [vars]      // queue is a list of vars, where vars are an array of DiscreteVar (assume all Unset)
    let mutable numberOfQueues = 1  // we just queued the start, so 1
    let mutable bestVars = [| |]    // best var settings found.
        
    (* return tuple of: (any-var-unset, index-of-unset-var) *)
    let unsetVar vars =
        let mutable index = 0   // we can't use Array.find since when all the vars are set it would throw exception
        let mutable retValue = (false, -1)
        for var in vars do      // still go through the whole array after finding the one we want.
            match var.Setting with
            | Unset -> retValue <- if not (fst retValue) then (true, index) else retValue
            | _ -> ()  // do nothing

            index <- index + 1
        
        retValue

    while not queue.IsEmpty do
        match queue with
        | queueHead :: restOfQueue -> let (anyUnset,varIndex) = unsetVar queueHead 
                                      if anyUnset then
                                         let tvar = Array.get queueHead varIndex

                                         // change the unset var to One and Zero
                                         let zeroVar = { tvar with Setting = Zero }
                                         let varArrayZero = Array.copy queueHead  // copy the array so we can change element
                                         Array.set varArrayZero varIndex zeroVar

                                         let oneVar = { tvar with Setting = One }
                                         let varArrayOne = Array.copy queueHead  // copy the array so we can change element
                                         Array.set varArrayOne varIndex oneVar

                                         queue <- varArrayZero :: varArrayOne :: restOfQueue
                                         numberOfQueues <- numberOfQueues + 2    // added two the queue
                                      else
                                         // all vars have a setting! evaluate it
                                         let util = multiplySumUtility queueHead
                                         let wt = multiplySumWeight queueHead
                                         if util > bestUtility && wt <= wlimit then
                                            bestUtility <- util
                                            bestVars <- queueHead
                                      
                                         queue <- restOfQueue // we've processed queueHead, take it off the queue
                                       
        | _ -> ()  // queue isempty, do nothing
       
    printfn "Total settings queued = %d" numberOfQueues
    (bestUtility, bestVars)

Another change was also made. On line 40, the computed weight for the assignment is computed (using our old function) and the new best utility total is not updated unless thus weight is less than or equal to the weight limit, which is a new argument to the exhaustiveSearcher. Now we still exhuastively search all possible combinations of variables, but only select the best one that is feasible, that is makes the weight limit. You might also notice that the functions multiplySumUtility and multiplySumWeight are used in the searcher in a somewhat non-modular way, that is they are assumed to exist in the environment. This is not necessarily an issue, but we will be revisiting this later as well.

Don’t try to run this exhaustive searcher with more than 8 to 12 variables, it will get mighty slow

If we execute this code, using the following:

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

    let vars = [|{Name = "food"; Setting = Unset; Weight = 5.0; Utility = 8.0}; (* These are deduced to be DiscreteVar record types *) 
                 {Name = "tent"; Setting = Unset; Weight = 14.5; Utility = 5.0}; 
                 {Name = "gps"; Setting = Unset; Weight = 1.0; Utility = 3.0}; 
                 {Name = "map"; Setting = Unset; Weight = 0.5; Utility = 3.0} |]
    let weightLimit = 16.0

    let totalUtility,bestVarSetting = exhaustiveSearcher weightLimit vars -1.0
    printfn "Best utility (ignores weight restriction): %f" totalUtility 
    for var in bestVarSetting do
        printfn "%A " var

We get the following. This is a best knapsack that is under the 16.0 unit weight limit, the food, gps and map are selected, no tent.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 

Total settings queued = 31
Best utility (ignores weight restriction): 14.000000
{Name = "food";
 Weight = 5.0;
 Utility = 8.0;
 Setting = One;}
{Name = "tent";
 Weight = 14.5;
 Utility = 5.0;
 Setting = Zero;}
{Name = "gps";
 Weight = 1.0;
 Utility = 3.0;
 Setting = One;}
{Name = "map";
 Weight = 0.5;
 Utility = 3.0;
 Setting = One;}