Diverse Sets of Near-Optimal Solutions

This direction is merged into another direction: quality-diversity trade-off (quality-diversity tradeoff). Its last version stays readable and citable here.

Version 1 of 119 papers23 conceptsfrozen 2026-10-04

In traditional optimization, the goal is usually to find the single best solution to a problem. However, in real-world decision-making, the "optimal" solution identified by a model is often fragile. Models are simplifications; they may omit subtle constraints, user preferences, or environmental uncertainties. If the single best solution proves unfeasible in practice, the decision-maker is left with nothing.

A growing body of research suggests a shift in focus: instead of finding one "best" solution, we should find a diverse set of high-quality solutions. This approach ensures that if one solution fails, others are available that are both performant and fundamentally different in their composition.

The Dual Constraint Framework

To find a set of solutions that are both good and different, researchers have converged on a two-part constraint system. Linnea Ingmar, Maria Garcia de la Banda, Peter J. Stuckey, and Guido Tack formalize this in Modelling Diversity of Solutions by distinguishing between two types of diversity requirements:

  1. Intra-diversity (Quality): Each individual solution in the set must meet a minimum performance threshold. It must be "near-optimal," falling within a certain percentage of the best possible score.
  2. Inter-diversity (Separation): The solutions in the set must be sufficiently different from one another, measured by a distance metric (such as Hamming distance for discrete choices).

By separating these requirements from the core solving logic, practitioners can explore the trade-offs between how "good" the solutions are and how "different" they are.

Filtering for "Good Enough" Solutions

The first challenge is defining the boundaries of the "near-optimal" region. In complex, multi-objective landscapes, this is often done using an epsilon-dominance mechanism.

As explored by Wenhua Li, Xingyi Yao, and their colleagues in Coevolutionary Framework for Generalized Multimodal Multi-objective Optimization, epsilon-dominance acts as a filter. It allows an algorithm to retain solutions that are not strictly the best but are within a tolerance level ($\epsilon$) of the global optimum. This creates a "quality envelope" that captures both global and local optima, providing a pool of candidates that are all "good enough" to be considered.

Statistical Guarantees and Greedy Selection

In fields like recommendation systems, the "quality" of a solution isn't just a score—it's a statistical guarantee. Anastasios N. Angelopoulos, Yixin Wang, Stephen Bates, and Michael I. Jordan address this in Recommendation Systems with Distribution-Free Reliability Guarantees.

Their framework uses a "Learn then Test" calibration to ensure that a set of recommendations meets a specific reliability target (like a maximum False Discovery Rate). Once this pool of statistically "safe" items is identified, they apply a greedy pruning algorithm to select a subset that maximizes diversity.

This sequence—verify quality first, then maximize diversity—is a recurring motif across the research. It ensures that diversity is never achieved at the expense of fundamental performance or safety requirements.

Why It Works: Robustness through Variety

The intuition behind this research direction is that diversity is a hedge against model incompleteness. If we only find the single best solution to a mathematical model, we are betting entirely on that model's perfect alignment with reality. By instead finding a set of $k$ solutions that are spread across the search space but all reside within a high-quality "plateau," we provide decision-makers with a menu of robust alternatives. Whether in constraint programming, evolutionary optimization, or machine learning recommendations, the goal is the same: providing variety without sacrificing excellence.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_diverse_sets_of_near_optimal_solutions_b1230131,
  title = {Diverse Sets of Near-Optimal Solutions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diverse-sets-of-near-optimal-solutions/rdr_b1230131116841a3bdf1e03bd9712447},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_diverse_sets_of_near_optimal_solutions_b1230131_v1,
  title = {Diverse Sets of Near-Optimal Solutions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diverse-sets-of-near-optimal-solutions/rdr_b1230131116841a3bdf1e03bd9712447/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}