# DiversiTree: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems

arXiv: https://arxiv.org/abs/2204.03822 · HTML: https://mlsanity.com/paper/2204.03822/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 57 references that are in the map.
- First posted on arXiv 8 Apr 2022.

## Builds on (most cited first, 9 of 9)

- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [One Solution is Not All You Need: Few-Shot Extrapolation via Structured MaxEnt RL](https://mlsanity.com/paper/2010.14484/) (2020)
- [Discovering Diverse Nearly Optimal Policies with Successor Features](https://mlsanity.com/paper/2106.00669/) (2021)
- [Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory](https://mlsanity.com/paper/1903.07410/) (2019)
- [On the Linear Ordering Problem and the Rankability of Data](https://mlsanity.com/paper/2104.05816/) (2021)
- [Blind Image Deblurring based on Kernel Mixture](https://mlsanity.com/paper/2101.06241/) (2021)

## Built on by (most cited first, 2 of 2)

- [A Path to Simpler Models Starts With Noise](https://mlsanity.com/paper/2310.19726/) (2023)
- [Balancing Optimality and Diversity: Human-Centered Decision Making through Generative Curation](https://mlsanity.com/paper/2409.11535/) (2024)

## Abstract (arXiv)

While most methods for solving mixed-integer optimization problems compute a single optimal solution, a diverse set of near-optimal solutions can often lead to improved outcomes. We present a new method for finding a set of diverse solutions by emphasizing diversity within the search for near-optimal solutions. Specifically, within a branch-and-bound framework, we investigated parameterized node selection rules that explicitly consider diversity. Our results indicate that our approach significantly increases the diversity of the final solution set. When compared with two existing methods, our method runs with similar runtime as regular node selection methods and gives a diversity improvement between 12% and 190%. In contrast, popular node selection rules, such as best-first search, in some instances performed worse than state-of-the-art methods by more than 35% and gave an improvement of no more than 130%. Further, we find that our method is most effective when diversity in node selection is continuously emphasized after reaching a minimal depth in the tree and when the solution set has grown sufficiently large. Our method can be easily incorporated into integer programming solvers and has the potential to significantly increase the diversity of solution sets.