Before delving into the more general branch and bound algorithm in F#, let’s try one to implement the simpler 0-1 Knapsack problem using branch and bound techniques. This problem mimics the idea of a person trying to pack a limited weight (or space) bag (knapsack) with items such that their total value (utility) is maximized. Mathematically, it is formulated as:
0-1 Knapsack definition
Here, there are n variables each denoted as vi. Likewise there are n weights associated with each item and n utility (value) settings for each, denoted wi and ui respectively. Note that the terminology used here differs from the Wiki link above in that variable, weight and utility indices go from 0 to n-1 to be more in line with computer array indexing and the value is denoted with u instead of c.
0-1 Knapsack has a pseudo-polynomial solution approach, but here we are focused on applying a branch and bound approach. Later we will look at other problem types.
Short Description of Branch and Bound
Before getting back to the case of the knapsack problem it will help to understand how branch and bound works. Consider the following search tree diagram:
Branch and Bound Illustration
Deciding on the selection of each variable can be viewed as a tree structure, where each branch is a variable selection and each node represents the setting (or non-setting) of each variable. At the top of the tree, all of the variables are unset. In the drawing, we have a case of three variables (indexed from 0 to 2). At each level of the tree one variable is decided (set). As an example, if you follow the red line from the top to the bottom, the variables are set to v0 = 0, v1 = 1, and v2 = 1. At the bottom level, all of the variables are set and therefore a value of the knapsack and a weight of the knapsack can be computed (see Eq 1). At any intermediate node other than the bottom layer, at least one variable remains to be set. There are 2n nodes at the bottom layer, that is all the combinations of n variables, in the figure n=3 so there are 8 in that case. And there are 2n+1-1 nodes in the whole graph for any n variables.
Notice that the nodes at the bottom are labeled with ‘U’ and the rest as ‘G’. This is meant to imply that nodes with complete settings have a particular utility while the rest (the ‘G’s) have only estimates; we will later be using a function named g hence the G moniker, but that is getting ahead of ourselves.
Programming
A first step is deciding how to represent the problem domain in code or the type system. We see that we have three arrays to represent, each with a cardinality of n. The weights and utilities could be either integers or floating point values, let’s choose the more inclusive floating point (float in F#). The variables of our domain can be either zero or one, or in the case of branch and bound unset. This leads us to determine how to represent (the type) the variables of our problem. We have decided to type the variables as DiscreteVar.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: |
(* this is setting for a variable of the problem *) type ZeroOneVarSetting = | Unset (* this is a discriminated union type in F# *) | One | Zero (* this is a variable of the problem. Each var has a Name and mutable v*) type DiscreteVar = { (* this is a record type in F# *) Name : string; mutable Setting : ZeroOneVarSetting; // discrete value setting } |
I assume that you know the basics of F#
We used a discriminated union type to capture the possible settings for a variable as either Unset, Zero or One, makes sense. Then, the DiscreteVar is a record type with a Name and Settings that use this type. To define a problem instance, we might use something like:
Arrays are denoted with [| |] while lists are denoted as [ ], each with elements separated with semicolons.
1: 2: 3: 4: 5: 6: 7: |
let vars = [|{Name = "food"; Setting = Unset}; {Name = "tent"; Setting = Unset}; {Name = "gps"; Setting = Unset }; {Name = "map"; Setting = Unset} |] let weights = [|5.0; 14.5; 1.0; 0.5 |] let utilities = [| 8.0; 5.0; 3.0; 3.0 |] let weightLimit = 20.0 |
Notice that each of vars, weights and utilities are array types. Another choice might be to make them lists. F# arrays allow for modification of an element, while lists do not. If we want to change an element of a list we need to extract the elements leading up to the element to be changed, concatenate this with the new element and then concatenate the rest and assign this to a new variable (see topic). Array sizes are fixed, but that works since once we define a problem set (as above) the size of these arrays doesn’t need to change. We make the setting for the variable mutable since we think we need to change it later. These are our ideas at this point anyway.
The approach throughout is to start with something and refine it as we go along.
Notice that we never defined the type of element that vars contains. F# deduces that the type of element is a record type and furthermore that the type is DiscreteVar based on seeing that these record names match in these record expressions (see topic). OK, let’s write a function to determine the total utility.
1: 2: 3: 4: 5: 6: |
let utility u v = let products = Array.map2 (fun uElem vElem -> uElem * vElem) u v Array.sum products let tv = utility utilities vars |
Line 1 defines a function named utility which takes two arguments named u and v. At this point we haven’t declared what types u and v are, and the compiler deduces their type from the body of the function and from subsequent uses. In fact, if you put that code into F#, the utility definition is fine until you add the invocation at line 5. Before adding line 5, the compiler thinks of the function as:
Type Deduction
That is, it knows that u and v are arrays, given their appearance as arguments to the Array.map2 function; it also knows that the array elements must allow the (*) operator so it chooses int as the array element type sans other information. Recall that Array.map2 takes as arguments a function that accepts two arguments and produces a value; the two arrays which must be of the same length. However, when we add the line 5 content, an error arises:
Type Mis-Deduction
Now, the compiler sees that the u argument is a float array, and then sees that it cannot apply the (*) operator to a float and a DiscreteVar (since v is a DiscreteVar array in this instance). So, its important to realize that function and data type deduction ‘looks’ at the whole content, including code that comes later. Function arguments that are not explicitly typed are generic arguments (think ala C++ templates but without the template keywording); these will prove very useful as they allow definition of functions that are flexible in their argument types. But enough about general F# typing for now, let’s fix our problem.
TIP: You can explicitly type function arguments to force their interpretion within the function body, and then fix invocations. Once all that works you can try to remove these declarations to make the code neater and more flexible — although sometimes F# does need type ‘hints’
So how are we going to develop utility? Let’s re-write utility such that it accepts an array of floats and an array of DiscreteVar like so …
1: 2: 3: 4: 5: 6: 7: 8: |
let utility u v = let products = Array.map2 (fun uElem vElem -> uElem * match vElem.Setting with | One -> 1.0 | _ -> 0.0 ) u v Array.sum products let tv = utility utilities vars printfn "%f" tv |
In the mapping function, the second argument is still a DiscreteVar but we use pattern matching to derive a float value from the discriminated union type. In this case, the pattern One produces a 1.0 and otherwise a 0.0 results since Unset and Zero will match the _ default pattern. The result is that products is an array of floats such that it is the pairwise product of the u array and 1.0 whereever vElem.Setting is One. Each member of this result (which is a float array) is then summed using the Array.sum method to produce a float result (remember that the final expression of a function is its return value). If we run this and examine the result as is we get 0.0, of course this is because all of the variables are Unset and thus a multicand of 0.0 is produced for each vElem in the expression.
We next realize that multiplying weights and the variables is the same function, so let’s rename it multiplySum. We also don’t need the intermediate value products and instead pipe (|>) the result of the pairwise multiplication to the Array.sum. We could apply this function using either utility or weight as the first argument.
1: 2: 3: 4: 5: 6: 7: |
let multiplySum x v = Array.map2 (fun xElem vElem -> xElem * match vElem.Setting with | One -> 1.0 | _ -> 0.0 ) x v |> Array.sum printfn "%f" (multiplySum utilities vars) printfn "%f" (multiplySum weights vars) |
The printfn function examines the format string and makes sure that the number and type of arguments match the wildcard patterns
In the multiplySum printfn statements, you must use parens to make the function application with its arguments into a single argument for the print, otherwise its three arguments. Of course, both of these would still produce 0.0.
We have a sense of some of the code that we may use, but then notice that the arrays for variables, weights and utility be the same length. Furthermore the next incremental change is then realizing that weight and utility are really factors of a knapsack item. Therefore, we adjust the definitions and get to this:
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: |
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; mutable Setting : ZeroOneVarSetting; // discrete value setting } 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 = 20.0 let multiplySumWeight v = Array.map (fun vElem -> vElem.Weight * match vElem.Setting with | One -> 1.0 | _ -> 0.0 ) v |> Array.sum let multiplySumUtility v = Array.map (fun vElem -> vElem.Utility * match vElem.Setting with | One -> 1.0 | _ -> 0.0 ) v |> Array.sum printfn "%f" (multiplySumWeight vars) printfn "%f" (multiplySumUtility vars) |
OK, the item definitions seem better suited to the domain at hand — using the type system hand-in-hand with the problem domain is called domain driven design. One concept from this idea is to use the type system to disallow invalid states or variable settings. We see this in small part in the ZeroOneVarSetting as the only choices are one of the three discriminants. If instead we used, say, an int type to represent the state of our variable, assuming that the value would be -1 for Unset, 0 for Zero and 1 for One, what would the meaning be if the int took on a value of 7 or -4? In the F# discriminated union approach, there is simply no opportunity for such erroneous or unexpected settings.
Unfortunately however, the two functions for getting the total weight and utility seem redundant varying only in which record member is used in the multiplication. Let’s revisit this again, this time creating a two argument function multiplyEither with a first argument of boolean that selects Utility if true and Weight otherwise.
1: 2: 3: 4: 5: 6: |
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 |
The idiomatic or canonical approach to leveraging functional style is often discussed in regard to F# code. See this and this for more
We then create our multiplySumWeight as multiplyEither true and multiplySumUtility false. This demonstrates an important feature of functional programming, namely partial function application. multiplySumWeight is multiplyEither with the first argument of true ‘baked in’; it only has one argument now the DiscreteVar array. That is the type for multiplySumWeight is DiscreteVar [] -> float, the type for multiplyEither is bool -> DiscreteVar [] -> float. Notice that we never told multiplyEither what type its argument b is, a Boolean type (bool) is deduced from its use as the test in the if expression (and the partial applications that use actual arguments of true and false). There are other variations for doing these accumulating products that could be used too, but for now we will leave it here.
With some of the functionality we need to address the problem, on to page 2.