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

The code is getting a bit hard to follow with everything in one file, we can use some code organization features to better organize (see this and this), particularly when we will later add more instance types and examples. If you are using Visual Studio, see this regarding Visual Studio and the order that .fs files appear in the solution pane. Generally, all definitions must come before use so the input files need to be arranged as such, although there are provisions for mutual recursion.

F# namespaces are an organization of modules, classes and other namespaces, meant to be used to group these elements together, possibly hierarchically. They are not necessary, but can be used to avoid naming conflicts — in larger programs the same union member or class name may appear and namespaces can be used to distinguish them. This will arise for us later as well.

F# modules are also used for organization. According to this, you can think of them like static classes in C++ or C# and are mostly used to group together related functions. All functions are ultimately part of a module, however if a source code file does not include a namespace or module declaration then it is automatically placed into a module with the same name as the file — note we haven’t used these declarations to this point so everything we’ve done was placed in an unnamed module. The open statement works like an include from other languages to bring external defintions in. There is also an [<AutoOpen>] attribute that can be specified for a module, this makes all of the contents of the module visible externally for other modules in the same namespace without explicitly using the open statement.

So let’s start by moving the DiscreteVar into a separate file, this is the content of the DiscreteVarTypes file now:

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

namespace BandBapplication

[<AutoOpen>]
module DiscreteVariableTypes =
    type ZeroOneVarSetting =
        | Unset                         (* this is a discriminated union type in F# *)
        | One
        | Zero
        static member isUnset a =
            match a with
            | Unset -> true
            | _ -> false

As can be seen, we placed the DiscreteVarTypes module in the BandBapplication namespace. We will place all of our other code in this namespace as well. We also specify the [<AutoOpen>] attribute, so that we do not need to explicitly use open DiscreteVarTypes in the other files in the namespace.

We next split our core branch and bound algortihm into its own .fs file, called BandB.fs:

 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:

namespace BandBapplication

module BandB =

    let BandB f g branch unFinished node initLowestValue =
        let mutable bestUtility = initLowestValue;
        let mutable queue = [node]
        let mutable bestNode = node    // best full sol'n found

        // 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
            | curNode :: restOfQueue -> 
                if unFinished curNode then
                    let toQueue = branch g bestUtility curNode
                    queue <- toQueue @ restOfQueue
                    numberOfQueues <- numberOfQueues + toQueue.Length
                else
                    let util = f curNode         
                    numberOfEvals <- numberOfEvals + 1
                    if util > bestUtility then  (* Any assumptions? *)
                        bestUtility <- util
                        bestNode <- curNode
                                      
                    queue <- restOfQueue // we've processed curVars, take it off the queue
                                       
            | _ -> ()  // queue isempty, do nothing
       
        printfn "BandB: total settings queued = %d, total number of evals: %d" numberOfQueues numberOfEvals
        (bestUtility, bestNode)

I am uncomfortable with setting bestNode on line 8 to the initial search node as it is not a full solution (indeed the opposite). I think it is better defined as an optional type but leave it for now

I took the liberty of making a few name changes here. These will make more sense as we add different problem types for the solver. The unsetVars function was renamed unFinished — the meaning is that a full solution setting has not yet been reached. The vars argument was renamed node to reflect that it is a node in the branch and bound search tree (see figures on prior pages). When this node is ‘finished’ then it means that all descisions have been selected, in the case of knapsack this means that all variables are set to Zero or One. A ‘node’ for knapsack is a partial setting of its variables, hence it was called vars before.

And then we split the functions particular to the 0-1 knapsack into their own file, called knapsack01. At the same time as doing this, I removed the active pattern match for the bound estimates against the bestUtility found as now we are also considering feasibility of the search node and its descendants (this will change once again later – its a development process).

 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:

    let branchknap wlimit g bestUtility vars =
        let unsetVarIndex = unsetVarIndex vars      // should only be called when there are Unset vars, so no -1 check
        let varArrayZero = vars 
                           |> Array.mapi (fun index var -> if index = unsetVarIndex then {var with Setting = Zero} else var)
        let varArrayOne  = vars 
                           |> Array.mapi (fun index var -> if index = unsetVarIndex then {var with Setting = One} else var)

        let gEstimateZero = g varArrayZero
        let gEstimateOne = g varArrayOne

        // not only use g but also ensure feasibilty!
        let zeroMakesWeight = (knapmultiplySumWeight varArrayZero) <= wlimit
        let oneMakesWeight = (knapmultiplySumWeight varArrayOne) <= wlimit

        let takeZero = zeroMakesWeight && gEstimateZero > bestUtility
        let takeOne = oneMakesWeight && gEstimateOne > bestUtility
                
        // update the queue, first match is the 
        match (takeZero, takeOne) with
        | true,true -> 
            varArrayOne :: [varArrayZero]
        | true,false -> 
            [varArrayZero]
        | false,true -> 
            [varArrayOne] 
        | _ -> [] // Neither case, nothing

Finally, here is the 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:

[<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) = BandB knapmultiplySumUtility gknap1 branchknap1 knapAnyUnset vars1Sorted -1.0
    printfn "Best Utility = %f" solutionUtility
    for var in solutionVars do
        printfn "%A" var

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

The old knapmultiplySumUtility is the f function, and each of gknap1 and branchknap1 leverage the knapsack specific functions with the problem instance weightLimit1 value baked in.

In the downloaded code you will notice that open DiscreteVarTypes is commented out, we don’t need this since we used the auto open feature for that module and we’re in the same namespace; of course we do use the ZeroOneVarSetting from that module. We defined KnapDiscreteVar here instead of in the DiscreteVarTypes module as that variable definition is specific to the knapsack problem. Otherwise everything works just as before, we’ve just gotten our code better organized.