We give two graph-theoretic models and a mixed-integer program to calculate the maximum achievable score in the popular board game “Ticket to Ride.” In Ticket to Ride, players compete to claim railway routes on a map, with points awarded based on the length of each route and the successful completion of destination tickets connecting specific city pairs. Each player has 45 train cars available, and each route can be chosen by only one player. Using the mixed-integer programming model, we examine the optimal solution with the 45 allocatable train cars, leading to an optimal score of 285 points. We also calculate the optimal solutions for up to 50 train cars. We determine the most frequently chosen tickets and routes over these 50 instances, giving insight into how optimization might be used to balance games. In particular, we identify several instances in which the point values can be adjusted to better balance the game.

Chemotherapy drug administration is a complex problem that often requires expensive clinical trials to evaluate potential regimens; one way to alleviate this burden and better inform future trials is to build reliable models for drug administration. This paper presents a mixed-integer program for combination chemotherapy (utilization of multiple drugs) optimization that incorporates various important operational constraints and, besides dose and concentration limits, controls treatment toxicity based on its effect on the count of white blood cells. To address the uncertainty of tumor heterogeneity, we also propose chance constraints that guarantee reaching an operable tumor size with a high probability in a neoadjuvant setting. We present analytical results pertinent to the accuracy of the model in representing biological processes of chemotherapy and establish its potential for clinical applications through a numerical study of breast cancer. History: Accepted by Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Funding: This work was supported by the National Science Foundation [Grants CMMI-1933369 and CMMI-1933373]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0207 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0207 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Intensive care units (ICUs) are crucial resources within hospitals, caring for the most critically ill patients. We propose a novel modeling framework that improves the outflow of ICU patients by anticipating unit interactions and resource sharing within the system. Across an arbitrary bipartite network of units, we consider two types of downstream staffing (baseline and flexible) and a two-stage decision process. In the first stage, we determine the level of flexible bed staffing using existing physical beds at downstream units in anticipation of incoming transfers from the ICUs. In the second stage, we determine the allocation of ICU patients to downstream beds. The goal of the model is to reduce inefficiencies and transfer delays causing ICU bed block due to lack of space in downstream units. We formulate a dynamic multiperiod model and analyze the dual of its (relaxed) stationary counterpart. Decomposing the relaxed stationary model into an ICU and downstream subproblems, we calculate the relative values of downstream beds and derive a practical acuity-based policy for the daily operational decisions. Using a large-scale simulation calibrated with historic hospital data, we demonstrate that our acuity-based policy reduces the number of long-run diverted ICU arrivals, particularly in high-demand scenarios, thus improving ICU throughput, when compared with a deterministic, a generalized randomized-most-idle, and static policies. History: Accepted by J. Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Funding: This work was partially supported by National Science Foundation [Grants CMMI-1635301/1635410/1635642]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1267 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0133 ) at ( http://dx.doi.org/10.5281/zenodo.7194693 ).

In accordance with the National Organ Transplant Act, which requires the efficient and equitable allocation of donated organs, the United Network for Organ Sharing (UNOS) prioritizes patients on th...

Many patients face difficulties when accessing medical facilities, particularly in rural areas. To alleviate these concerns, medical centers may offer transportation to eligible patients. However, the operation of such services is typically not tightly coordinated with the scheduling of medical appointments. Motivated by our collaborations with the U.S. Veterans Health Administration, we propose an integrated approach that simultaneously considers patient routing and operating room scheduling decisions. We model this problem as a mixed-integer program. Unfortunately, realistically sized instances of this problem are intractable, so we focus on a special case of the problem that captures the needs of low-volume (e.g., rural) hospitals. We establish structural properties that are exploited to develop a branch-and-price algorithm, which greatly outperforms a commercial solver on the original formulation. We discuss several algorithmic strategies to improve the overall solution efficiency. We evaluate the performance of the proposed approach through an extensive computational study calibrated with clinical data. Our results demonstrate that there exist opportunities for healthcare providers to significantly improve the quality of their services by integrating scheduling and routing decisions.

Robust dynamic programming (robust DP) mitigates the effects of ambiguity in transition probabilities on the solutions of Markov decision problems. We consider the computation of robust DP solutions for discrete-stage, infinite-horizon, discounted problems with finite state and action spaces. We present robust modified policy iteration (RMPI) and demonstrate its convergence. RMPI encompasses both of the previously known algorithms, robust value iteration and robust policy iteration. In addition to proposing exact RMPI, in which the “inner problem” is solved precisely, we propose inexact RMPI, in which the inner problem is solved to within a specified tolerance. We also introduce new stopping criteria based on the span seminorm. Finally, we demonstrate through some numerical studies that RMPI can significantly reduce computation time.

Scheduling elective procedures in an operating suite is a formidable task because of competing performance metrics and uncertain surgery durations. In this paper, we present an optimization framework for batch scheduling within a block booking system that maximizes the expected utilization of operating room resources subject to a set of probabilistic capacity constraints. The algorithm iteratively solves a series of mixed-integer programs that are based on a normal approximation of cumulative surgery durations. This approximation is suitable for high-volume medical specialities but might not be acceptable for the specialties that perform few procedures per block. We test our approach using the data from the ophthalmology department of the Veterans Affairs Pittsburgh Healthcare System. The performance of the schedules obtained by our approach is significantly better than schedules produced by simple heuristic scheduling rules.

We study the problem of (re)designing the regional network by which cadaveric livers are allocated. Whereas prior research focused mainly on maximizing a measure of efficiency of the network that was based on aggregate patient survival, we explicitly account for the trade-off between efficiency and a measure of geographical equity in the allocation process. To this end, we extend earlier optimization models to incorporate both objectives and develop an exact branch-and-price approach to solve this problem, generalizing a solution approach studied for the case where only efficiency is taken into account. In addition, we propose an effective solution algorithm that approximates the (generally nonconcave) frontier of Pareto-efficient solutions with respect to the two objectives by simultaneously generating and successively improving upper and lower bounds on this frontier. We implement and test our approach on observed data and show that solutions significantly dominating the current configuration in both efficiency and equity can be found. Of course, other subjective criteria are needed to choose among the different Pareto-efficient candidate solutions.

Operating room (OR) scheduling is an important operational problem for most hospitals. In this study, we present a novel two-stage stochastic mixed-integer programming model to minimize total expected operating cost given that scheduling decisions are made before the resolution of uncertainty in surgery durations. We use this model to quantify the benefit of pooling ORs as a shared resource and to illustrate the impact of parallel surgery processing on surgery schedules. Decisions in our model include the number of ORs to open each day, the allocation of surgeries to ORs, the sequence of surgeries within each OR, and the start time for each surgeon. Realistic-sized instances of our model are difficult or impossible to solve with standard stochastic programming techniques. Therefore, we exploit several structural properties of the model to achieve computational advantages. Furthermore, we describe a novel set of widely applicable valid inequalities that make it possible to solve practical instances. Based on our results for different resource usage schemes, we conclude that the impact of parallel surgery processing and the benefit of OR pooling are significant. The latter may lead to total cost reductions between 21% and 59% on average.

The most widely used progress measure for branch-and-bound (B&B) algorithms when solving mixed-integer programs (MIPs) is the MIP gap. We introduce a new progress measure that is often much smoother than the MIP gap. We propose a double exponential smoothing technique to predict the solution time of B&B algorithms and evaluate the prediction method using three MIP solvers. Our computational experiments show that accurate predictions of the solution time are possible, even in the early stages of B&B algorithms.

Abstract We develop stochastic integer programming techniques tailored toward solving a Synchronous Optical Network (SONET) ring design problem with uncertain demands. Our approach is based on an L‐shaped algorithm, whose (integer) master program prescribes a candidate network design, and whose (continuous) subproblems relay information regarding potential shortage penalty costs to the ring design decisions. This naive implementation performs very poorly due to two major problems: (1) the weakness of the master problem relaxations, and (2) the limited information passed to the master problem by the optimality cuts. Accordingly, we enforce certain necessary conditions regarding shortage penalty contributions to the objective function within the master problem, along with a corresponding set of valid inequalities that improves the solvability of the master problem. We also show how a nonlinear reformulation of the model can be used to capture an exponential number of optimality cuts generated by the linear model. We augment these techniques with a powerful upper‐bounding heuristic to further accelerate the convergence of the algorithm, and demonstrate the effectiveness of our methodologies on a test bed of randomly generated stochastic SONET instances. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 12–26 2004