Weighted by Probability Computational Details:
To illustrate our approach, we begin with the formula for computing the likelihood of selecting an item from a set of items (of average utility) equal in size to that shown in the MaxDiff questionnaire. We zero-center the raw HB scores such that the average item has a score of 0. Since e0 is equal to 1, the likelihood of selecting item i from a set involving a - 1 other items of average desirability is:
Pi = eUi / (eUi + a - 1)
It is easy to expand this equation to include more items. For example, the likelihood that a portfolio containing items i, j, and k reaches the respondent is:
Pijk = (eUi + eUj + eUk) / (eUi + eUj + eUk + a - 1)
Exhaustive TURF Limitation:
With an exhaustive search, the number of portfolios that the TURF procedure must evaluate can become extremely large. Currently, we have placed a limitation of 5,000,000 portfolios to evaluate exhaustively in any one TURF run. If you specify a run that exceeds this limit, the software will automatically switch to a stepwise algorithm (explained below). The formula to determine how many portfolios the exhaustive TURF procedure must process is as follows.
m! / n!(m-n)!
where:
m is the total number of items in your study
n is the size of the portfolio to optimize
For example, searching for an optimal portfolio of 5 items from 50 leads to 2,118,760 possible portfolios to evaluate, which the Analyzer will do exhaustively. But, searching for 6 items out of 50 leads to 15,890,700 possible portfolios, which exceeds the limit and will therefore be solved using the stepwise algorithm.
Stepwise TURF Algorithm
One of the challenges with TURF is dealing with truly large spaces of potential portfolio combinations. For example, choosing the optimal 12 flavors out of 70 involves examining over 10 trillion possible 12-flavor combinations (if using an exhaustive algorithm which examines each possible one). Such problems are hard to solve within reasonable time limits if using exhaustive search. Researchers often rely on heuristic search algorithms that can find nearly-optimal solutions in a fraction of the time required to exhaustively search for the globally optimal solution.
For large TURF problems (where there are more than 5,000,000 possible sets to search if solving exhaustively) the analyzer will use a Stepwise algorithm. Stepwise TURF searches for the optimal portfolio in incremental steps, taking the best result from the previous step forward to the next step. For example, searching for 12 flavors out of 70 could be done in three steps:
•Step 1: Find the best 4 flavors out of 70 using exhaustive search (916,895 portfolios to exhaustively search)
•Step 2: Force the best 4 flavors from step 1 into the search; use exhaustive search to find the next best 4 flavors to add to those previous 4 (720,720 portfolios to examine)
•Step 3: Force the 8 flavors from steps 1 and 2 into the search; use exhaustive search to find the next best 4 flavors to add to those previous 8 (557,845 portfolios to examine)
Breaking the problem into three steps of 4, 4, then 8 flavors leads to 2,195,460 portfolios to search (rather than 10 trillion), which takes less than 1 minute. However, we are not assured of finding the optimal solution. And, if we are interested in reviewing the top dozen portfolios, there isn't a guarantee that we've done a very good job at finding any of global top dozen solutions. Early decisions in the stepwise procedure corner us into a fraction of the search space, and prohibit us from looking elsewhere for better solutions. So, we don't stop searching just yet.
To further improve upon the stepwise procedure, we take a few more seconds to examine hundreds of potential item swaps (Fedorov swaps) that could lead to better reach. We take the top several dozen portfolios found in the stepwise routine, and we try swapping non-included flavors for included flavors one at a time, looking for new portfolio definitions that increase the reach. It turns out that these last few seconds spent conducting Fedorov swaps can improve the results quite dramatically.
For more information on the stepwise TURF procedure, see Stepwise TURF + Swaps.