Analytics Corner

On "Robust Fluid Processing Networks" by Bertsimas, Nasrabadi and Paschalidis (2015)

Citation: Dimitris Bertsimas, Ebrahim Nasrabadi and Ioannis Paschalidis. (2015) Robust Fluid Processing Networks IEEE Transactions on Automatic Control, 60(3):715-728. Paper

Summary: Fluid networks provide a deterministic approximation to multiclass processing networks, making them much more tractable than their stochastic counterpart; however, the manager completely disregards randomness and there might be value in incorporating such uncertainty in the decision-making process. The authors' robust optimization approach aims at doing just that by combining the tractability of fluid networks and the practical relevance of including uncertainty in the modeling framework through an approach (robust optimization) that has a track record of leading to reformulated problems of complexity similar to that of the deterministic problems.

Specifically, the authors show that the robust fluid model preserves the computational tractability of the classical fluid problem and retains its original structure. They derive a scheduling policy determining how various classes should be processed at the servers of the network using complementary slackness optimality conditions. They also develop a polynomial-time algorithm under certain conditions. Simulation results demonstrate that the robust fluid policies are near-optimal when the optimal policies can be computed and outperform heuristics when the optimal policies cannot be computed in a tractable manner.

Outline:

I. Introduction

II. Problem description and fluid model

A. Criss-cross network

This is a simple network where one type goes through two servers (becoming class 1 and then class 3) but must compete with another type (class 2) at the first server. The second type doesn't go through the second server and simply exits the system.

B. A general formulation

The authors define the general problem, formulate its dual and write out the complementary slackness conditions.

III. Robust fluid model

A. Modeling the uncertainty

Uncertainty is incorporated on the arrival and service times (the lambda's and the 1/mu's) using Bertsimas-and-Sim uncertainty sets bounding the deviation from the nominal value by a total amount Gamma_j at server j at each time. 

B. Robust counterpart problem

The authors define the robust problem and re-formulate it in a tractable manner using strong duality arguments. 

C. Robust policies

The authors translate the optimal solution of the robust problem into a dynamic scheduling policy for the control of stochastic networks.  The idea is to give priority on each server to classes with the highest value of a new parameter between 0 and 1 computed using the optimal control found by solving the robust fluid problem.  

IV. A single-server system

In this section the authors show how they can find an optimal control for the robust fluid problem in polynomial time. They show they need to solve at most n linear optimization problems in the single-server case because they pick a class to serve until that class is depleted. Then an optimal policy is to serve each class with service rate the arrival rate and no job will be held in the network. This leads to a piecewise-constant solution with breakpoints the times where a class becomes depleted. 

A. Klimov's problem

All the results can carry over to a single server queue with probabilistic feedback.

V. Simulation results 

The goal is to compare the performance of the robust fluid policy to that of the optimal policy in small-size networks (when the optimal policy can be computed), and to that of reasonable heuristics on moderate to large-size networks. The authors also investigate the sensitivity of the robust policy to the parameter Gamma.

A. Computational remarks

B. Network examples

The authors consider four different network types: the criss-cross network and three types of reentrant networks, where at least one type of jobs cycles back to a server it had already visited. 

VI. Conclusion

Why I like this paper: First, there is the obvious reason that this paper provides a tractable approach to incorporating uncertainty in fluid networks, filling an important gap in the literature between (deterministic) fluid networks and stochastic networks. Also, over 15 years ago when I first started my PhD on robust optimization I did research on fluid networks for about a year before moving to inventory theory. It is fun to see that someone finally solved the problem, and the results are very elegant. I also love anything that uses strong duality or complementary slackness. 

Further reading:

  • Malcolm C. Pullan (1996) A duality theory for separated continuous linear programs. SIAM Journal on Control and Optimization, 34:931-965. The title says it all.
  • Mathieu Ricard (1995) Optimization of Queueing Networks: An Optimal Control Approach. PhD dissertation, MIT. It doesn't have anything about robust optimization in it but the threshold policies derived for various complex settings are impressive.

On "Project Management Under Risk: Using the Real Options Approach to Evaluate Flexibility in R&D" by Huchzermeier and Loch (2001)

In an effort to better remember the papers I read, I'm starting a new section about my blog devoted to short summaries of papers I find interesting. It's called "Analytics Corner". 

Citation: Arnd Huchzermeier, Christoph H. Loch, (2001) Project Management Under Risk: Using the Real Options Approach to Evaluate Flexibility in R&D. Management Science 47(1):85-101. Link

Summary: The authors consider a situation where a manager developing a new product can either abandon, continue or improve the product during development. Theyanalyze the setting using dynamic programming, study the impact of five types of uncertainty on the real options value  and obtain results counterintuitive to prevailing knowledge in option pricing theory, due to the unique features of the R&D real options framework. This paper contributes to improved risk management in R&D projects.

Outline:

1. Introduction and Literature Overview 

2. Five types of operational uncertainty

Market payoff variability, (R&D) budget variability, performance variability, market requirement variability, schedule variability (project may finish ahead of or behind schedule.

3. The basic model

3.1 Contingent claims analysis

Motivation of the use of dynamic programming, justification of discounting at the risk-free rate.

3.2 A dynamic programming model of an R&D project

T discrete stages corresponding to regular design reviews, leading to market introduction. Market success is determined by product performance, modeled by a one-dimensional parameter i. Performance uncertainty is captured in the variability of a probability distribution, measured by higher variance given same mean. This causes product (expected final) performance to drift between review period. Hence the authors define transition probabilities from expected performance state i to expected performance stage j. 

Performance may unexpectedly improve with probability p or deteriorate with probability 1-p. Improvement or deterioration are spread equally over the next N states. For instance the probability of improvement is p/N for j=i+1/2, i+1, ..., i+N/2. The parameters N and p can be chosen to approximate a distribution using its first two moments. At each time period, the manager can decide to abandon, continue or improve the project. (The originality of the paper comes from having the possibility to improve.) Improvement results of a mean shift of the transition probabilities by 1 (the index of each state j is increased by 1, both for improvement and deterioration.)

Expected payoff if the product is launched in state i is given by m+F(i)*(M-m) where m is the smaller margin if the project misses the performance level and competes only on cost and M is the profit margin if the project exceeds this performance level, and F(i) is the probability that performance i exceeds the market requirement D. This payoff function of i is assumed convex-concave increasing. 

The authors then formulate the manager's problem as a dynamic programming problem, writing out Bellman's equations from T back to time 0, evaluating the value of three actions (abandon, continue and improve) at each time period. They characterize the optimal policy as follows, assuming the payoff function is convex-concave increasing: there exists three functions L_u(t)>=L_m(t) and L_d(t) such that it is optimal to abandon if i<=L_d(t), and if i>L_d(t): continue if i>L_u(t) or i<=L_m(t) and improve if L_m(t)<i<=L_u(t). This is presented visually in Figure 4.

4. Uncertainty and the Value of Flexibility

This section studies the impact of increasing the variance of certain key drivers, to see whether the intuition that higher uncertainty in project payoff increases the real option value extends to other types of uncertainty faced by R&D managers.

4.1 Market payoff variability

4.2 Budget variability

4.3 Performance variability

4.4 Market requirements variability

4.5 Schedule variability

5. Conclusion

Why I like this paper: I like the use of dynamic programming in a managerial context (this is one of the papers I gave to read to the doctoral students in my PhD course on nonlinear programming) and the visual nature of the optimal policy shown in Figure 4. 

Further Reading: Real options: Managerial flexibility and strategy in resource allocation by Lenos Trigeorgis (1996)