D<scp>iversi</scp>T<scp>ree</scp>: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems

DOI10.1287/IJOC.2022.0164arXiv2204.03822OpenAlexW4386027258MaRDI QIDQ6202331FDOQ6202331

Authors: Hugh R. Medal, Andrew C. Trapp 

Publication date: 26 March 2024

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2204.03822

Recommendations

• How to select a small set of diverse solutions to mixed integer programming problems
• Generating Multiple Solutions for Mixed Integer Programming Problems
• Diversity Maximization Approach for Multiobjective Optimization
• Enriching Solutions to Combinatorial Problems via Solution Engineering
• A simple and effective algorithm for the MaxMin diversity problem

zbMATH Keywords

integer programmingdiversitynear-optimal solutionsnode-selection rules

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

This page was built for publication: D<scp>iversi</scp>T<scp>ree</scp>: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202331)