Learning F#: Case study with branch and bound – PART II
OpCoast © 2016
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 () and upperbound estimator () are to be passed in, assuming that they operate as being applied to vars. We already know the function here for 0-1 knapsack, its just multiplySumUtility (or is it?), but we don’t have yet. Well, 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 | Zerotype 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 = curVars |> Array.mapi (fun index var -> if index = unsetVarIndex then {var with Setting = Zero} else var) let varArrayOne = 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 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 if the weight of was within wlimit. But we removed wlimit as an argument baking that into the 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 just as we did for
This idea will be changed later, but this shows additional usage of partial function application
Well, we don’t want to be acceptable if the weight limit is not met, so what if we re-created a new 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 newlet knapLimited wlimit vars = let w = multiplySumWeight vars if w <= wlimit then (multiplySumUtility vars) else System.Double.NegativeInfinitylet fknap = knapLimited weightLimitlet (solutionUtility, solutionVars) = BandB fknap gknap vars -1.0printfn "Best Utility = %f" solutionUtilityfor 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 |
Download code so far
Nevertheless, the above will fix the problem, but let’s revisit this later; on to page 2