Projects

Methodologies

  • Stochastic Integer Programming

  • Risk-averse Optimization

  • Network Games and Optimization

  • Mixed-integer Nonlinear Programming

  • High Performance Computing

Applications

  • Transportation & Logistics

  • Interdependent Critical Infrastructures

  • Power Flow Optimization

  • Healthcare Operations Management

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:

alt text 
  • 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.

(Collaborators: M. Lejeune at GWU; Cong Shi in IOE at UMich.)

2.Integrated System Design, Resource Planning and Operations (sponsors: NSF, UMich M-cube)

alt text 

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.

alt text 

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.

(Collaborators: Brian Denton, Cong Shi, and Mark Daskin in IOE at UMich; Ruiwei Jiang at U of Michigan; Xuan Vinh Doan at Warwick Business School in UK)

3.Decomposition Algorithms, Large-Scale Optimization, and Parallel Computing (sponsor: DoE)

alt text 

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.

(Collaborators: Shabbir Ahmed at Gatech; Jon Lee in IOE at UMich; J. Cole Smith at Clemson)

4.Network Optimization, Interdiction, and Protection Under Uncertain Data (sponsor: DoD/Army)

alt text 

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.

(Collaborators: Yongjia Song at VCU; Zhili Zhou at IBM Singapore; Enlu Zhou at Gatech; Qipeng Zheng at UCF; Murat Kurt at SUNY Buffalo; J. Cole Smith at Clemson; Eugene Vorobeychik at Vanderbilt)

5.Load Control Optimization in Sustainable Power Systems; Power Stablization under Contingency (sponsor: NSF)

alt text 

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.

(Collaborators: Johanna L. Mathieu and Ian A. Hiskens in EECS, Ruiwei Jiang in IOE at U of Michigan)

6.Carsharing/Ridesharing System Design and Operations Optimization (sponsors: NSF, DiDi, UMich M-cube, Ford)

alt text 

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.

(Collaborators: Pascal Van Hentenryck at Georgia Tech, Ruiwei Jiang, Viswanath Nagarajan, Yafeng Yin, Robert Hampshire, Peter Adriaens at U of Michigan; Mengshi Lu at Purdue University)

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.

(Collaborators: Yafeng Yin and Yiheng Feng at U of Michigan.)

Completed Projects

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

for their generous support to our research and education activities.


alt text 

Related Product

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.




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:

alt text