Liver Allocation Policy Design
Allocating livers for transplantation has been a controversial issue in the United States for decades. This line of research applies operations research and decision science techniques to refine and select liver allocation policy for optimally allocating transplantable organs.
Optimal Region Design for Liver Allocation
Two main allocation approaches developed in the past are (1) to allocate organs to patients with higher priority at the same locale; (2) to allocate organs to patients with the greatest medical need regardless of their locations. To balance these two allocation approaches, the U.S. organ transplantation and allocation network has implemented a three-tier hierarchical allocation system, dividing the U.S. into 11 regions. The purpose of allocating organs at the regional level is to increase the likelihood that a donor-recipient match exists, compared to the former allocation approach, and to increase the quality of the match, compared to the latter approach. However, the question of which regional configuration is the most efficient for regional liver distribution remains unanswered.
Dissertation Title: Optimizing the Efficiency of the United States Organ Allocation System through Region Reorganization.
Dissertation Summary: One of the remaining central questions is how to facilitate regional distribution of organ procurement organizations. We develop a large-scale set-partitioning model to find the most efficient set of regions. We also design a branch-and-price algorithm for the problem, for which we apply a decomposition-based heuristic and several valid inequalities to improve the algorithm effectiveness. The computational studies use clinical data and show that (1) regional reorganization is beneficial; (2) the branch-and-price algorithm is effective to the optimal region design problem.
Two theoretical extensions were also studied in my dissertation. One is polyhedral study for the mixed-integer programming reformulation of a class of 0-1 fractional programs that includes the pricing problem of optimal region design. The other is generalization of proportional resource allocation that creates a fair allocation environment.
Here is an electronic copy of my dissertation.
Nan's dissertation has been chosen as a finalist of the 2006 INFORMS George B. Dantzig Dissertation Award for "the best dissertation in any area of operations research and the management sciences that is innovative and relevant to practice." The final selection will be announced during the INFORMS annual meeting in November 2006.
Joint work with Andrew J. Schaefer and Brady Hunsaker.
Publication:
Stahl, J.E., N. Kong, S.M. Shechter, A.J. Schaefer, and M.S. Roberts, “A Methodological Framework for Optimally Re-Organizing Liver Transplant Regions,” 2005. Medical Decision Making. Vol. 25, No. 3, pp. 35-46.
Working Paper:
Kong, N., A.J. Schaefer, and B. Hunsaker, "Maximizing the Efficiency of the U.S. Liver Allocation Systems through Region Design." To be submitted to Operations Research. 2006.
Kong, N., A.J. Schaefer, and B. Hunsaker, "A Polyhedral Study for the Pricing Problem in Optimal Region Design," 2006. To be submitted to Discrete Optimization.
Kong, N., A.J. Schaefer, and B. Hunsaker, "Generalization of Proportional Resource Allocation," 2006.
Since joining USF, Nan has established relationship with LifeLink, the local Organ Procurement Organization (OPO) in the Tampa Bay area. His continuing work in liver allocation policy study includes the following:
Simulation-based Optimization for Organ Allocation Policy Selection
Allocating organs is a complicated resource allocation process. Hence, it is difficult to guarantee modeling realism and accuracy when designing an analytic evaluation of allocation policy with respect to realistic medical outcomes. On the other hand, a discrete-event simulation model is capable of greatly incorporating system realism. However, previous simulation models suffer from heavy computational burden and thus are unlikely to be applied for the purpose of selecting the optimal allocation policy. We are developing a new simulation model and integrate it into a meta-heuristic optimization framework.
Joint work with my Ph.D. student Patricio Rocha, and my REU student Egor Dolzhenko. This work is currently funded by a USF New Researcher Grant. The co-PI is a researcher from the Department of Epidemiology and Biostatistics in the College of Public Health at USF. The grant proposal is here. Nan also received a USF Faculty International Travel Grant for presenting the work in INFORMS International 2006 at Hong Kong, China.
Working Paper:
Rocha, P., E. Dolzhenko and N. Kong, “A Simulation-based Optimization Approach to Policy Selection for the U.S. Liver Transplantation and Allocation System,” 2006. Target Journal: IIE Transactions.
Rocha, P., E. Dolzhenko and N. Kong, “Simulation Optimization for a Large-scale Set-Partitioning Problem in Liver Allocation,” 2006. Target Journal: Algorithmic Operations Research.
An Analytic Hierarchy Processes (AHP) Approach to Organ Allocation Policy Selection
One of the main concern in organ allocation is the tradeoff between system efficiency and equity. It is difficult to reach consensus on allocation policy among transplantation policy makers, administrators, transplant surgeons, and transplant candidates and their families. This research uses AHP to build a framework that quantifies the policy selection process to help policy makers reach valid consensus in terms of balancing medical outcomes that fall into the two categories: efficiency and equity.
Working Paper:
Kong, N. and V. Veerachandran “Assisting Policy Making for Balancing the Efficiency and Equity of the U.S. Liver Allocation: An Analytic Hierarchy Processes (AHP) Approach,” 2006. Target Journal: Health Care Management Science.
Stochastic Integer Programming
Stochastic integer programs (SIPs) have been notoriously difficult to solve. Algorithmic develop and computational enhancement for SIPs still remains at its infancy.
A Superadditive Duality Approach for Two-Stage SIPs
We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances whose extensive forms are several orders of magnitude larger than the extensive forms of those instances found in the literature.
This is a joint work with Andrew J. Schaefer and Brady Hunsaker.
A Constant Factor Approximation Algorithm for Two-Stage Stochastic Combinatorial Optimization Problems
We introduce the two-stage stochastic maximum-weight matching problem and demonstrate that this problem is NP-complete. We give a factor 1/2 approximation algorithm and prove its correctness. We also provide a tight example to show the bound given by the algorithm is exactly 1/2. Computational results on some two-stage stochastic bipartite matching instances indicate that the performance of the approximation algorithm appears to be substantially better than its worst-case performance.
This work can be generalized to a class of two-stage stochastic programs with TU technology and recourse matrices. It is one of the early attempts in applying approximation algorithms to stochastic combinatorial optimization problems.
This is a joint work with Andrew J. Schaefer.
Total Unimodular Stochastic Programs
We consider totally unimodular stochastic programs, that is, stochastic programs whose extensive-form constraint matrix is totally unimodular. We generalize the notion of total unimodularity to apply to sets of matrices and provide properties of such sets. Using this notion, we give several sufficient conditions for stochastic programs to be totally unimodular, and provide necessary conditions for specific classes of problems. When solving such problems using the L-shaped method it is not clear whether the integrality restrictions should be imposed on the master problem. Such restrictions will make each master problem more difficult to solve. On the other hand, solving the linear relaxation of the master typically means sending fractional (and unlikely optimal) solutions to the subproblems, perhaps leading to more iterations. Our computational results investigate this trade-off and provide insight into which strategy is preferable under a variety of circumstances.
This is a joint work with Andrew J. Schaefer and Shabbir Ahmed.
A Hierarchical Bounding Technique Investigation for Two-Stage SIPs
We consider a general two-stage stochastic mixed-integer program with discrete distribution and finite support. We derive a class of bounds for the optimal objective value of this problem by solving a group of truncated deterministic equivalent problems, each of which corresponds to a subset of scenarios. For the cases where the number of scenarios is large, we apply sampling techniques. Computational results for several stochastic linear and integer programs are presented.
This is a joint work with Burhaneddin Sandikci and Andrew J. Schaefer.
Publications:
Kong, N., A.J. Schaefer, and B. Hunsaker, “Two-Stage Integer Programs with Stochastic Right-Hand Sides: A Superadditive Dual Approach,” 2006. Mathematical Programming. Vol. 108, pp. 275-296.
Kong, N. and A.J. Schaefer, “A Factor ½ Approximation Algorithm for a Class of Two-Stage Stochastic Mixed-Integer Programs,” 2006. European Journal of Operational Research. Vol. 172, pp. 740-746.
Paper Currently under Review at a Full Reviewed Journal:
Kong, N., A.J. Schaefer, and S. Ahmed, “Totally Unimodular Stochastic Programs.” Submitted to Mathematical Programming. 2006. Available Online at Optimization Online Digest – May 2006.
Working Paper:
Sandikci, B., N. Kong, and A.J. Schaefer, “A Hierarchy of Bounds for Two-Stage Stochastic Mixed-Integer Programs,” 2006. To be submitted to INFORMS Journal on Computing.
My other work covers a variety of theoretical topics that lie in computational discrete optimization and discrete optimization under uncertainty. On the applied side, I have started working on several other issues related to organ transplantation using simulation and optimization. I have also started exploring application of OR modeling and solution techniques in large-scale logistic and monitoring networks in health care, environmental science, electricity generation, and homeland security.
Other Issues in Organ Allocation. 1) Heart Technology Assessment. With our expertise and extensive study in liver allocation, we plan to understand the current environment of organ replacement and supplementation technologies by developing, verifying, and validating a simulation model of the current allocation system for heart transplants. We have resubmitted an NIH R01 grant proposal for second review, on which I am a co-PI. 2) Prompt kidney transplantation. A major challenge faced by an organ procurement organization (OPO) is to place / allocate organs promptly. It is often difficult to place extended criteria donor (ECD) kidneys, i.e. donors have problems -- the elderly donor, the donor with risk factors for transmission of disease. We have started our collaboration with LinfeLink, the local OPO in the Tampa Bay area, to study this problem.
Outpatient Clinic Access Management. The goal of outpatient clinic access management is to provide quality care when patients want and need it. To build a sustainable advanced clinic access system, one not only needs to optimize conventional system metrics such as appointment waiting time, but also address the following issues: 1) how to increase the system ability to predict and absorb demand; 2) how to match supply and demand; 3) how to redesign the system to increase supply. A large Veterans’ hospital may be responsible for an area with more than 5 million population. Due to the huge volume of demand, an appointment for a outpatient visit often takes months in the current practice, especially for visiting specialists. In addition, patients have to come to the main medical facility to receive necessary treatment. As a result, medical service satisfaction level is further decreased. Since a Veterans’ hospital can also deliver care in lower-scale local clinics. It is possible to redesign the system such that physicians, especially specialists, and patients can both visit local clinics. Many OR questions arise here including resource allocation, scheduling, routing, etc. The complexity of special health care provision complicates the problem. This requires an optimal design of team staffing. Such a problem is important especially for heath care provision in a rural area from a large provider. We have teamed up with the Veteran’s hospital in Tampa FL. I plan to submit an NSF unsolicited proposal to CMMI SEE program next February.
Optimal Design of Air Pollution Monitoring Networks. There have been many Monte-Carlo simulation models for estimating spatial and temporal average air pollutant concentration values. The location of air quality sensors affects the accuracy of these estimates. Hence, a major challenge is how to optimally design the monitoring network such that the accuracy of these estimates meet the requirement give the resource limitation. This decision is often times influenced by the major facilities of interest in the studied area. For example, in a metropolitan area, schools and highways may be focal points. Furthermore, higher-level decision making, beach advisory in Florida, must be driven by observed air quality data. We have started an interdisciplinary collaboration with a researcher from the Department of Environmental and Occupational Health in the College of Public Health at USF.
Stochastic Programming with Decision-Dependent Uncertainty. There is limited work that deals with decision-dependent uncertainty in the stochastic programming literature, even though this type of uncertainty is very common in many real-world applications. On the other hand, standard stochastic programs that only consider decision-independent uncertainty have been studied intensively. I am currently investigating the power and applicability of stochastic programming in modeling and solving optimization problems under decision-dependent uncertainty. For example, one focus will be to develop models and solutions to address stochastic programs in which uncertainty is not necessarily affinely dependent upon the decisions and decisions do not have to be discrete. I plan to use sequential decision making in liver offer acceptance and HIV treatment planning as focal real-world applications. I have submitted an NSF grant proposal on this topic.
Resource Allocation in Competitive Markov Decision Making Processes. The Department of homeland Security's Secure Boarder Initiative (SBI) has included a comprehensive and systematic upgrading of the technology used in controlling the border. We present a model to assist in the allocation of static resources for border control. More generally, we introduce a framework for optimally allocating static interdiction devices in a zero-sum, one player controlled stochastic game. Benders' decomposition is applied for the resultant large-scale mixed-integer program. Currently I am working on the paper "Static and Dynamic Resource Allocation in Competitive Markov Decision Processes" with Halil Bayrak and Matthew D. Bailey. The paper will be submitted to Operations Research.
Stochastic Mathematical Programs with Equilibrium Constraints in Electricity Transmission. Previously strategic games in the electricity market have been modeled as mathematical programs with equilibrium constraints (MPECs). However, the uncertainty in electricity generation demand should not be ignored in many cases. This work attempts to extend the previous studies in solving these games in the electricity market to address demand uncertainty. General solution techniques for SMPCs are being investigated. Currently I am working on the paper "Solving a Stochastic Cournot Game in the Electricity Market as Stochastic Mathematical Program with Equilibrium Constraints" with Lizhi Wang and Mainak Mazumdar.
Other topics include
Latest Update: November, 2006