My presentation about using OR/IE models for solving COVID-19 related problems in the IOE lunch-and-learn series in March 2020.
A video showing the redesign of the University of Michigan campus bus system during the pandemic to ensure safer travels through social distancing and shorter routes.
A video describing a network-based epidemic control project that my student, my collaborator (Eugene Vorobeychik at Vanderbilt), and I have worked on. Specially thanks to MconneX | MichEpedia for shooting the video.
Related Research
1.Risk Management under Ambiguous Decision Preferences (sponsor: NSF)
We develop modeling techniques and computational paradigms for complex service systems that need to correlate a variety of information and decisions. We design risk optimization approaches that are capable of handling integrated system design and service operations with multiple resources, multiple stages of service, and multiple stakeholders with diverse decision preferences under data uncertainty.
One of the risk-averse stochastic optimization models we consider is called chance-constrained program (CCP), which bounds the probability of the occurrence of undesirable random outcomes. Given constraint A x >= b with either matrix A or vector b (or both) being random, a chance constraint reads: Pr(Ax >= b) >= 1-\alpha, where 1-\alpha represents a required reliability level. We analyze a multi-objective CCP variant that considers the reliability 1-\alpha as a decision variable, and trades off between the original objective cost and the “cost of reputation” associated with the quality of service given by 1-\alpha.
Instead of parametric analysis, we develop integer-programming-based approaches to study:
optimal 1-\alpha for different forms of reputation cost functions, e.g., linear, pwl.
tradeoffs in multiple objectives and reliabilities associated with multiple joint chance constraints regarding multiple uncertain processes or systems.
mixed-integer programming reformulations, support vector machines (SVM) from data mining, decomposition methods, and valid inequalities for optimizing CCP models with variable risk parameter.
2.Integrated System Design, Resource Planning and Operations (sponsors: NSF, UMich M-cube)
Many service systems in health care operations, cloud computing, transportation, etc., possess structural similarities in integrated system design and service operations. We focus on (1) the study of stochastic optimization approaches that can incorporate different performance metrics for guiding service operations and balancing risk and return; and (2) the exploration of problem structures that will result in efficient and scalable computational schemes.
For example, we study a problem of stochastic resource allocation and scheduling, which involves chance constraints for measuring the risk of operational decisions under uncertainty. We describe the problem in the context of surgery planning in Operating Rooms (ORs) under uncertain surgery durations, for which we formulate CCPs to improve the quality of service and service fairness: two chance constraints respectively guarantee low probabilities of having long waiting time of patients and OR overtime for completing surgeries.
The resulting formulation is highly complex, with multiple types of binary variables (for both allocation and scheduling decisions) and chance constraints. We develop decomposition algorithms and various types of cutting planes for optimizing the results.
3.Decomposition Algorithms, Large-Scale Optimization, and Parallel Computing (sponsor: DoE)
We develop new decomposition paradigms for stochastic integer programming models, and generate more effective cutting planes and objective bounds. We focus on two-stage stochastic integer programs, and advance decomposition paradigms based on special structures of specific risk-averse programs, and also based on special integer-programming structures (e.g., totally unimodularity, special ordered sets of type 1 (SOS1), cover inequalities). We have implemented the related approaches in a series of research projects that optimize stochastic problems of (i) project management, (ii) resource allocation, (iii) appointment scheduling, and (iv) network interdiction. Moreover, the new decomposition paradigms can be widely applied to large-scale complex system design and operations management, including optimizing critical interdependent infrastructures such as power grids, transportation systems, and cyber-clouds.
4.Network Optimization, Interdiction, and Protection Under Uncertain Data (sponsor: DoD/Army)
We design networks and optimize network operations in energy, healthcare, and transportation, in particular focusing on problems of critical infrastructure design (e.g., power grids), epidemic control, and transportation under uncertainty. We use stochastic programming models and decomposition algorithms for tackling large-scale network problems with random supply/demand or arc disruptions.
We also study network interdiction models and design algorithms for specially-structured networks (e.g., trees, small-world networks) in related problems. Dynamic programming and heuristic approaches are used for deriving solutions in polynomial time, and generating valid bounds to the stochastic integer programs.
In particular, we are interested in network optimization problems with constraints/ objective functions reflecting risk-averse behavior of a decision maker. For instance, in a risk-averse shortest path interdiction problem, a follower aims to identify a path under random arc cost, and minimizes the VaR of the path length for a given reliability level. We develop heuristics and exact cutting-plane algorithms. In addition, by constructing path-flow reformulations, we design column generation algorithms to improve the computational efficacy. The risk-averse network interdiction models can be generalized to problems of UAV routing, cloud computing data exchange, and emergency service delivery.
5.Load Control Optimization in Sustainable Power Systems; Power Stablization under Contingency (sponsor: NSF)
With increasing penetrations of fluctuating renewable energy sources, such as wind power plants and solar photovoltaics, and active participation of electric loads in power system operation, uncertainty will increase. Specifically, we develop data-driven and distribution-free optimization methods that are suited to dispatching power systems with both fluctuating renewable energy sources and flexible loads contributing to balancing reserves via load control. The flexibility of an aggregation of loads is difficult to compute and uncertain. Investigating, characterizing, and managing this uncertainty is the focus of this research. Moreover, we quantify the tradeoff between the uncertainty and profitability of load control, and the effect of uncertainty and methods for managing it on power system dispatch, which affects pollutant emissions.
6.Carsharing/Ridesharing System Design and Operations Optimization (sponsors: NSF, DiDi, UMich M-cube, Ford)
We consider vehicle routing, service matching, and appointment scheduling arising in large-scale carsharing and ridesharing problems. We use mixed-integer programming formulations and spatial-temporal networks to model carsharing/ridesharing systems and analyze related operations. We apply stochastic programming and dynamic programming techniques to optimize real-time operations, under uncertain travel time and service time. We examine a wide class of mobility sharing systems, including on-demand ridesharing companies such as DiDi ChuXing, and not-for-profit carsharing for underserved populations.
7.Real-time traffic signal control (sponsor: USDOT Center for Connected Automated Transportation (CCAT))
The centralized control models that are commonly used to regulate traffic lights at a specific intersection can become inefficient when the intersection is viewed as a part of larger ecosystem of multiple intersections across a large area. This research aims to revolutionize the current process of traffic signal timing via distributed and decentralized optimization methods. The challenge is to develop and solve network-based signal control models with random variables and complicated nonlinear constraints that represent how traffic lights communicate and coordinate.
“DiDi: Learning-Based Distributionally Robust Optimization Method for Route Planning,” (with co-PI, Yafeng Yin in CEE at UMich), Didi Chuxing, 2018-2019.
“DiDi: Real-Time Optimization and Pricing of Ride Sharing,” (with other PIs: Pascal Van Hentenryck currently at Georgia Tech, ISyE; Viswanath Nagarajan in IOE at UMich), Didi Chuxing, 2017-2018.
“Business Model Innovation and Operational Strategies for Shared Autonomous Vehicles,” (with other PIs: Robert Hampshire at UM Transportation Research Institute; Peter Adriaens at Department of Civil and Environmental Engineering), M-cubed program, University of Michigan, 07.2016-12.2017.
“Data-driven Risk-aware Adversarial Analysis under Uncertainty,” U.S. Department of Defense, Department of Army, 02.2017-11.2017.
“Optimization in Smarter-Grid Engineering and Operations,” IBM Smarter Planet Innovation Faculty Award, 2012-2013.
“Mathematical Modeling for Improving System Sustainability: From the Classroom Experience to Real-world Applications,” Procter & Gamble Higher Education Grant Program, 2012.
Acknowledgement
We would like to acknowlege our sponsors, including
National Science Foundation
Department of Energy
Department of Defense, Army Research Office
USDOT Center for Connected Automated Transportation (CCAT)
Ford Motor Company
IBM
Procter & Gamble
DiDi ChuXing
Microsoft
for their generous support to our research and education activities.
To sum up, I am interested in problems that combine stochastic programming, mixed-integer programming, network optimization, as well as learning and statistics. I find both theories and applications in the related research areas very interesting. Lastly, despite that I am an optimizer, here is what I truly follow: