Part II: Generalized Branch and Bound

Armed with success for completing the 0-1 knapsack using a branch and bound approach, we now tackle the general form of branch and bound — and get to a very functional solution. So what about the 0-1 knapsack solver keeps it from being a generalized branch and bound solver? Well firstly, the variable definition includes the Weight and Utility fields which are specific to knapsack. The discrete variables only have states Unset, Zero and One which is fine assuming that the variables are binary. That is a discrete variable can also be one that takes on any value from a set of possibilities (possibly infinite as in ‘positive integers’), not just 0 or 1. Also, the branching part of the code makes the same assumption, substituting in Zero or One for Unset variables. This also effected the queue update in that we decided if none, zero or one, or both variable updates should be queued. The function used to evaluate the objective function (that is maximize the knapsack utility, the multiplySumUtility call) was explicitly invoked in the code. And finally the upper bound estimator (estimator) was also explicit in the routine. So there are lot’s of things that make this routine specific to the 0-1 knapsack — but its a good learning experience before trying to create a general solver (assuming our bottom-up approach) — and it does follow the general method of branch and bound.

Let’s start making some changes.

The first change is to make the objective function and estimator functions parameters of the branch and bound function. Functions can be arguments since functions are first-class objects in F# (F# is not the only language where this is true). We’d like to get to a branch and bound function that starts to look like this, and its invocation:

1: 
2: 
3: 
4: 
5: 

let BandB f g vars initLowestValue =
    (* TBD *)
    
(* invoke *)
let (solutionUtility, solutionVars) = BandB fknap gknap vars -1.0

That is the objective function (f) and upperbound estimator (g) are to be passed in, assuming that they operate as being applied to vars. We already know the function f here for 0-1 knapsack, its just multiplySumUtility (or is it?), but we don’t have g yet. Well, g is estimator with the weight limit for a particular problem built in, we can use partial function application for this. Let’s see where this stands so far:

  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: 

open System.Collections.Generic

(* Part II page 1 *)
type ZeroOneVarSetting =
    | Unset                         (* this is a discriminated union type in F# *)
    | One
    | Zero

type DiscreteVar = 
    {                               (* this is a record type in F# *)
    Name : string;
    Weight : float;
    Utility : float;
    Setting : ZeroOneVarSetting;         // discrete value setting
    }

let BandB f g vars initLowestValue =
    let mutable bestUtility = initLowestValue;
    let mutable queue = [vars]
    let mutable bestVars = [| |]     // 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
    
    (* return index of unset (first) var, or -1 if all are set (to One or Zero) *)
    let unsetVarIndex vars =
        try
            Array.findIndex (fun var -> var.Setting = Unset) vars
        with
            | :? KeyNotFoundException -> -1

    (* active patterns *)
    let (|TakeBoth|TakeZeroOnly|TakeOneOnly|TakeNeither|) (gZero, gOne, bestSoFar) = 
        if gZero > bestSoFar && gOne > bestSoFar then
            TakeBoth
        else if gZero > bestSoFar then
            TakeZeroOnly
        else if gOne > bestSoFar then
            TakeOneOnly
        else
            TakeNeither

    while not queue.IsEmpty do
        match queue with
        | curVars :: restOfQueue -> 
            let unsetVarIndex = unsetVarIndex curVars 
            if not (unsetVarIndex = -1) then

                let varArrayZero = Array.copy curVars 
                                   |> Array.mapi (fun index var -> if index = unsetVarIndex then {var with Setting = Zero} else var)
                let varArrayOne  = Array.copy curVars 
                                   |> Array.mapi (fun index var -> if index = unsetVarIndex then {var with Setting = One} else var)

                let gEstimateZero = g varArrayZero
                let gEstimateOne = g varArrayOne
                
                // update the queue
                queue <- match (gEstimateZero, gEstimateOne, bestUtility) with
                         | TakeBoth -> 
                                numberOfQueues <- numberOfQueues + 2
                                varArrayOne :: varArrayZero :: restOfQueue
                         | TakeZeroOnly -> 
                                numberOfQueues <- numberOfQueues + 1
                                varArrayZero :: restOfQueue
                         | TakeOneOnly -> 
                                numberOfQueues <- numberOfQueues + 1
                                varArrayOne :: restOfQueue
                         | _ -> restOfQueue // Neither case, just take the rest!
                        
            else
                let util = f curVars         
                numberOfEvals <- numberOfEvals + 1
                if util > bestUtility then  (* NOT GOOD AS WE LOST THE WEIGHT LIMIT *)
                    bestUtility <- util
                    bestVars <- curVars
                                      
                queue <- restOfQueue // we've processed curVars, take it off the queue
                                       
        | _ -> ()  // queue isempty, do nothing
       
    printfn "Total settings queued = %d, total number of evals: %d" numberOfQueues numberOfEvals
    (bestUtility, bestVars)

(* Some of this might be Visual Studio specific, you may need to adjust for other platforms *)
[<EntryPoint>]
let main argv = 
    (* DEFINE vars and functions for 0-1 knapsack *)

                 (* These are deduced to be DiscreteVar record types *)
    let vars = [|{Name = "food"; Setting = Unset; Weight = 5.0; Utility = 8.0}; 
                 {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 multiplySumEither b v = 
        Array.map (fun vElem -> (if b then vElem.Utility else vElem.Weight) * match vElem.Setting with
                                                                              | One -> 1.0
                                                                              | _ -> 0.0 ) v |> Array.sum
    let multiplySumWeight = multiplySumEither false
    let multiplySumUtility = multiplySumEither true

    let estimator wlimit vars =
        // assume vars are sorted in decreasing utility/weight ratio
        let assignedUtility = multiplySumUtility vars
        let remainingWeight = wlimit - multiplySumWeight vars
        let (leftOverWeight,unassignedUtilityEstimate) = 
            Array.fold (fun acc var -> match acc,var.Setting with
                                       | (_,accUtil),Zero  
                                       | (_,accUtil),One
                                       | (0.0,accUtil),_ -> (fst acc, accUtil)
                                       | (accWt,accUtil),varSetting -> 
                                           if accWt >= var.Weight then
                                              (accWt - var.Weight, accUtil + var.Utility)
                                           else 
                                              let frac = var.Weight / accWt
                                              (0.0, accUtil + frac * var.Utility)
                       ) (remainingWeight,0.0) vars

        assignedUtility + unassignedUtilityEstimate

    let gknap = estimator weightLimit   // this is new

    let (solutionUtility, solutionVars) = BandB multiplySumUtility gknap vars -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

Notice the appearance of the now-generalized objective function f on line 72 and of the upper bound estimator on lines 55 and 56. These are defined in the invocation at line 125. This is not a bad change, but we see the issue on line 74. This line used to only take the improved value for f if the weight of f was within wlimit. But we removed wlimit as an argument baking that into the g function. wlimit is a parameter of the 0-1 knapsack but not of general branch and bound optimization problems so we don’t want to add it back to the argument list of BandB, but what if we baked that into f just as we did for g?

This idea will be changed later, but this shows additional usage of partial function application

Well, we don’t want f to be acceptable if the weight limit is not met, so what if we re-created a new f that returns -infinity (or the smallest negative number) if the weight limit is not met? So our new portion of the main code would be adapted as:

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

let gknap = estimator weightLimit   // this is new
let knapLimited wlimit vars =
    let w = multiplySumWeight vars
    if w <= wlimit then (multiplySumUtility vars) else System.Double.NegativeInfinity

let fknap = knapLimited weightLimit

let (solutionUtility, solutionVars) = BandB fknap gknap vars -1.0
printfn "Best Utility = %f" solutionUtility
for var in solutionVars do
    printfn "%A" var

The knapLimited function does just what we thought, and we then create fknap using it with the particular weight limit for our problem instance baked in. However, when we run this we still have a problem … recall that the estimator for 0-1 knapsack required the variables in decreasing order of utility/weight ratio. The user variables as defined are not in such an order. We could fix this by sorting the var array before passing it to BandB but this doesn’t seem right. The general BandB routine should not require variables in a particular order, although it is perfectly fair that the f and g functions for a particular problem instance type would.

1: 
2: 

let varsSorted = (Array.sortBy (fun elem -> -elem.Utility / elem.Weight) vars)
let (solutionUtility, solutionVars) = BandB fknap gknap varsSorted -1.0

Nevertheless, the above will fix the problem, but let’s revisit this later; on to page 2