Understanding optimization methods
Exact methods prove the best answer. Heuristic methods find a strong answer efficiently. Which to use depends on the scale of the problem and the confidence the decision requires.
How it works
Optimization methods find the best combination of elements from a defined set, subject to whatever constraints apply. The right approach depends on the size of the problem and the confidence the decision requires. Exact methods evaluate the full solution space or use pruning logic to prove no better answer exists. Heuristic methods search efficiently and return strong solutions without guaranteeing optimality.
The tradeoff applies across problem types, from TURF item selection to choice model product design. When the output will directly drive a significant business decision, exact methods or near-exact heuristics with multiple runs are preferred.
Exact vs. heuristic
Exact methods become computationally expensive as the problem grows. Heuristic methods scale well but cannot confirm the solution is the best possible. The practical difference matters, and the sections below describe each approach in detail.
For most research applications, item sets are small enough for exact methods. Heuristic methods become necessary when item sets are large or portfolio configurations are complex.
Exact methods
Full enumeration tests every possible combination in the solution space. It guarantees the optimal solution and is simple to verify. For a 20-item set with a target bundle of 5, there are 15,504 combinations. This is fast by any standard. As the problem grows, the combination count grows quickly and enumeration becomes impractical.
Branch-and-bound search finds the optimal solution more efficiently by eliminating branches of the search tree that cannot beat the current best result. When the algorithm determines a partial solution cannot lead to a stronger outcome than the best complete solution found so far, it prunes that branch and moves on. For many structured problems, branch-and-bound reaches the global optimum substantially faster than enumeration. Performance depends on the structure of the problem and how early strong solutions are found.
Filtered enumeration reduces the search space before optimization begins. The analyst specifies which combinations are infeasible or off-limits, and the search runs only over the remaining space. When the filtered space is small enough, enumeration is exact over all feasible combinations. When it is still too large, filtered enumeration can be combined with heuristic methods to search the reduced space. This approach is most valuable when the full solution space is too large for unconstrained enumeration but the analyst can identify infeasible combinations in advance.
Heuristic methods
Stepwise plus swaps builds a solution incrementally by adding the element contributing the most at each step, then tests whether swapping any included element for an excluded element would improve the result. The swap phase makes this more robust than a pure greedy approach. It is practical for large problems and consistently produces strong solutions.
Beam search retains multiple promising partial solutions at each step rather than committing to a single path. The number of paths retained is the beam width. A wider beam reduces the risk of locking in a suboptimal direction early but increases computation time. Beam search is useful when multiple near-optimal solutions may exist and the search should explore more of the space than a single greedy path would cover.
Monte Carlo plus swaps samples many candidate solutions randomly, evaluates each, and applies local swap improvements to the strongest candidates. Because results depend on random sampling, a seeded implementation is important for reproducibility. This method is well-suited to very large or difficult search spaces where structured traversal is impractical.
Genetic algorithms maintain a population of candidate solutions and improve them over successive generations. Each generation evaluates the fitness of each candidate, selects high-performing candidates as parents, creates new candidates by combining elements of parent solutions, and introduces random mutations to maintain diversity. Because the algorithm maintains a population rather than following a single path, it explores multiple regions of the solution space simultaneously and is less likely to converge on a local optimum. Genetic algorithms are well-suited to large, complex search spaces where the solution involves multiple interacting dimensions.
Greedy forward search selects the strongest element first, locks it in, then selects the next-strongest incremental contributor given the current solution, and repeats until the target size is reached. It is fast, transparent, and easy to explain to nontechnical audiences. It is also the least reliable when overlap or interaction effects create situations where the locally optimal choice at each step leads to a weaker final solution. Best used when speed and transparency matter more than search depth.
Method selection by problem type
TURF and reach optimization selects K items from a fixed set of N. The search space is the set of all possible K-item combinations. For most research applications, item sets are small enough for exact methods. Full enumeration and branch-and-bound handle the typical problem size without difficulty. When item sets are larger or the project requires fast scenario turnaround, stepwise plus swaps and beam search produce strong results. Greedy forward search is an option when transparency and speed are priorities.
Choice model product optimization designs product configurations by selecting attribute levels and then optimizes which configurations to offer as a portfolio. The search space is defined by all possible attribute-level combinations across all products, and many of those combinations may be infeasible. Genetic algorithms and Monte Carlo plus swaps are effective because they explore diverse configurations without requiring structured traversal of the full space. Filtered enumeration reduces the space to feasible configurations before the search begins, making exact or near-exact methods practical for problems that would otherwise require heuristic search.
Technical notes
Combinatorial scale
The number of possible K-item combinations from N items is N! / (K! × (N−K)!). At N=20 and K=5, this is 15,504. At N=50 and K=10, it exceeds 10 billion. At N=100 and K=10, it exceeds 10 trillion. The count peaks when K is near N/2 and decreases as K approaches 1 or N.
The growth rate determines when exact methods become impractical. Branch-and-bound pruning reduces the effective search space considerably for well-structured problems, but worst-case performance can approach full enumeration on difficult problem structures.
Branch-and-bound pruning
Branch-and-bound maintains an upper bound on the value any partial solution can achieve. If a partial solution already scores lower than the best complete solution found so far, even the best remaining elements cannot improve it, and the branch is pruned.
Efficiency depends on how tight the upper bound is and how early strong solutions are found. Seeding the search with a greedy or stepwise result before beginning the exact search tightens the bound and allows more aggressive pruning. On well-structured problems, branch-and-bound can approach greedy speed. On difficult problems, it may approach enumeration cost.
Greedy path dependence
Greedy forward search selects locally optimal elements at each step. This can produce a globally suboptimal solution when overlap or interaction effects create traps. Consider three items A, B, and C. A and B each score well individually but largely overlap. C scores lower individually but covers a distinct segment. Greedy selects A first, then B as the next-strongest incremental contributor. C may never be selected. A stronger solution of A and C is missed.
Swap logic partially corrects for this. After building a greedy solution, testing whether replacing any included element with an excluded element improves the result can recover some missed solutions. Stepwise plus swaps is preferred over pure greedy for this reason.
Beam width
Beam search retains the top B partial solutions at each step, where B is the beam width. At B=1, beam search is equivalent to greedy forward search. As B increases, the algorithm explores more of the solution space. Computation time scales with the beam width.
There is no universal optimal beam width. Wider beams are more useful when the best final solution requires an element that a greedy approach would not select early, meaning the optimal path diverges from the greedy path near the start of the search. For most applications, a moderate beam width produces strong solutions without significant computation cost.
Monte Carlo reproducibility
Monte Carlo plus swaps samples candidate starting solutions randomly. Without a fixed seed, results vary across runs on the same data. A seeded implementation fixes the random starting points, making results reproducible. The seed value should be recorded alongside other run parameters so any result can be reproduced exactly. Solution quality improves with more samples and more swap iterations per candidate; the right settings depend on problem size and the confidence level the project requires.
Genetic algorithm mechanics
A genetic algorithm represents each candidate solution as a chromosome. In reach optimization, this is a set of item indicators. In product optimization, it is a set of attribute-level selections defining a configuration. The algorithm initializes a population of random candidates and proceeds through generations. Each generation involves fitness evaluation, selection of high-fitness parents, crossover to produce child solutions by combining parent elements, and mutation to introduce random variation.
Elitism preserves the best solutions found so far by carrying them forward unchanged into the next generation. Without elitism, the algorithm can lose strong solutions through crossover or mutation. Key parameters include population size, crossover rate, mutation rate, and the number of generations. Larger populations and more generations improve solution quality but increase computation time. Convergence is assessed by monitoring whether the best fitness score continues to improve across generations.
Filtered enumeration
Filtered enumeration requires the analyst to define feasibility rules before the search begins. Rules typically specify element combinations that cannot appear together in a solution. For example, a luxury positioning paired with the lowest price tier might be ruled infeasible, or a feature combination that cannot be manufactured might be excluded.
The filter can reduce the solution space dramatically. A product design problem with five attributes at four levels each produces 1,024 possible configurations per product. Feasibility filtering may reduce this to a fraction of the full space, bringing exact enumeration within reach. When the filtered space remains too large for exact search, the same heuristic methods can be applied to the reduced space. The filter operates as a preprocessing step rather than a replacement for the optimization algorithm.