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