- Randomized Robust Price Optimization.
Guan, X., and Mišić, V. V. (2023)
Major revision in Management Science.
[Abstract] [SSRN]
Abstract:
The robust multi-product pricing problem is to determine the prices of a collection of products so as to maximize the worst-case revenue, where the worst case is taken over an uncertainty set of demand models that the firm expects could be realized in practice. A tacit assumption in this approach is that the pricing decision is a deterministic decision: the prices of the products are fixed and do not vary. In this paper, we consider a randomized approach to robust pricing, where a decision maker specifies a distribution over potential price vectors so as to maximize its worst-case revenue over an uncertainty set of demand models. We formally define this problem -- the randomized robust price optimization problem -- and analyze when a randomized price scheme performs as well as a deterministic price vector, and identify cases in which it can yield a benefit. We also propose two solution methods for obtaining an optimal randomization scheme over a discrete set of candidate price vectors based on constraint generation and double column generation, respectively, and show how these methods are applicable for common demand models, such as the linear, semi-log and log-log demand models. We numerically compare the randomized approach against the deterministic approach on a variety of synthetic and real problem instances; on synthetic instances, we show that the improvement in worst-case revenue can be as much as 1300%, while on real data instances derived from a grocery retail scanner dataset, the improvement can be as high as 92%.
- Randomized Policy Optimization for Optimal Stopping.
Guan, X., and Mišić, V. V. (2022)
Revise and resubmit in Management Science.
[Abstract] [SSRN]
- Finalist, INFORMS Finance Section Best Student Paper Competition (2023) (to student co-author X. Guan)
Abstract:
Optimal stopping is the problem of determining when to stop a stochastic system in order to maximize reward, which is of practical importance in domains such as finance, operations management and healthcare. Existing methods for high-dimensional optimal stopping that are popular in practice produce deterministic linear policies -- policies that deterministically stop based on the sign of a weighted sum of basis functions -- but are not guaranteed to find the optimal policy within this policy class given a fixed basis function architecture. In this paper, we propose a new methodology for optimal stopping based on randomized linear policies, which choose to stop with a probability that is determined by a weighted sum of basis functions. We motivate these policies by establishing that under mild conditions, given a fixed basis function architecture, optimizing over randomized linear policies is equivalent to optimizing over deterministic linear policies. We formulate the problem of learning randomized linear policies from data as a smooth non-convex sample average approximation (SAA) problem. We theoretically prove the almost sure convergence of our randomized policy SAA problem and establish bounds on the out-of-sample performance of randomized policies obtained from our SAA problem based on Rademacher complexity. We also show that the SAA problem is in general NP-Hard, and consequently develop a practical heuristic for solving our randomized policy problem. Through numerical experiments on a benchmark family of option pricing problem instances, we show that our approach can substantially outperform state-of-the-art methods.
- Exact Logit-Based Product Design.
Akçakuş, İ., and Mišić, V. V. (2021)
Major revision in Management Science.
[Abstract] [SSRN]
Abstract:
The share-of-choice product design (SOCPD) problem is to find the product, as defined by its attributes, that maximizes market share arising from a collection of customer types or segments. When customers follow a logit model of choice, the market share is given by a weighted sum of logistic probabilities, leading to the logit-based share-of-choice product design problem. In this paper, we develop a methodology for solving this problem to provable optimality. We first analyze the complexity of this problem, and show that this problem is theoretically intractable: it is NP-Hard to solve exactly, even when there are only two customer types, and it is furthermore NP-Hard to approximate to within a non-trivial factor. Motivated by the difficulty of this problem, we propose three different mixed-integer exponential cone programs of increasing strength for solving the problem exactly, which allow us to leverage modern integer conic program solvers such as Mosek. Using both synthetic problem instances and instances derived from real conjoint data sets, we show that our methodology can solve large instances to provable optimality or near optimality in operationally feasible time frames and yields solutions that generally achieve higher market share than previously proposed heuristics.
- Assortment Optimization under the Decision Forest Model.
Akchen, Y.-C., and Mišić, V. V. (2021)
Major revision in Manufacturing & Service Operations Management.
[Abstract] [SSRN]
Abstract:
Problem definition: We study the problem of finding the optimal assortment that maximizes expected revenue under the decision forest model, a recently proposed nonparametric choice model that is capable of representing any discrete choice model and in particular, can be used to represent non-rational customer behavior.
This problem is of practical importance because it allows a firm to tailor its product offerings to profitably exploit deviations from rational customer behavior, but at the same time is challenging due to the extremely general nature of the decision forest model.
Methodology/Results: We approach this problem from a mixed-integer optimization perspective and propose two different formulations. We theoretically compare the two formulations in strength, and analyze when they are integral in the special case of a single tree. We further propose a methodology for solving the two formulations at a large-scale based on Benders decomposition, and show that the Benders subproblem can be solved efficiently by primal-dual greedy algorithms when the master solution is fractional for one of the formulations, and in closed form when the master solution is binary for both formulations. Using synthetically generated instances, we demonstrate the practical tractability of our formulations and our Benders decomposition approach, and their edge over heuristic approaches.
Managerial implications: In a case study based on a real-world transaction data, we demonstrate that our proposed approach can factor the behavioral anomalies observed in consumer choice into assortment decision and create higher revenue.
- Automated Scheduling of Doppler Exoplanet Observations at Keck Observatory.
Handley, L. B., Petigura, E. A., Mišić, V. V., Lubin, J., and Isaacson, H. (2024)
The Astronomical Journal, 167 (3): 122.
[Abstract] [DOI] [PDF]
Abstract:
Precise Doppler studies of extrasolar planets require fine-grained control of observational cadence, i.e., the timing of and spacing between observations. We present a novel framework for scheduling a set of Doppler campaigns with different cadence requirements at the W. M. Keck Observatory. For a set of observing programs and allocated nights on an instrument, our software optimizes the timing and ordering of ~1000 observations within a given observing semester. We achieve a near-optimal solution in real-time using a hierarchical Integer Linear Programming framework. Our scheduling formulation optimizes over the roughly 103000 possible orderings. A top level optimization finds the most regular sequence of allocated nights by which to observe each host star in the request catalog based on a frequency specified in the request. A second optimization scheme minimizes the slews and downtime of the instrument. We have assessed our algorithms performance with simulated data and with the real suite of Doppler observations of the California Planet Search in 2023.
- Solving the Traveling Telescope Problem with Mixed Integer Linear Programming.
Handley, L. B., Petigura, E. A., and Mišić, V. V. (2024)
The Astronomical Journal, 167 (1): 133.
[Abstract] [DOI] [PDF]
Abstract:
The size and complexity of modern astronomical surveys has grown to the point where, in many cases, traditional human scheduling of observations is tedious at best and impractical at worst. Automated scheduling algorithms present an opportunity to save human effort and increase scientific productivity. A common scheduling challenge involves determining the optimal ordering of a set of targets over a night subject to timing constraints and time-dependent slew overheads. We present a solution to the `Traveling Telescope Problem' (TTP) that uses Mixed-Integer Linear Programming (MILP). This algorithm is fast enough to enable dynamic schedule generation in many astronomical contexts. It can determine the optimal solution for 100 observations within 10 minutes on a modern workstation, reducing slew overheads by a factor of 5 compared to random ordering. We also provide a heuristic method that can return a near-optimal solution at significantly reduced computational cost. As a case study, we explore our algorithm's suitability to automatic schedule generation for Doppler planet searches.
- Column-Randomized Linear Programs: Performance Guarantees and Applications.
Akchen, Y.-C., and Mišić, V. V. (2023)
Forthcoming in Operations Research.
[Abstract] [SSRN] [DOI]
Abstract:
We propose a randomized method for solving linear programs with a large number of columns but a relatively small number of constraints. Since enumerating all the columns is usually unrealistic, such linear programs are commonly solved by column generation, which is often still computationally challenging due to the intractability of the subproblem in many applications. Instead of iteratively introducing one column at a time as in column generation, our proposed method involves sampling a collection of columns according to a user-specified randomization scheme and solving the linear program consisting of the sampled columns. While similar methods for solving large-scale linear programs by sampling columns (or, equivalently, sampling constraints in the dual) have been proposed in the literature, in this paper we derive an upper bound on the optimality gap that holds with high probability and converges with rate \(1 / \sqrt{K}\), where \(K\) is the number of sampled columns, to the value of a linear program related to the sampling distribution. To the best of our knowledge, this is the first paper addressing the convergence of the optimality gap for sampling columns/constraints in generic linear programs without additional assumptions on the problem structure and sampling distribution. We further apply the proposed method to various applications, such as linear programs with totally unimodular constraints, Markov decision processes, covering problems and packing problems, and derive problem-specific performance guarantees. We also generalize the method to the case that the sampled columns may not be statistically independent. Finally, we numerically demonstrate the effectiveness of the proposed method in the cutting-stock problem and in nonparametric choice model estimation.
- Decision Forest: A Nonparametric Approach to Modeling Irrational Choice.
Chen, Y.-C., and Mišić, V. V. (2022)
Management Science, 68 (10): 7090-7111.
[Abstract] [SSRN] [DOI] [Code]
- Honorable Mention, INFORMS George E. Nicholson Student Paper Competition (2020) (awarded to student co-author Y.-C. Chen)
- First Place, INFORMS Decision Analysis Society Best Student Paper Award (2019) (awarded to student co-author Y.-C. Chen)
- Second Place, INFORMS Revenue Management and Pricing (RMP) Section Best Student Paper Award (2019) (awarded to student co-author Y.-C. Chen)
- Finalist, INFORMS Service Science Section Best Paper Award (2019)
- Spotlight presentation (16 out of 80+ submissions) at INFORMS Revenue Management & Pricing (RMP) Conference 2019, Stanford, CA.
- Management Science Review Blog Post: Modeling Irrational Decisions
Abstract:
Customer behavior is often assumed to follow weak rationality, which implies that adding a product to an assortment will not increase the choice probability of another product in that assortment. However, an increasing amount of research has revealed that customers are not necessarily rational when making decisions. In this paper, we study a new nonparametric choice model that relaxes this assumption and can model a wider range of customer behavior, such as decoy effects between products. In this model, each customer type is associated with a binary decision tree, which represents a decision process for making a purchase based on checking for the existence of specific products in the assortment. Together with a probability distribution over customer types, we show that the resulting model -- a decision forest -- is able to represent any customer choice model, including models that are inconsistent with weak rationality. We theoretically characterize the depth of the forest needed to fit a data set of historical assortments and prove that asymptotically, a forest whose depth scales logarithmically in the number of assortments is sufficient to fit most data sets. We also propose an efficient algorithm for estimating such models from data, based on combining randomization and optimization. Using synthetic data and real transaction data exhibiting non-rational behavior, we show that the model outperforms the multinomial logit and ranking-based models in out-of-sample predictive ability.
- A Simulation-Based Evaluation of Machine Learning Models for Clinical Decision Support: Application and Analysis Using Hospital Readmission.
Mišić, V. V., Rajaram, K. and Gabel, E. (2021)
npj (Nature) Digital Medicine, 4 (98): 1-11.
[Abstract] [DOI] [PDF]
Abstract:
The interest in applying machine learning in healthcare has grown rapidly in recent years. Most predictive algorithms requiring pathway implementations are evaluated using metrics focused on predictive performance, such as the c statistic. However, these metrics are of limited clinical value, for two reasons: (1) they do not account for the algorithm’s role within a provider workflow; and (2) they do not quantify the algorithm’s value in terms of patient outcomes and cost savings. We propose a framework for simulating the selection of patients over time by a clinician using a machine learning algorithm, and quantifying the expected patient outcomes and cost savings. Using data on unplanned emergency department surgical readmissions, we show that factors such as the provider's schedule and postoperative prediction timing can have major effects on the pathway cohort size and potential cost reductions from preventing hospital readmissions.
-
Interpretable Optimal Stopping.
Ciocan, D. F., and Mišić, V. V. (2022)
Management Science, 68 (3): 1616-1638.
[Abstract] [DOI] [SSRN]
Abstract:
Optimal stopping is the problem of deciding when to stop a stochastic system to obtain the greatest reward, arising in numerous application areas such as finance, healthcare and marketing. State-of-the-art methods for high-dimensional optimal stopping involve approximating the value function or the continuation value, and then using that approximation within a greedy policy. Although such policies can perform very well, they are generally not guaranteed to be interpretable; that is, a decision maker may not be able to easily see the link between the current system state and the policy’s action. In this paper, we propose a new approach to optimal stopping, wherein the policy is represented as a binary tree, in the spirit of naturally interpretable tree models commonly used in machine learning. We formulate the problem of learning such policies from observed trajectories of the stochastic system as a sample average approximation (SAA) problem. We prove that the SAA problem converges under mild conditions as the sample size increases, but that computationally even immediate simplifications of the SAA problem are theoretically intractable. We thus propose a tractable heuristic for approximately solving the SAA problem, by greedily constructing the tree from the top down. We demonstrate the value of our approach by applying it to the canonical problem of option pricing, using both synthetic instances and instances calibrated with real S&P500 data. Our method obtains policies that (1) outperform state-of-the-art non-interpretable methods, based on simulation-regression and martingale duality, and (2) possess a remarkably simple and intuitive structure.
- Machine Learning Prediction of Post-Operative Emergency Department Hospital Readmission.
Mišić, V. V., Gabel, E., Hofer, I., Rajaram, R., and Mahajan, A. (2020)
Anesthesiology, 132 (5): 968-980.
[Abstract] [DOI] [PDF]
Abstract:
Background: Although prediction of hospital readmissions has been studied in medical patients, it has received relatively little attention in surgical patient populations. Published predictors require information only available at the moment of discharge. The authors hypothesized that machine learning approaches can be leveraged to accurately predict readmissions in postoperative patients from the emergency department. Further, the authors hypothesize that these approaches can accurately predict the risk of readmission much sooner than hospital discharge.
Methods: Using a cohort of surgical patients at a tertiary care academic medical center, surgical, demographic, lab, medication, care team, and current procedural terminology data were extracted from the electronic health record. The primary outcome was whether there existed a future hospital readmission originating from the emergency department within 30 days of surgery. Secondarily, the time interval from surgery to the prediction was analyzed at 0, 12, 24, 36, 48, and 60 h. Different machine learning models for predicting the primary outcome were evaluated with respect to the area under the receiver-operator characteristic curve metric using different permutations of the available features.
Results: Surgical hospital admissions (N = 34,532) from April 2013 to December 2016 were included in the analysis. Surgical and demographic features led to moderate discrimination for prediction after discharge (area under the curve: 0.74 to 0.76), whereas medication, consulting team, and current procedural terminology features did not improve the discrimination. Lab features improved discrimination, with gradient-boosted trees attaining the best performance (area under the curve: 0.866, SD 0.006). This performance was sustained during temporal validation with 2017 to 2018 data (area under the curve: 0.85 to 0.88). Lastly, the discrimination of the predictions calculated 36 h after surgery (area under the curve: 0.88 to 0.89) nearly matched those from time of discharge.
Conclusions: A machine learning approach to predicting postoperative readmission can produce hospital-specific models for accurately predicting 30-day readmissions via the emergency department. Moreover, these predictions can be confidently calculated at 36 h after surgery without consideration of discharge-level data.
- Optimization of Tree Ensembles.
Mišić, V. V. (2020)
Operations Research, 68 (5): 1605-1624.
[Abstract] [DOI] [Arxiv]
- Second Place, INFORMS Junior Faculty Interest Group (JFIG) Paper Competition (2017)
Abstract:
Tree ensemble models such as random forests and boosted trees are among the most widely used and practically successful predictive models in applied machine learning and business analytics. Although such models have been used to make predictions based on exogenous, uncontrollable independent variables, they are increasingly being used to make predictions where the independent variables are controllable and are also decision variables. In this paper, we study the problem of tree ensemble optimization: given a tree ensemble that predicts some dependent variable using controllable independent variables, how should we set these variables so as to maximize the predicted value? We formulate the problem as a mixed-integer optimization problem. We theoretically examine the strength of our formulation, provide a hierarchy of approximate formulations with bounds on approximation quality and exploit the structure of the problem to develop two large-scale solution methods, one based on Benders decomposition and one based on iteratively generating tree split constraints. We test our methodology on real data sets, including two case studies in drug design and customized pricing, and show that our methodology can efficiently solve large-scale instances to near or full optimality, and outperforms solutions obtained by heuristic approaches. In our drug design case, we show how our approach can identify compounds that efficiently trade-off predicted performance and novelty with respect to existing, known compounds. In our customized pricing case, we show how our approach can efficiently determine optimal store-level prices under a random forest model that delivers excellent predictive accuracy.
-
Data Analytics in Operations Management: A Review.
Mišić, V. V. and Perakis, G. (2020)
Manufacturing & Services Operations Management, 22 (1): 158-169.
[Abstract] [DOI] [SSRN]
Abstract:
Research in operations management has traditionally focused on models for understanding, mostly at a strategic level, how firms should operate. Spurred by the growing availability of data and recent advances in machine learning and optimization methodologies, there has been an increasing application of data analytics to problems in operations management. In this paper, we review recent applications of data analytics to operations management, in three major areas -- supply chain management, revenue management and healthcare operations -- and highlight some exciting directions for the future.
-
Exact First-Choice Product Line Optimization.
Bertsimas, D., and Mišić, V. V. (2019)
Operations Research, 67 (3): 651-670.
[Abstract] [DOI] [SSRN] [Code]
- An earlier version of this work was titled "Data-driven assortment optimization".
Abstract:
A fundamental problem faced by firms is that of product line design: given a set of candidate products that may be offered to a collection of customers, what subset of those products should be offered so as to maximize the profit that is realized when customers make purchases according to their preferences? In this paper, we consider the product line design problem when customers choose according to a first-choice rule and present a new mixed-integer optimization formulation of the problem. We theoretically analyze the strength of our formulation and show that it is stronger than alternative formulations that have been proposed in the literature, thus contributing to a unified understanding of the different formulations for this problem. We also present a novel solution approach for solving our formulation at scale, based on Benders decomposition, which exploits the surprising fact that Benders cuts for both the relaxation and the integer problem can be generated in a computationally efficient manner. We demonstrate the value of our formulation and Benders decomposition approach through two sets of experiments. In the first, we use synthetic instances to show that our formulation is computationally tractable and can be solved an order of magnitude faster for small to medium scale instances than the alternate, previously proposed formulations. In the second, we consider a previously studied product line design instance based on a real conjoint data set, involving over 3000 candidate products and over 300 respondents. We show that this problem, which required a week of computation time to solve in prior work, is solved by our approach to full optimality in approximately ten minutes.
- The Airlift Planning Problem.
Bertsimas, D., Chang, A. A., Mišić, V. V., and Mundru, N. (2019)
Transportation Science, 53 (3): 773-795.
[Abstract] [DOI] [PDF]
Abstract:
The United States Transportation Command (USTRANSCOM) is responsible for planning and executing the transportation of United States military personnel and cargo by air, land and sea. The airlift planning problem faced by the air component of USTRANSCOM is to decide how requirements (passengers and cargo) will be assigned to the available aircraft fleet and the sequence of pickups and dropoffs that each aircraft will perform in order to ensure that the requirements are delivered with minimal delay and with maximum utilization of the available aircraft. This problem is of significant interest to USTRANSCOM due to the highly time-sensitive nature of the requirements that are typically designated for delivery by airlift, as well as the very high cost of airlift operations. At the same time, the airlift planning problem is extremely difficult to solve due to the combinatorial nature of the problem and the numerous constraints present in the problem (such as weight restrictions and crew rest requirements). In this paper, we propose an approach for solving the airlift planning problem faced by USTRANSCOM based on modern, large-scale optimization. Our approach relies on solving a large-scale mixed-integer programming model that disentangles the assignment decision (which aircraft will pickup and deliver which requirement) from the sequencing decision (in what order the aircraft will pickup and deliver its assigned requirements), using a combination of heuristics and column generation. Through computational experiments with both a simulated data set and a planning data set provided by USTRANSCOM, we show that our approach leads to high-quality solutions for realistic instances (e.g., 100 aircraft and 100 requirements) within operationally feasible time frames. Compared to a baseline approach that emulates current practice at USTRANSCOM, our approach leads to reductions in total delay and aircraft time of 8 to 12% in simulated data instances and 16 to 40% in USTRANSCOM's planning instances.
- A Comparison of Monte Carlo Tree Search and Rolling Horizon Optimization for Large Scale Dynamic Resource Allocation Problems.
Bertsimas, D., Griffith, J. D., Gupta, V., Kochenderfer, M. and Mišić, V. V. (2017)
European Journal of Operational Research, 263 (2): 664-678.
[Abstract] [DOI] [PDF] [Supplement]
Abstract:
Dynamic resource allocation (DRA) problems constitute an important class of dynamic stochastic optimization problems that arise in a variety of important real-world applications. DRA problems are notoriously difficult to solve to optimality since they frequently combine stochastic elements with intractably large state and action spaces. Although the artificial intelligence and operations research communities have independently proposed two successful frameworks for solving dynamic stochastic optimization problems---Monte Carlo tree search (MCTS) and rolling horizon optimization (RHO), respectively---the relative merits of these two approaches are not well understood. In this paper, we adapt both MCTS and RHO to two problems -- a problem inspired by tactical wildfire management and a classical problem involving the control of queueing networks -- and undertake an extensive computational study comparing the two methods on large scale instances of both problems in terms of both the state and the action spaces. We show that both methods are able to greatly improve on a baseline, problem-specific heuristic. On smaller instances, the MCTS and RHO approaches perform comparably, but the RHO approach outperforms MCTS as the size of the problem increases for a fixed computational budget.
- Robust Product Line Design.
Bertsimas, D., and Mišić, V. V. (2017)
Operations Research, 65 (1): 19 - 37
[Abstract]
[DOI]
[PDF]
Abstract:
The majority of approaches to product line design that have been proposed by marketing scientists assume that the underlying choice model that describes how the customer population will respond to a new product line is known precisely. In reality, however, marketers do not precisely know how the customer population will respond and can only obtain an estimate of the choice model from limited conjoint data. In this paper, we propose a new type of optimization approach for product line design under uncertainty. Our approach is based on the paradigm of robust optimization where, rather than optimizing the expected revenue with respect to a single model, one optimizes the worst-case expected revenue with respect to an uncertainty set of models. This framework allows us to account for both parameter uncertainty, when we may be confident about the type of model structure but not about the values of the parameters, and structural uncertainty, when we may not even be confident about the right model structure to use to describe the customer population. Through computational experiments with a real conjoint data set, we demonstrate the benefits of our approach in addressing parameter and structural uncertainty. With regard to parameter uncertainty, we show that product lines designed without accounting for parameter uncertainty are fragile and can experience worst-case revenue losses as high as 23%, and that the robust product line can significantly outperform the nominal product line in the worst-case, with relative improvements of up to 14%. With regard to structural uncertainty, we similarly show that product lines that are designed for a single model structure can be highly suboptimal under other structures (worst-case losses of up to 37%), while a product line that optimizes against the worst of a set of structurally distinct models can outperform single-model product lines by as much as 55% in the worst-case and can guarantee good aggregate performance over structurally distinct models.
- Decomposable Markov Decision Processes: A Fluid Optimization Approach.
Bertsimas, D., and Mišić, V. V. (2016)
Operations Research, 64 (6): 1537 - 1555
[Abstract]
[DOI]
[PDF]
[e-companion]
Abstract:
Decomposable Markov decision processes (MDPs) are problems where the stochastic system can be decomposed into multiple individual components. Although such MDPs arise naturally in many practical applications, they are often difficult to solve exactly due to the enormous size of the state space of the complete system, which grows exponentially with the number of components. In this paper, we propose an approximate solution approach to decomposable MDPs that is based on re-solving a fluid linear optimization formulation of the problem at each decision epoch. This formulation tractably approximates the problem by modeling transition behavior at the level of the individual components rather than the complete system. We prove that our fluid formulation provides a tighter bound on the optimal value function than three state-of-the-art formulations: the approximate linear optimization formulation, the classical Lagrangian relaxation formulation and a novel, alternate Lagrangian relaxation that is based on relaxing an action consistency constraint. We provide a numerical demonstration of the effectiveness of the approach in the area of multiarmed bandit problems, where we show that our approach provides near optimal performance and outperforms state-of-the-art algorithms.
- The Perils of Adapting to Dose Errors in Radiation Therapy.
Mišić, V. V., and Chan, T. C. Y. (2015)
PLoS ONE, 10 (5), e0125335.
[Abstract]
[DOI]
[PDF]
- An earlier version of this work was titled "Dose-reactive methods in adaptive robust radiation therapy for lung cancer".
Abstract:
We consider adaptive robust methods for lung cancer that are also dose-reactive, wherein the treatment is modified after each treatment session to account for the dose delivered in prior treatment sessions. Such methods are of interest because they potentially allow for errors in the delivered dose to be corrected as the treatment progresses, thereby ensuring that the tumor receives a sufficient dose at the end of the treatment. We show through a computational study with real lung cancer patient data that while dose reaction is beneficial with respect to the final dose distribution, it may lead to exaggerated daily underdose and overdose relative to non-reactive methods that grows as the treatment progresses. However, by combining dose reaction with a mechanism for updating an estimate of the uncertainty, the magnitude of this growth can be mitigated substantially. The key finding of this paper is that reacting to dose errors -- an adaptation strategy that is both simple and intuitively appealing -- may backfire and lead to treatments that are clinically unacceptable.
- Adaptive and Robust Radiation Therapy Optimization for Lung Cancer.
Chan, T. C. Y., and Mišić, V. V. (2013)
European Journal of Operational Research, 231 (3) 745-756.
[Abstract] [PDF] [Supplement]
- Honorable mention, Canadian Operational Research Society (CORS) 2012 Student Paper Competition, Open Category
Abstract:
A previous approach to robust intensity-modulated radiation therapy (IMRT) treatment planning for moving tumors in the lung involves solving a single planning problem before the start of treatment and using the resulting solution in all of the subsequent treatment sessions. In this paper, we develop an adaptive robust optimization approach to IMRT treatment planning for lung cancer, where information gathered in prior treatment sessions is used to update the uncertainty set and guide the reoptimization of the treatment for the next session. Such an approach allows for the estimate of the uncertain effect to improve as the treatment goes on. Our method is computationally tractable, as it involves solving a sequence of linear optimization problems. We present computational results for a lung cancer patient case and show that using our adaptive robust method, it is possible to attain a significant improvement over the traditional robust approach in both tumor coverage and organ sparing simultaneously. We also prove that under certain conditions our adaptive robust method is asymptotically optimal, which provides insight into the performance observed in our computational study. The essence of our method -- solving a sequence of single-stage robust optimization problems, with the uncertainty set updated each time -- can potentially be applied to other problems that involve multi-stage decisions to be made under uncertainty.
- Computational Enhancements to Fluence Map Optimization for Total Marrow Irradiation Using IMRT.
Aleman, D. M., Mišić, V. V., and Sharpe, M. B. (2013)
Computers & Operations Research, 40 (9) 2167-2177.
[Abstract] [PDF]
Abstract:
The fluence map optimization (FMO) problem is a core problem in intensity modulated radiation therapy (IMRT) treatment planning. Although it has been studied extensively for site-specific treatment planning, few studies have examined efficient computational methods for solving it for intensity modulated total marrow irradiation (IM-TMI) planning; few studies have also looked at exploiting prior beamlet information to solve the FMO problem in a beam orientation optimization context. In this study, we consider different types of line search strategies and different types of warm-start techniques to improve the speed with which the FMO problem for IM-TMI is solved and the quality of the end solution. We also consider a parallelism-enhanced algorithm to solve the FMO problem for IM-TMI treatment planning with a large number of beams (36 equispaced beams at each of 11 isocenters, for a total of 396 beams). We show that the backtracking line search strategy with step reduction exhibits the best performance and that using either of the two types of warm-start techniques which we consider leads to significant improvements in both solution time and quality. We also provide results for the aforementioned 396-beam plan and show that 30-beam solutions obtained using beam orientation optimization attain a comparable level of quality as this larger solution.
- Neighborhood Search Approaches to Non-Coplanar Beam Orientation Optimization for Total Marrow Irradiation using IMRT.
Mišić, V. V., Aleman, D. M., and Sharpe, M. B. (2010)
European Journal of Operational Research, 205 (3) 522-527.
[Abstract] [PDF]
Abstract:
We consider the beam orientation optimization (BOO) problem for total marrow irradiation (TMI) treatment planning using intensity modulated radiation therapy (IMRT). Currently, IMRT is not widely used in TMI treatment delivery; furthermore, the effect of using non-coplanar beam orientations is not known. We propose and implement several variations of a single neighborhood search algorithm that solves the BOO problem effectively when gantry angles and couch translations are considered. Our work shows that the BOO problem for TMI cases can be solved in a clinically acceptable amount of time and leads to treatment plans that are more effective than the conventional approach to TMI.
- Data, models and decisions for large-scale stochastic optimization.
Massachusetts Institute of Technology, PhD thesis. (2016)
[Abstract] [PDF]
Abstract:
Modern business decisions exceed human decision making ability: often, they are of a large scale, their outcomes are uncertain, and they are made in multiple stages. At the same time, firms have increasing access to data and models. Faced with such complex decisions and increasing access to data and models, how do we transform data and models into effective decisions? In this thesis, we address this question in the context of four important problems: the dynamic control of large-scale stochastic systems, the design of product lines under uncertainty, the selection of an assortment from historical transaction data and the design of a personalized assortment policy from data.
In the first chapter, we propose a new solution method for a general class of Markov decision processes (MDPs) called decomposable MDPs. We propose a novel linear optimization formulation that exploits the decomposable nature of the problem data to obtain a heuristic for the true problem. We show that the formulation is theoretically stronger than alternative proposals and provide numerical evidence for its strength in multiarmed bandit problems.
In the second chapter, we consider to how to make strategic product line decisions under uncertainty in the underlying choice model. We propose a method based on robust optimization for addressing both parameter uncertainty and structural uncertainty. We show using a real conjoint data set the benefits of our approach over the traditional approach that assumes both the model structure and the model parameters are known precisely.
In the third chapter, we propose a new two-step method for transforming limited customer transaction data into effective assortment decisions. The approach involves estimating a ranking-based choice model by solving a large-scale linear optimization problem, and solving a mixed-integer optimization problem to obtain a decision. Using synthetic data, we show that the approach is scalable, leads to accurate predictions and effective decisions that outperform alternative parametric and non-parametric approaches.
In the last chapter, we consider how to leverage auxiliary customer data to make personalized assortment decisions. We develop a simple method based on recursive partitioning that segments customers using their attributes and show that it improves on a "uniform" approach that ignores auxiliary customer information.
- Adaptive and robust radiation therapy optimization for lung cancer.
University of Toronto, Master of Applied Science thesis. (2012)
[Abstract] [PDF]
Abstract:
A previous approach to robust intensity-modulated radiation therapy (IMRT) treatment planning for moving tumours in the lung involves solving a single planning problem before treatment and using the resulting solution in all of the subsequent treatment sessions. In this thesis, we develop two adaptive robust IMRT optimization approaches for lung cancer, which involve using information gathered in prior treatment sessions to guide the reoptimization of the treatment for the next session. The first method is based on updating an estimate of the uncertain effect, while the second is based on additionally updating the dose requirements to account for prior errors in dose. We present computational results using real patient data for both methods and an asymptotic analysis for the first method. Through these results, we show that both methods lead to improvements in the final dose distribution over the traditional robust approach, but differ greatly in their daily dose performance.
- Computational enhancements to fluence map optimization for total marrow irradiation using IMRT.
University of Toronto, Bachelor of Applied Science thesis. (2010)
[Abstract] [PDF]
- Centennial Thesis Award, University of Toronto, 2010
Abstract:
Bone marrow transplants are frequently used to treat diseases such as blood and bone marrow cancers. To perform a bone marrow transplant, it is necessary to eliminate the patient’s existing bone marrow. In practice, this is most often achieved by irradiating the patient’s entire body – a process known as total body irradiation (TBI) – which frequently results in radiation related side effects. A safer alternative to TBI is total marrow irradiation (TMI), which is concerned with irradiating the bone marrow and avoiding healthy tissue as much as possible.
In prior work, we considered the possibility of using intensity modulated radiation therapy (IMRT) for the purpose of TMI and specifically, we developed algorithms to solve a fundamental problem in IMRT treatment planning known as the beam orientation optimization (BOO) problem. In this study, we consider the fluence map optimization (FMO) problem which is at the heart of the BOO problem and consider several methods of improving FMO solution speed and quality. In particular, we consider different line search strategies for the projected gradient algorithm which solves the FMO problem, different warm-start techniques for speeding up FMO evaluation in a BOO setting, and algorithms for parallelized objective function and gradient evaluation to improve the speed of FMO when a large number of beams is used.
We present results from our tests of different line search strategies and different warm start methods. We also report results from using our parallelism enhanced FMO algorithm to solve the FMO problem with 396 beams. We discuss the quality of the different line search and warm start methods; we also discuss the quality of the 30-beam solutions we studied in this and prior work and the limitations of using IMRT for TMI. We conclude by identifying some interesting questions for future research.
