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

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.