Combinatorial Models

There is a large class of models that are very different from the models discussed so far. Models where the outputs involve changing the order of existing input variables, or grouping subsets of the inputs, are called combinatorial models.

These problems are usually very difficult to solve because they often require exponential time; that is, the amount of time needed to solve a problem with 4 variables might be 4 x 3 x 2 x 1, and doubling the number of variables to 8 raises the solving time to 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1, or a factor of 1,680. The number of variables doubles, but the number of possible solutions that must be checked increases 1,680 times. For example, choosing the starting lineup for a baseball team is a combinatorial problem. For 9 players, you can choose one out of the 9 as the first batter. You can then choose one out of the remaining 8 as the second batter, one of the remaining 7 will be the third, and so on. There are thus 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 (9 factorial) ways to choose a lineup of 9 players. This is about 362,880 different orderings. Now if the number of players is doubled, there are 18 factorial possible lineups, or 6,402,373,705,000,000 possible lineups!

The Evolver and RISKOptimizer algorithms, Genetic Algorithm and OptQuest, are both capable of intelligently searching through the possible permutations. This is much more practical than searching through all possibilities, and it is much more efficient than examining purely random permutations.