﻿ 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 tool 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 flavors each 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 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 in swapping can improve the results quite dramatically.