Search

We introduce a new approach for deterministic sensitivity analysis of Markov reward processes, commonly used in cost-effectiveness analyses, via reformulation into a polynomial system. Our approach leverages cylindrical algebraic decomposition (CAD), a technique arising from algebraic geometry that provides an exact description of all solutions to a polynomial system. While it is typically intractable to build a CAD for systems with more than a few variables, we show that a special class of polynomial systems, which includes the polynomials arising from Markov reward processes, can be analyzed much more tractably. We establish several theoretical results about such systems and develop a specialized algorithm to construct their CAD, which allows us to perform exact, multi-way sensitivity analysis for common health economic analyses. We develop an open-source software package that implements our algorithm. Finally, we apply it to two case studies, one with synthetic data and one that re-analyzes a previous cost-effectiveness analysis from the literature, demonstrating advantages of our approach over standard techniques. Our software and code are available at: \url{https://github.com/mmaaz-git/markovag}., Comment: 46 pages

We consider the problem of load balancing in parallel queues by transferring customers between them at discrete points in time. Holding costs accrue as customers wait in the queue, while transfer decisions incur both fixed (setup) and variable costs proportional to the number and direction of transfers. Our work is primarily motivated by inter-facility patient transfers between hospitals during a surge in demand for hospitalization (e.g., during a pandemic). By analyzing an associated fluid control problem, we show that under fairly general assumptions including time-varying arrivals and convex increasing holding costs, the optimal policy in each period partitions the state-space into a well-defined $\textit{no-transfer region}$ and its complement, such that transferring is optimal if and only if the system is sufficiently imbalanced. In the absence of fixed transfer costs, an optimal policy moves the state to the no-transfer region's boundary; in contrast, with fixed costs, the state is moved to the no-transfer region's relative interior. We further leverage the fluid control problem to provide insights on the trade-off between holding and transfer costs, emphasizing the importance of preventing excessive idleness when transfers are not feasible in continuous-time. Using simulation experiments, we investigate the performance and robustness of the fluid policy for the stochastic system. In particular, our case study calibrated using data during the pandemic in the Greater Toronto Area demonstrates that transferring patients between hospitals could result in up to 27.7% reduction in total cost with relatively few transfers.

Adaptive robust optimization problems have received significant attention in recent years, but remain notoriously difficult to solve when recourse decisions are discrete in nature. In this paper, we propose new reformulation techniques for adaptive robust binary optimization (ARBO) problems with objective uncertainty. Without loss of generality, we focus on ARBO problems with "selective adaptability", a term we coin to describe a common class of linking constraints between first-stage and second-stage solutions. Our main contribution revolves around a collection of exact and approximate network flow reformulations for the ARBO problem, which we develop by building upon ideas from the decision diagram literature. Our proposed models can generate feasible solutions, primal bounds and dual bounds, while their size and approximation quality can be precisely controlled through user-specified parameters. Furthermore, and in contrast with existing solution methods, these models are easy to implement and can be solved directly with standard off-the-shelf solvers. Through an extensive set of computational experiments, we show that our models can generate high-quality solutions and dual bounds in significantly less time than popular benchmark methods, often by orders of magnitude.

Inverse optimization has been increasingly used to estimate unknown parameters in an optimization model based on decision data. We show that such a point estimation is insufficient in a prescriptive setting where the estimated parameters are used to prescribe new decisions. The prescribed decisions may be low-quality and misaligned with human intuition and thus are unlikely to be adopted. To tackle this challenge, we propose conformal inverse optimization, which seeks to learn an uncertainty set for the unknown parameters and then solve a robust optimization model to prescribe new decisions. Under mild assumptions, we show that our method enjoys provable guarantees on solution quality, as evaluated using both the ground-truth parameters and the decision maker's perception of the unknown parameters. Our method demonstrates strong empirical performance compared to classic inverse optimization.

For decades, National Football League (NFL) coaches' observed fourth down decisions have been largely inconsistent with prescriptions based on statistical models. In this paper, we develop a framework to explain this discrepancy using an inverse optimization approach. We model the fourth down decision and the subsequent sequence of plays in a game as a Markov decision process (MDP), the dynamics of which we estimate from NFL play-by-play data from the 2014 through 2022 seasons. We assume that coaches' observed decisions are optimal but that the risk preferences governing their decisions are unknown. This yields an inverse decision problem for which the optimality criterion, or risk measure, of the MDP is the estimand. Using the quantile function to parameterize risk, we estimate which quantile-optimal policy yields the coaches' observed decisions as minimally suboptimal. In general, we find that coaches' fourth-down behavior is consistent with optimizing low quantiles of the next-state value distribution, which corresponds to conservative risk preferences. We also find that coaches exhibit higher risk tolerances when making decisions in the opponent's half of the field as opposed to their own half, and that league average fourth down risk tolerances have increased over time., Comment: 22 pages, 12 figures

Cycling stress assessment, which quantifies cyclists' perceived stress imposed by the built environment and motor traffics, increasingly informs cycling infrastructure planning and cycling route recommendation. However, currently calculating cycling stress is slow and data-intensive, which hinders its broader application. In this paper, We propose a deep learning framework to support accurate, fast, and large-scale cycling stress assessments for urban road networks based on street-view images. Our framework features i) a contrastive learning approach that leverages the ordinal relationship among cycling stress labels, and ii) a post-processing technique that enforces spatial smoothness into our predictions. On a dataset of 39,153 road segments collected in Toronto, Canada, our results demonstrate the effectiveness of our deep learning framework and the value of using image data for cycling stress assessment in the absence of high-quality road geometry and motor traffic data.

Measuring soccer shooting skill is a challenging analytics problem due to the scarcity and highly contextual nature of scoring events. The introduction of more advanced data surrounding soccer shots has given rise to model-based metrics which better cope with these challenges. Specifically, metrics such as expected goals added, goals above expectation, and post-shot expected goals all use advanced data to offer an improvement over the classical conversion rate. However, all metrics developed to date assign a value of zero to off-target shots, which account for almost two-thirds of all shots, since these shots have no probability of scoring. We posit that there is non-negligible shooting skill signal contained in the trajectories of off-target shots and propose two shooting skill metrics that incorporate the signal contained in off-target shots. Specifically, we develop a player-specific generative model for shot trajectories based on a mixture of truncated bivariate Gaussian distributions. We use this generative model to compute metrics that allow us to attach non-zero value to off-target shots. We demonstrate that our proposed metrics are more stable than current state-of-the-art metrics and have increased predictive power.

Purpose: To develop a machine learning-based, 3D dose prediction methodology for Gamma Knife (GK) radiosurgery. The methodology accounts for cases involving targets of any number, size, and shape. Methods: Data from 322 GK treatment plans was modified by isolating and cropping the contoured MRI and clinical dose distributions based on tumor location, then scaling the resulting tumor spaces to a standard size. An accompanying 3D tensor was created for each instance to account for tumor size. The modified dataset for 272 patients was used to train both a generative adversarial network (GAN-GK) and a 3D U-Net model (U-Net-GK). Unmodified data was used to train equivalent baseline models. All models were used to predict the dose distribution of 50 out-of-sample patients. Prediction accuracy was evaluated using gamma, with criteria of 4%/2mm, 3%/3mm, 3%/1mm and 1%/1mm. Prediction quality was assessed using coverage, selectivity, and conformity indices. Results: The predictions resulting from GAN-GK and U-Net-GK were similar to their clinical counterparts, with average gamma (4%/2mm) passing rates of 84.9 and 83.1, respectively. In contrast, the gamma passing rate of baseline models were significantly worse than their respective GK-specific models (p < 0.001) at all criterion levels. The quality of GK-specific predictions was also similar to that of clinical plans. Conclusion: Deep learning models can use GK-specific data modification to predict 3D dose distributions for GKRS plans with a large range in size, shape, or number of targets. Standard deep learning models applied to unmodified GK data generated poorer predictions., Comment: Submitted to Physica Medica

Motivated by a cycling infrastructure planning application, we present a machine learning approach to solving bilevel programs with a large number of independent followers, which as a special case includes two-stage stochastic programming. We propose an optimization model that explicitly considers a sampled subset of followers and exploits a machine learning model to estimate the objective values of unsampled followers. Unlike existing approaches, we embed machine learning model training into the optimization problem, which allows us to employ follower features that cannot be represented using leader decisions. We prove bounds on the optimality gap of the generated leader decision as measured by the original objective that considers the full follower set. We develop follower sampling algorithms to tighten the bounds and a representation learning approach to learn follower features, which are used as inputs to our machine learning model. Through numerical studies, we show that our approach generates leader decisions of higher quality compared to baselines. Finally, we perform a real-world case study in Toronto, Canada, where we solve a cycling network design problem with over one million followers. Compared to the current practice, our approach improves a transportation metric by 19.2% and can lead to a potential cost saving of $18M.

This paper presents a landmark study of equity, diversity and inclusion (EDI) in the field of sports analytics. We developed a survey that examined personal and job-related demographics, as well as individual perceptions and experiences about EDI in the workplace. We sent the survey to individuals in the five major North American professional leagues, representatives from the Olympic and Paralympic Committees in Canada and the U.S., the NCAA Division I programs, companies in sports tech/analytics, and university research groups. Our findings indicate the presence of a clear dominant group in sports analytics identifying as: young (72.0%), White (69.5%), heterosexual (89.7%) and male (82.0%). Within professional sports, males in management positions earned roughly 30,000 USD (27%) more on average compared to females. A smaller but equally alarming pay gap of 17,000 USD (14%) was found between White and non-White management personnel. Of concern, females were nearly five times as likely to experience discrimination and twice as likely to have considered leaving their job due to isolation or feeling unwelcome. While they had similar levels of agreement regarding fair processes for rewards and compensation, females "strongly agreed" less often than males regarding equitable support, equitable workload, having a voice, and being taken seriously. Over one third (36.3%) of females indicated that they "strongly agreed" that they must work harder than others to be valued equally, compared to 9.8% of males. We conclude the paper with concrete recommendations that could be considered to create a more equitable, diverse and inclusive environment for individuals working within the sports analytics sector.

We study a control problem for queueing systems where customers may return for additional episodes of service after their initial service completion. At each service completion epoch, the decision maker can choose to reduce the probability of return for the departing customer but at a cost that is convex increasing in the amount of reduction in the return probability. Other costs are incurred as customers wait in the queue and every time they return for service. Our primary motivation comes from post-discharge Quality Improvement (QI) interventions (e.g., follow up phone-calls, appointments) frequently used in a variety of healthcare settings to reduce unplanned hospital readmissions. Our objective is to understand how the cost of interventions should be balanced with the reductions in congestion and service costs. To this end, we consider a fluid approximation of the queueing system and characterize the structure of optimal long-run average and bias-optimal transient control policies for the fluid model. Our structural results motivate the design of intuitive surge protocols whereby different intensities of interventions (corresponding to different levels of reduction in the return probability) are provided based on the congestion in the system. Through extensive simulation experiments, we study the performance of the fluid policy for the stochastic system and identify parameter regimes where it leads to significant cost savings compared to a fixed long-run average optimal policy that ignores holding costs and a simple policy that uses the highest level of intervention whenever the queue is non-empty. In particular, we find that in a parameter regime relevant to our motivating application, dynamically adjusting the intensity of interventions could result in up to 25.4% reduction in long-run average cost and 33.7% in finite-horizon costs compared to the simple aggressive policy.

We establish an open framework for developing plan optimization models for knowledge-based planning (KBP) in radiotherapy. Our framework includes reference plans for 100 patients with head-and-neck cancer and high-quality dose predictions from 19 KBP models that were developed by different research groups during the OpenKBP Grand Challenge. The dose predictions were input to four optimization models to form 76 unique KBP pipelines that generated 7600 plans. The predictions and plans were compared to the reference plans via: dose score, which is the average mean absolute voxel-by-voxel difference in dose a model achieved; the deviation in dose-volume histogram (DVH) criterion; and the frequency of clinical planning criteria satisfaction. We also performed a theoretical investigation to justify our dose mimicking models. The range in rank order correlation of the dose score between predictions and their KBP pipelines was 0.50 to 0.62, which indicates that the quality of the predictions is generally positively correlated with the quality of the plans. Additionally, compared to the input predictions, the KBP-generated plans performed significantly better (P<0.05; one-sided Wilcoxon test) on 18 of 23 DVH criteria. Similarly, each optimization model generated plans that satisfied a higher percentage of criteria than the reference plans. Lastly, our theoretical investigation demonstrated that the dose mimicking models generated plans that are also optimal for a conventional planning model. This was the largest international effort to date for evaluating the combination of KBP prediction and optimization models. In the interest of reproducibility, our data and code is freely available at https://github.com/ababier/open-kbp-opt., Comment: 19 pages, 7 tables, 6 figures

Intensity-modulated radiation therapy (IMRT) allows for the design of customized, highly-conformal treatments for cancer patients. Creating IMRT treatment plans, however, is a mathematically complex process, which is often tackled in multiple, simpler stages. This sequential approach typically separates radiation dose requirements from mechanical deliverability considerations, which may result in suboptimal treatment quality. For patient health to be considered paramount, holistic models must address these plan elements concurrently, eliminating quality loss between stages. This combined direct aperture optimization (DAO) approach is rarely paired with uncertainty mitigation techniques, such as robust optimization, due to the inherent complexity of both parts. This paper outlines a robust DAO (RDAO) model and discusses novel methodologies for efficiently integrating salient constraints. Because the highly-complex RDAO model is difficult to solve, an original candidate plan generation (CPG) heuristic is proposed. The CPG produces rapid, high-quality, feasible plans, which are immediately clinically viable, and can also be used to generate a feasible incumbent solution for warm starting the RDAO model. Computational results obtained using clinical patient datasets with motion uncertainty show the benefit of incorporating the CPG, both in terms of first incumbent solution and final output plan quality., Comment: 27 pages, 14 figures

Value functions are used in sports applications to determine the optimal action players should employ. However, most literature implicitly assumes that the player can perform the prescribed action with known and fixed probability of success. The effect of varying this probability or, equivalently, "execution error" in implementing an action (e.g., hitting a tennis ball to a specific location on the court) on the design of optimal strategies, has received limited attention. In this paper, we develop a novel modeling framework based on Markov reward processes and Markov decision processes to investigate how execution error impacts a player's value function and strategy in tennis. We power our models with hundreds of millions of simulated tennis shots with 3D ball and 2D player tracking data. We find that optimal shot selection strategies in tennis become more conservative as execution error grows, and that having perfect execution with the empirical shot selection strategy is roughly equivalent to choosing one or two optimal shots with average execution error. We find that execution error on backhand shots is more costly than on forehand shots, and that optimal shot selection on a serve return is more valuable than on any other shot, over all values of execution error.

Inverse optimization describes a process that is the "reverse" of traditional mathematical optimization. Unlike traditional optimization, which seeks to compute optimal decisions given an objective and constraints, inverse optimization takes decisions as input and determines an objective and/or constraints that render these decisions approximately or exactly optimal. In recent years, there has been an explosion of interest in the mathematics and applications of inverse optimization. This paper provides a comprehensive review of both the methodological and application-oriented literature in inverse optimization.

Clinical pathways are standardized processes that outline the steps required for managing a specific disease. However, patient pathways often deviate from clinical pathways. Measuring the concordance of patient pathways to clinical pathways is important for health system monitoring and informing quality improvement initiatives. In this paper, we develop an inverse optimization-based approach to measuring pathway concordance in breast cancer, a complex disease. We capture this complexity in a hierarchical network that models the patient's journey through the health system. A novel inverse shortest path model is formulated and solved on this hierarchical network to estimate arc costs, which are used to form a concordance metric to measure the distance between patient pathways and shortest paths (i.e., clinical pathways). Using real breast cancer patient data from Ontario, Canada, we demonstrate that our concordance metric has a statistically significant association with survival for all breast cancer patient subgroups. We also use it to quantify the extent of patient pathway discordances across all subgroups, finding that patients undertaking additional clinical activities constitute the primary driver of discordance in the population., Comment: 24 pages + Appendices

The purpose of this work is to advance fair and consistent comparisons of dose prediction methods for knowledge-based planning (KBP) in radiation therapy research. We hosted OpenKBP, a 2020 AAPM Grand Challenge, and challenged participants to develop the best method for predicting the dose of contoured CT images. The models were evaluated according to two separate scores: (1) dose score, which evaluates the full 3D dose distributions, and (2) dose-volume histogram (DVH) score, which evaluates a set DVH metrics. Participants were given the data of 340 patients who were treated for head-and-neck cancer with radiation therapy. The data was partitioned into training (n=200), validation (n=40), and testing (n=100) datasets. All participants performed training and validation with the corresponding datasets during the validation phase of the Challenge, and we ranked the models in the testing phase based on out-of-sample performance. The Challenge attracted 195 participants from 28 countries, and 73 of those participants formed 44 teams in the validation phase, which received a total of 1750 submissions. The testing phase garnered submissions from 28 teams. On average, over the course of the validation phase, participants improved the dose and DVH scores of their models by a factor of 2.7 and 5.7, respectively. In the testing phase one model achieved significantly better dose and DVH score than the runner-up models. Lastly, many of the top performing teams reported using generalizable techniques (e.g., ensembles) to achieve higher performance than their competition. This is the first competition for knowledge-based planning research, and it helped launch the first platform for comparing KBP prediction methods fairly and consistently. The OpenKBP datasets are available publicly to help benchmark future KBP research, which has also democratized KBP research by making it accessible to everyone., Comment: 26 pages, 6 figures, 5 tables

Inverse optimization, determining parameters of an optimization problem that render a given solution optimal, has received increasing attention in recent years. While significant inverse optimization literature exists for convex optimization problems, there have been few advances for discrete problems, despite the ubiquity of applications that fundamentally rely on discrete decision-making. In this paper, we present a new set of theoretical insights and algorithms for the general class of inverse mixed integer linear optimization problems. Specifically, a general characterization of optimality conditions is established and leveraged to design new cutting plane solution algorithms. Through an extensive set of computational experiments, we show that our methods provide substantial improvements over existing methods in solving the largest and most difficult instances to date.

In this manuscript, we present an argument that machine learning, a subfield of artificial intelligence, can drive improvement in value-based health care through reducing error in clinical decision making. Much of what has been previously published on machine learning in medicine represent single-use or proof-of-concept cases, as well as broad reviews of the advantages and limitations of machine learning. It is timely to look at the broader strategy for artificial intelligence implementation in medicine and emphasize how machine learning can positively influence value-based care.

We determine how prediction methods combine with optimization methods in two-stage knowledge-based planning (KBP) pipelines to produce radiation therapy treatment plans. We trained two dose prediction methods, a generative adversarial network (GAN) and a random forest (RF) with the same 130 treatment plans. The models were applied to 87 out-of-sample patients to create two sets of predicted dose distributions that were used as input to two optimization models. The first optimization model, inverse planning (IP), estimates weights for dose-objectives from a predicted dose distribution and generates new plans using conventional inverse planning. The second optimization model, dose mimicking (DM), minimizes the sum of one-sided quadratic penalties between the predictions and the generated plans using several dose-objectives. Altogether, four KBP pipelines (GAN-IP, GAN-DM, RF-IP, and RF-DM) were constructed and benchmarked against the corresponding clinical plans using clinical criteria; the error of both prediction methods was also evaluated. The best performing plans were GAN-IP plans, which satisfied the same criteria as their corresponding clinical plans (78%) more often than any other KBP pipeline. However, GAN did not necessarily provide the best prediction for the second-stage optimization models. Specifically, both the RF-IP and RF-DM plans satisfied all clinical criteria 25% and 15% more often than GAN-DM plans (the worst performing planning), respectively. GAN predictions also had a higher mean absolute error (3.9 Gy) than those from RF (3.6 Gy). We find that state-of-the-art prediction methods when paired with different optimization algorithms, produce treatment plans with considerable variation in quality.

Out-of-hospital cardiac arrest (OHCA) claims over 400,000 lives each year in North America and is one of the most time-sensitive medical emergencies. Drone-delivered automated external defibrillators (AEDs) have the potential to be a transformative innovation in the provision of emergency care for OHCA. In this paper, we propose a simulation-optimization framework to minimize the total number of drones required to meet a pre-specified response time goal, while guaranteeing a sufficient number of drones are located at each base. To do this, we develop a location-queuing model that is based on the p-median architecture, where each base constitutes an explicit M/M/d queue, and that incorporates estimated baseline response times to the demand points. We then develop a reformulation technique that exploits the baseline response times, allowing us to solve real-world instances to optimality using an off-the-shelf solver. To test our model, we develop a two-stage machine learning approach to simulate both the locations and baseline response times for future OHCAs. We demonstrate the application of our framework using eight years of real data from an area covering 26,000 square kilometres around Toronto, Canada. A modest number of drones are required to significantly reduce response times in all regions. Furthermore, an objective function focused on improving the 90th percentile is well-suited for use in practice because the model reduces the entire response time distribution, while providing equitable coverage in both cities and rural areas. Overall, this paper provides a realistic framework that can be leveraged by healthcare providers seeking to implement a drone network.

Clinical pathways outline standardized processes in the delivery of care for a specific disease. Patient journeys through the healthcare system, though, can deviate substantially from these pathways. Given the positive benefits of clinical pathways, it is important to measure the concordance of patient pathways so that variations in health system performance or bottlenecks in the delivery of care can be detected, monitored, and acted upon. This paper proposes the first data-driven inverse optimization approach to measuring pathway concordance in any problem context. Our specific application considers clinical pathway concordance for stage III colon cancer. We develop a novel concordance metric and demonstrate using real patient data from Ontario, Canada that it has a statistically significant association with survival. Our methodological approach considers a patient's journey as a walk in a directed graph, where the costs on the arcs are derived by solving an inverse shortest path problem. The inverse optimization model uses two sources of information to find the arc costs: reference pathways developed by a provincial cancer agency (primary) and data from real-world patient-related activity from patients with both positive and negative clinical outcomes (secondary). Thus, our inverse optimization framework extends existing models by including data points of both varying "primacy" and "alignment". Data primacy is addressed through a two-stage approach to imputing the cost vector, while data alignment is addressed by a hybrid objective function that aims to minimize and maximize suboptimality error for different subsets of input data., Comment: 61 pages

We develop a knowledge-based automated planning (KBAP) pipeline that generates treatment plans using deep neural network architectures for predicting 3D doses. Our pipeline consisted of a generative adversarial network (GAN) to predict dose from a CT image followed by two optimization models to learn objective function weights and generate fluence-based plans, respectively. We investigated three different GAN models. The first two models predicted dose for each axial slice independently. One predicted dose as a RGB color map, while the other predicted a scalar value for dose directly. The third GAN model predicted scalar doses for the full 3D CT image at once, considering correlations between adjacent CT slices. For all models, we also investigated the impact of scaling the GAN predictions before optimization. Each GAN model was trained on 130 previously delivered oropharyngeal treatment plans. Performance was tested on 87 out-of-sample plans, by evaluating using clinical planning criteria and compared to their corresponding clinical plans. The best performing KBAP plans were generated with the 3D GAN, which predicted dose values followed by scaling. These plans satisfied close to 77% of all clinical criteria, compared to the clinical plans, which satisfied 64% of all criteria. Additionally, these KBAP plans satisfied the same criteria as the clinical plans 84% more frequently compared to the 2D GAN model using RGB dose prediction. The 3D GAN predictions were also more similar to the final plan compared to the other approaches, as it better captured the vertical dosimetric relationship between adjacent axial slices. The deliverable plans better captured implicit constraints associated with physical deliverability. Overall, our final plans had superior performance in satisfying clinical criteria and generated more realistic predictions compared to the previous state-of-the-art., Comment: 15 pages, submitted to Medical Physics

Most inverse optimization models impute unspecified parameters of an objective function to make an observed solution optimal for a given optimization problem with a fixed feasible set. We propose two approaches to impute unspecified left-hand-side constraint coefficients in addition to a cost vector for a given linear optimization problem. The first approach identifies parameters minimizing the duality gap, while the second minimally perturbs prior estimates of the unspecified parameters to satisfy strong duality, if it is possible to satisfy the optimality conditions exactly. We apply these two approaches to the general linear optimization problem. We also use them to impute unspecified parameters of the uncertainty set for robust linear optimization problems under interval and cardinality constrained uncertainty. Each inverse optimization model we propose is nonconvex, but we show that a globally optimal solution can be obtained either in closed form or by solving a linear number of linear or convex optimization problems.

Knowledge-based planning (KBP) is an automated approach to radiation therapy treatment planning that involves predicting desirable treatment plans before they are then corrected to deliverable ones. We propose a generative adversarial network (GAN) approach for predicting desirable 3D dose distributions that eschews the previous paradigms of site-specific feature engineering and predicting low-dimensional representations of the plan. Experiments on a dataset of oropharyngeal cancer patients show that our approach significantly outperforms previous methods on several clinical satisfaction criteria and similarity metrics., Comment: 15 pages. Accepted for publication in PMLR. Presented at Machine Learning for Health Care

The topic of learning to solve optimization problems has received interest from both the operations research and machine learning communities. In this work, we combine techniques from both fields to address the problem of learning to generate decisions to instances of continuous optimization problems where the feasible set varies with contextual features. We propose a novel framework for training a generative model to estimate optimal decisions by combining interior point methods and adversarial learning, which we further embed within an data generation algorithm. Decisions generated by our model satisfy in-sample and out-of-sample optimality guarantees. Finally, we investigate case studies in portfolio optimization and personalized treatment design, demonstrating that our approach yields advantages over predict-then-optimize and supervised deep learning techniques, respectively., Comment: 72 pages

We develop a generalized inverse optimization framework for fitting the cost vector of a single linear optimization problem given multiple observed decisions. This setting is motivated by ensemble learning, where building consensus from base learners can yield better predictions. We unify several models in the inverse optimization literature under a single framework and derive assumption-free and exact solution methods for each one. We extend a goodness-of-fit metric previously introduced for the problem with a single observed decision to this new setting, and demonstrate several important properties. Finally, we demonstrate our framework in a novel inverse optimization-driven procedure for automated radiation therapy treatment planning. Here, the inverse optimization model leverages an ensemble of dose predictions from different machine learning models to construct a consensus treatment plan that outperforms baseline methods. The consensus plan yields better trade-offs between the competing clinical criteria used for plan evaluation.

The lack of emergency medical transportation is viewed as the main barrier to the access of emergency medical care in low and middle-income countries (LMICs). In this paper, we present a robust optimization approach to optimize both the location and routing of emergency response vehicles, accounting for uncertainty in travel times and spatial demand characteristic of LMICs. We traveled to Dhaka, Bangladesh, the sixth largest and third most densely populated city in the world, to conduct field research resulting in the collection of two unique datasets that inform our approach. This data is leveraged to develop machine learning methodologies to estimate demand for emergency medical services in a LMIC setting and to predict the travel time between any two locations in the road network for different times of day and days of the week. We combine our robust optimization and machine learning frameworks with real data to provide an in-depth investigation into three policy-related questions. First, we demonstrate that outpost locations optimized for weekday rush hour lead to good performance for all times of day and days of the week. Second, we find that significant improvements in emergency response times can be achieved by re-locating a small number of outposts and that the performance of the current system could be replicated using only 30% of the resources. Lastly, we show that a fleet of small motorcycle-based ambulances has the potential to significantly outperform traditional ambulance vans. In particular, they are able to capture three times more demand while reducing the median response time by 42% due to increased routing flexibility offered by nimble vehicles on a larger road network. Our results provide practical insights for emergency response optimization that can be leveraged by hospital-based and private ambulance providers in Dhaka and other urban centers in LMICs.

We present a new inverse optimization methodology for multi-objective convex optimization that accommodates an input solution that may not be Pareto optimal and determines a weight vector that produces a Pareto optimal solution that approximates the input solution and preserves the decision maker's intention encoded in it. We introduce a notion of trade-off preservation, which we use as a measure of similarity for approximating the input solution, and show its connection with minimizing an optimality gap. Our inverse model maintains the complexity of the traditional inverse convex models. We propose a linear approximation to the model and a successive linear programming algorithm that balance between trade-off preservation and computational efficiency, and show that our model encompasses many of the existing models from the literature. We demonstrate the proposed method using clinical data from prostate cancer radiation therapy., Comment: 23 pages; 5 figures

In classical inverse linear optimization, one assumes a given solution is a candidate to be optimal. Real data is imperfect and noisy, so there is no guarantee this assumption is satisfied. Inspired by regression, this paper presents a unified framework for cost function estimation in linear optimization comprising a general inverse optimization model and a corresponding goodness-of-fit metric. Although our inverse optimization model is nonconvex, we derive a closed-form solution and present the geometric intuition. Our goodness-of-fit metric, $\rho$, the coefficient of complementarity, has similar properties to $R^2$ from regression and is quasiconvex in the input data, leading to an intuitive geometric interpretation. While $\rho$ is computable in polynomial-time, we derive a lower bound that possesses the same properties, is tight for several important model variations, and is even easier to compute. We demonstrate the application of our framework for model estimation and evaluation in production planning and cancer therapy.

We consider the stability of Robust Optimization problems with respect to perturbations in their uncertainty sets. We focus on Linear Optimization problems, including those with a possibly infinite number of constraints, also known as Linear Semi-Infinite Optimization (LSIO) problems, and consider uncertainty in both the cost function and constraints. We prove Lipschitz continuity of the optimal value and {\epsilon}-approximate optimal solution set with respect to the Hausdorff distance between uncertainty sets and with an explicit Lipschitz constant that can be calculated. In addition, we prove closedness and upper semi-continuity for the optimal solution set mapping with respect to the uncertainty set., Comment: 37 pages

Sudden cardiac arrest is a significant public health concern. Successful treatment of cardiac arrest is extremely time sensitive, and use of an automated external defibrillator (AED) where possible significantly increases the probability of survival. Placement of AEDs in public locations can improve survival by enabling bystanders to treat victims of cardiac arrest prior to the arrival of emergency medical responders. However, since the exact locations of future cardiac arrests cannot be known a priori, AEDs must be placed strategically in public locations to ensure their accessibility in the event of an out-of-hospital cardiac arrest emergency. In this paper, we propose a data-driven optimization model for deploying AEDs in public spaces while accounting for uncertainty in future cardiac arrest locations. Our approach involves discretizing a continuous service area into a large set of scenarios, where the probability of cardiac arrest at each location is itself uncertain. We model uncertainty in the spatial risk of cardiac arrest using a polyhedral uncertainty set that we calibrate using historical cardiac arrest data. We propose a solution technique based on row-and-column generation that exploits the structure of the uncertainty set, allowing the algorithm to scale gracefully with the total number of scenarios. Using real cardiac arrest data from the City of Toronto, we conduct an extensive numerical study on AED deployment public locations. We find that hedging against cardiac arrest location uncertainty can produce AED deployments that outperform a intuitive sample average approximation by 9 to 15%, and cuts the performance gap with respect to an ex-post model by half. Our findings suggest that accounting for cardiac arrest location uncertainty can lead to improved accessibility of AEDs during cardiac arrest emergencies and the potential for improved survival outcomes., Comment: 55 pages