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.
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.
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.
- 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.