Generating Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems

Author

Izuwa C. Ahanor, University of Tennessee, KnoxvilleFollow

Date of Award

12-2023

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Industrial Engineering

Major Professor

Hugh Medal

Committee Members

Hugh Medal, James Ostrowski, Mingzhou Jin, Andrew C. Trapp

Abstract

Mixed-integer optimization problems (MIPs) pose a class of challenges crucial to a range of real-world applications, from space exploration to healthcare. Traditional approaches to solving MIPs have predominantly focused on identifying a single optimal solution, neglecting the considerable advantages of generating a Diverse Rashomon set—a set of diverse near-optimal solutions. This dissertation aims to bridge the gap between conventional optimization methods and emerging machine learning paradigms, thereby significantly enhancing both the speed and diversity of near-optimal solution sets in MIPs.

The first part of the dissertation introduces an innovative approach for incorporating diversity into node selection within a branch-and-bound framework. Experimental results indicate that our method surpasses conventional node selection rules, such as best-first search, achieving diversity improvements ranging from 12\% to 190\%. This portion of the work elucidates the branch-and-bound tree exploration techniques that emphasize diversity during the MIP-solving process.

The second part of the dissertation adopts graph neural networks (GNNs) to further accelerate and diversify the generation of near-optimal solutions. The research establishes that traditional methods follow a sequential node-by-node exploration to solve and generate near-optimal solutions for MIPs. Given the expansive solution space typically associated with MIPs, this sequential approach falls short of covering the near-optimal solution landscape adequately. To overcome this limitation, we employ machine learning in the form of generative models trained to produce near-optimal solutions across the entire solution space.

In both segments of the dissertation, the merits of generating a Diverse Rashomon set—a collection of diverse near-optimal solutions—are discussed. Such a set offers a robust ensemble of solutions applicable to various domains. Finally, the dissertation rigorously tests the proposed methods against state-of-the-art techniques and reports superior results.

Recommended Citation

Ahanor, Izuwa C., "Generating Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems. " PhD diss., University of Tennessee, 2023.
https://trace.tennessee.edu/utk_graddiss/9158