Andrew C. Trapp

Izuwa Ahanor, Hugh Medal, Andrew C. Trapp

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.

Narges Ahani, Andrew C. Trapp

Decision support tools enable improved decision-making for challenging decision problems by empowering stakeholders to process, analyze, visualize, and otherwise make sense of a variety of key factors. Their intentional design is a critical component of the value they create. All decision-support tools share in common that there is a complex decision problem to be solved for which decision-support is useful, and moreover, that appropriate analytics expertise is available to produce solutions to the problem setting at hand. When well-designed, decision support tools reduce friction and increase efficiency in providing support for the decision-making process, thereby improving the ability of decision-makers to make quality decisions. On the other hand, the presence of overwhelming, superfluous, insufficient, or ill-fitting information and software features can have an adverse effect on the decision-making process and, consequently, outcomes. We advocate for an innovative, and perhaps overlooked, approach to designing effective decision support tools: genuinely listening to the project stakeholders, to ascertain and appreciate their real needs and perspectives. By prioritizing stakeholder needs, a foundation of mutual trust and understanding is established with the design team. We maintain this trust is critical to eventual tool acceptance and adoption, and its absence jeopardizes the future use of the tool, which would leave its analytical insights for naught. We discuss examples across multiple contexts to underscore our collective experience, highlight lessons learned, and present recommended practices to improve the design and eventual adoption of decision dupport tools.

Patrick Flaherty, Pitchaya Wiratchotisatian, Ji Ah Lee et al.

We present a global optimization approach for solving the maximum a-posteriori (MAP) clustering problem under the Gaussian mixture model.Our approach can accommodate side constraints and it preserves the combinatorial structure of the MAP clustering problem by formulating it asa mixed-integer nonlinear optimization problem (MINLP). We approximate the MINLP through a mixed-integer quadratic program (MIQP) transformation that improves computational aspects while guaranteeing $ε$-global optimality. An important benefit of our approach is the explicit quantification of the degree of suboptimality, via the optimality gap, en route to finding the globally optimal MAP clustering. Numerical experiments comparing our method to other approaches show that our method finds a better solution than standard clustering methods. Finally, we cluster a real breast cancer gene expression data set incorporating intrinsic subtype information; the induced constraints substantially improve the computational performance and produce more coherent and bio-logically meaningful clusters.

Hachem Saddiki, Andrew C. Trapp, Patrick Flaherty

Variational inference methods for latent variable statistical models have gained popularity because they are relatively fast, can handle large data sets, and have deterministic convergence guarantees. However, in practice it is unclear whether the fixed point identified by the variational inference algorithm is a local or a global optimum. Here, we propose a method for constructing iterative optimization algorithms for variational inference problems that are guaranteed to converge to the $ε$-global variational lower bound on the log-likelihood. We derive inference algorithms for two variational approximations to a standard Bayesian Gaussian mixture model (BGMM). We present a minimal data set for empirically testing convergence and show that a variational inference algorithm frequently converges to a local optimum while our algorithm always converges to the globally optimal variational lower bound. We characterize the loss incurred by choosing a non-optimal variational approximation distribution suggesting that selection of the approximating variational distribution deserves as much attention as the selection of the original statistical model for a given data set.