Learning F#: Case study with branch and bound – Part II (page 2)

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