# 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;} ```