The next issue to tackle is the branching part in the body of the BandB
code. As it stands it is specific to discrete variables with two states (since we create varArrayZero
and varArrayOne
only) and adjust the queue based on an active pattern. To address this, suppose we instead created a generalized branch function that takes a given partial variable setting state (node in the tree) and creates the queue entries? The invoker of BandB
would supply this function and BandB
itself would be quite generalized. Here is our new branch and bound function:
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: |
let BandB f g branch 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 while not queue.IsEmpty do match queue with | curVars :: restOfQueue -> if anyUnset curVars then let toQueue = branch g bestUtility curVars queue <- toQueue @ restOfQueue numberOfQueues <- numberOfQueues + toQueue.Length else let util = f curVars numberOfEvals <- numberOfEvals + 1 if util > bestUtility then (* Any assumptions? *) bestUtility <- util bestVars <- curVars 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, bestVars) |
??? If you reverse lines 15 and 16, then you get a compiler error saying that toQueue
cannot be resolved and needs type annotations, even though it does seem to have the correct type.
As can be seen, the routine now closely follows a generalized branch and bound algorithm. The core branch and bound routine requires a means for determining if all variables are unset (i.e., if not all decisions have been made), which is provided with the test using the anyUnset
routine, a branching mechanism which is provided as an input function branch
as well as an objective function evaluator f
and upperbound limit function g
.
The branch
function uses the upper bound estimator g
the current best solution found and a partially set variable array to determine additional queue items. This is also in line with how the general algorithm works.
The anyUnset
function can take advantage of the Array.exists function that tests if any member of the array satisfies the predicate, which for us is determining if any variable is Unset
.
1: 2: |
let anyUnset vars = Array.exists (fun elem -> elem.Setting = Unset) vars |
Now let’s look at the invocation of this new format; many of the routines we had before are the same …
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: |
(* *************************************************************************************** *) (* KNAPSACK INSTANCE *) 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 (* *** 0-1 KNAPSACK FUNCTIONS *** *) 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 // we can't use _,accUtil,Zero here - that's a 3-tuple | (_,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 knapLimited wlimit vars = let w = multiplySumWeight vars if w <= wlimit then (multiplySumUtility vars) else System.Double.NegativeInfinity let fknap = knapLimited weightLimit (* 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 (* 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 let branchknap 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 // update the queue match (gEstimateZero, gEstimateOne, bestUtility) with | TakeBoth -> varArrayOne :: [varArrayZero] | TakeZeroOnly -> [varArrayZero] | TakeOneOnly -> [varArrayOne] | _ -> [] // Neither case, nothing (* *************************************************************************************** *) (* Invoke *) let varsSorted = (Array.sortBy (fun elem -> -elem.Utility / elem.Weight) vars) // still have this let (solutionUtility, solutionVars) = BandB fknap gknap branchknap varsSorted -1.0 printfn "Best Utility = %f" solutionUtility for var in solutionVars do printfn "%A" var |
The gknap
function (line 36) is our estimator with the weight limit for a problem instance built in. Also the fknap
function, as before, is designed to return -infinity when the solution is not feasible, in this case when the assigned weight is greater than the limit. That was why we introduced knapLimited
(line 37). But should we saddle the f
function like this, what if instead we re-designed g
so that infeasible solutions (as portions of the search space) would never get queued? This would be a bit more efficient as well. Then f
could be designed assuming that the solution is feasible and we would go back to using the simple multiplySumUtility
we started with. So here is a revised estimator
function:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: |
let estimator wlimit vars = // assume vars are sorted in decreasing utility/weight ratio let assignedUtility = multiplySumUtility vars let remainingWeight = wlimit - multiplySumWeight vars if remainingWeight < 0.0 then -1.0 // we are already over the weight limit, else let (leftOverWeight,unassignedUtilityEstimate) = Array.fold (fun acc var -> match acc,var.Setting with | (_,accUtil),Zero // we can't use _,accUtil,Zero here - that's a 3-tuple | (_,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 |
with invocation (note the use of the simpler multiplySumUtility
function is back in place of fknap
):
1:
|
let (solutionUtility, solutionVars) = BandB multiplySumUtility gknap branchknap varsSorted -1.0 |
we now have:
1:
|
BandB: total settings queued = 13, total number of evals: 1 |
we have cut down the number of nodes queued to 13 from 16 and only needed to do one function evaluation rather than 4. So this design between f
and g
is a bit better, but either one works.
Download code so far
Before adding other optimization types and examples, let’s see how to organize F# code