Efficient Algorithms for Separated Continuous Linear Programs: The Multicommodity Flow Problem with Holding Costs and Extensions

References

• Anderson E. J. A continuous model for job-shop scheduling. (1978) . Ph.D. thesis, University of Cambridge, Cambridge, UKGoogle Scholar
• Anderson E. J., Nash P.Linear Programming in Infinite-Dimensional Spaces (1987) (John Wiley & Sons, New York) Google Scholar
• Anderson E. J., Nash P., Perold A. F. Some properties of a class of continuous linear programs. SIAM J. Control Optim. (1983) 21(5):758–765Crossref, Google Scholar
• Avram F., Bertsimas D., Ricard M., Kelly F. P., Williams R. J. Fluid models of sequencing problems in open queueing networks: An optimal control approach. Stochastic Networks (1995) 71(Springer-Verlag, New York) 199–234Proc. Internat. Math. AssociationCrossref, Google Scholar
• Avram F., Bertsimas D., Sethuraman J. Optimal control of fluid tandem networks. . Working paper, CORC Technical Report TR-2005-08Google Scholar
• Bauerle N. Asymptotic optimality of tracking policies in stochastic networks. Ann. Appl. Probab. (2000) 10(4):1065–1083Crossref, Google Scholar
• Bellman R. Bottleneck problem and dynamic programming. Proc. National Acad. Sci. (1953) 39:947–951Crossref, Google Scholar
• Bellman R.Dynamic Programming (1957) (Princeton University Press, Princeton, NJ) Google Scholar
• Bertsimas D., Gamarnik D., Sethuraman J. From fluid relaxations to practical algorithms for high multiplicity job shop scheduling: The holding cost objective. Oper. Res. (2003) 51(5):798–813Link, Google Scholar
• Bertsimas D., Sethuraman J. From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective. Math. Programming (2002) 92(1):61–102Crossref, Google Scholar
• Chen H., Mandelbaum A. Discrete flow networks: Bottleneck analysis and fluid approximations. Math. Oper. Res. (1991) 16(2):408–446Link, Google Scholar
• Chen H., Mandelbaum A., Yao D. D. Hierarchical modeling of stochastic networks, Part I: Fluid models. Stochastic Modeling and Analysis of Manufacturing Systems (1994) (Springer-Verlag, New York) 47–105Crossref, Google Scholar
• Chen H., Yao D. D.Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization (2001) (Springer-Verlag, New York) Crossref, Google Scholar
• Dai J. G., Weiss G. A fluid heuristic for minimizing makespan in job-shops. Oper. Res. (2002) 50(4):692–707Link, Google Scholar
• Filipiak J.Modelling and Control of Dynamic Flows in Communication Networks (1988) (Springer-Verlag, Berlin, Germany) Crossref, Google Scholar
• Fleischer L. Faster algorithms for the quickest transshipment problem. SIAM J. Optim. (2001) 12(1):18–35Crossref, Google Scholar
• Fleischer L., Skutella M. The quickest multicommodity flow problem. 9th Internat. Integer Programming and Combinatorial Optimization Conf. (2002) 36–53Number 2337, Lecture Notes in Computer ScienceCrossref, Google Scholar
• Fleischer L., Skutella M. Quickest flows over time. SIAM J. Comput. (2003) . ForthcomingGoogle Scholar
• Gans N., van Ryzin G. Optimal control of a multiclass, flexible queueing system. Oper. Res. (1997) 45(5):677–693Link, Google Scholar
• Grötschel M., Lovász L., Schrijver A. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica (1981) 1:169–197Crossref, Google Scholar
• Hajek B., Ogier R. G. Optimal dynamic routing in communication networks with continuous traffic. Networks (1984) 14:457–487Crossref, Google Scholar
• Harrison J. M.Brownian Motion and Stochastic Flow Systems (1985) (John Wiley & Sons, New York) Google Scholar
• Harrison J. M., Fleming W., Lions P. L. Brownian models of queueing networks with heterogenous customer populations. Stochastic Differential Systems, Stochastic Control Theory and Applications, Proc. Internat. Math. Association (1988) (Springer-Verlag, New York) 147–186Crossref, Google Scholar
• Harrison J. M., Kelly F. P., Zachary S., Ziedins I. The bigstep approach to flow management in stochastic processing networks. Stochastic Networks: Theory and Applications, Royal Statistical Society Lecture Note Series, No. 4 (1996) (Oxford University Press, Oxford, UK) 57–90Google Scholar
• Harrison J. M. Stochastic networks and activity analysis. Analytic Methods in Applied Probability (2002) 207(American Mathematical Society, Providence, RI) 53–76American Mathematical Society Translations Ser. 2Crossref, Google Scholar
• Hoppe B., Tardos É. Polynomial time algorithms for some evacuation problems. Proc. 5th Annual ACM-SIAM Sympos. Discrete Algorithms (1994) (ACM, New York) 433–441Google Scholar
• Luo X., Bertsimas D. A new algorithm for state-constrained separated continuous linear programs. SIAM J. Control Optim. (1999) 37(1):177–210Crossref, Google Scholar
• Maglaras C. Dynamic control of stochastic processing networks: A fluid model approach. (1998) . Ph.D. thesis, Stanford University, Stanford, CAGoogle Scholar
• Maglaras C. Discrete-review policies for scheduling stochastic networks: Trajectory tracking and fluid-scale asymptotic optimality. Ann. Appl. Probab. (2000) 10(3):897–929Crossref, Google Scholar
• Meyn S. P., Yin G. G., Zhang Q. Stability and optimization of queueing networks and their fluid models. Mathematics of Stochastic Manufacturing Systems (1997) 33(American Mathematical Society, Providence, RI) 175–200Lectures in Applied MathematicsGoogle Scholar
• Philpott A. B., Craddock M. An adaptive discretization algorithm for a class of continuous network programs. Networks (1995) 26:1–11Crossref, Google Scholar
• Pullan M. C. An algorithm for a class of continuous linear programs. SIAM J. Control Optim. (1993) 31(6):1558–1577Crossref, Google Scholar
• Pullan M. C. Forms of optimal solutions for separated continuous linear programs. SIAM J. Control Optim. (1995) 33(6):1952–1977Crossref, Google Scholar
• Pullan M. C. A duality theory for separated continuous linear programs. SIAM J. Control Optim. (1996) 34(3):931–965Crossref, Google Scholar
• Sethuraman J. Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations. (1999) . Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar