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

While most methods for solving mixed-integer optimization problems compute a single optimal solution, a diverse set of near-optimal solutions can often be more useful. 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 investigate parameterized node selection … Read more

A Reformulation Technique to Solve Polynomial Optimization Problems with Separable Objective Functions of Bounded Integer Variables

Real-world problems are often nonconvex and involve integer variables, representing vexing challenges to be tackled using state-of-the-art solvers. We introduce a mathematical identity-based reformulation of a class of polynomial integer nonlinear optimization (PINLO) problems using a technique that linearizes polynomial functions of separable and bounded integer variables of any degree. We also introduce an alternative … Read more

A Comparative Study of Stability Representations for Solving Many-to-One Matching Problems with Utility-Weighted Objectives, Ties, and Incomplete Lists via Integer Optimization

We consider integer optimization models for finding stable solutions to many-to-one, utility-weighted matching problems with incomplete preference lists and ties. While traditional algorithmic approaches for the stable many-to-one matching problem, such as the Deferred Acceptance algorithm, offer efficient performance for the strict problem setting, adaptation to alternative settings often requires careful customization. Optimization-based approaches are … Read more

Select, Route and Schedule: Optimizing Community Paramedicine Service Delivery with Mandatory Visits and Patient Prioritization

Many patients receive reactive care in the United States healthcare system, including those who frequent emergency rooms and who are recently discharged from a hospital. Community paramedicine is a recent healthcare innovation that enables proactive visitation of patients at home, often shortly after emergency department and hospital discharge. We propose an optimization framework for managing … Read more

Aid Allocation for Camp-Based and Urban Refugees with Uncertain Demand and Replenishments

There are nearly 26 million refugees worldwide seeking safety from persecution, violence, conflict, and human rights violations. Camp-based refugees are those that seek shelter in refugee camps, whereas urban refugees inhabit nearby, surrounding populations. The systems that supply aid to refugee camps may suffer from ineffective distribution due to challenges in administration, demand uncertainty and … Read more

Enriching Solutions to Combinatorial Problems via Solution Engineering

Existing approaches to identify multiple solutions to combinatorial problems in practice are at best limited in their ability to simultaneously incorporate both diversity among generated solutions, as well as problem-specific desires that are apriori unknown, or at least difficult to articulate, for the end-user. We propose a general framework that can generate a set of … Read more

Finding Diverse Solutions of High Quality to Binary Integer Programs

Typical output from an optimization solver is a single optimal solution. At the same time, a set of high-quality and diverse solutions could be beneficial in a variety of contexts, for example problems involving imperfect information, or those for which the structure of high-quality solution vectors can reveal meaningful insights. In view of this, we … Read more