MARKET-BASED DISTRIBUTED OPTIMIZATION APPROACHES FOR THREE CLASSES OF RESOURCE ALLOCATION PROBLEMS

Baisravan HomChaudhuri and Manish Kumar

References

  1. [1] R.A. Giliano and P.A. Mitchem, Valuation of network com-puting resources, S.H. Clearwater (ed.), Market based control:A paradigm for distributed resource allocation (New Jersey:World Scientific Publishing, 1996), 28–52.
  2. [2] K. Harty and D. Cheriton, A market approach to operatingsystem memory allocation, S.H. Clearwater (ed.), Market basedcontrol: A paradigm for distributed resource allocation (NewJersey: World Scientific Publishing, 1996), 126–155.
  3. [3] D.F. Ferguson, C. Nickolaou, J. Sairamesh, and Y. Yemini,Economic models for allocating resources in computer systems,S.H. Clearwater (ed.), Market based control: A paradigm fordistributed resource allocation (New Jersey: World ScientificPublishing, 1996), 156–183.
  4. [4] K. Kuwabara, T. Ishida, Y. Nishibe, and T. Suda, An equi-libratory market-based approach for distributed resource allo-cation and its application to communication network control,S.H. Clearwater (ed.), Market based control: A paradigm fordistributed resource allocation (New Jersey: World ScientificPublishing, 1996), 53–73.
  5. [5] A.D. Baker, A case study where agents bid with actual coststo schedule a factory, S.H. Clearwater (ed.), Market basedcontrol: A paradigm for distributed resource allocation (NewJersey: World Scientific Publishing, 1996), 184–223.
  6. [6] H. Voos, Resource allocation in continuous production usingmarket-based multi-agent systems, 5th IEEE Int. Conf. onIndustrial Informatics, 2, 2007, 1085–1090.
  7. [7] D.P. Bertsekas and J.N. Tsitsiklis, Parallel and distributedcomputation: Numerical methods, (Belmont: Athena Scientific,1997).
  8. [8] J.N. Tsitsiklis, Problems in decentralized decision making andcomputation, Ph.D. Thesis, Massachusetts Institute of Tech-nology, Cambridge, MA, 1984.
  9. [9] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, Randomizedgossip algorithms, IEEE Transactions on Information Theory,52, 2006, 2508–2530.
  10. [10] R.A. Freeman, P. Yang, and K.M. Lynch, Stability and con-vergence properties of dynamic average consensus estimators,Proc. IEEE Conf. on Decision and Control, San Diego, CA,2006, 398–403.
  11. [11] A. Jadbabaie, J. Lin, and A.S. Morse, Coordination of groupsof mobile autonomous agents using nearest neighbor rules,IEEE Transactions on Automatic Control, 48, 2003, 988–1001.
  12. [12] A. Nedic and A. Ozdaglar, Distributed subgradient methodsfor multi-agent optimization, IEEE Transactions on AutomaticControl, 54, 2009, 48–61.
  13. [13] A. Nedic, A. Ozdaglar, and P.A. Parrilo, Constrained consensusand optimization in multi-agent networks, IEEE Transactionson Automatic Control, 55(4), 2010, 922–938.
  14. [14] A.W. Colombo, R. Schoop, and R. Neubert, Collaborative(agent-based) factory automation, R. Zurawski (ed.), TheIndustrial Information Technology Handbook (Boca Raton,FL: CRC Press, 2004).
  15. [15] N. Jennings and S. Bussmann, Agent-based control, IEEEControl Systems Magazine, 23, 2003.
  16. [16] F. Kl¨ugl, A.L.C. Bazzan, and S. Ossowski, Applications of agenttechnology in traffic and transportation, (Berlin, Germany:Birkhauser Verlag, 2005).
  17. [17] G.B. Dantzig and P. Wolfe, Decomposition principle for linearprograms, Operations Research, 8(1), 1960, 101–111.
  18. [18] M. Zhu and S. Mart´inez, On distributed optimization underinequality constraints via lagrangian primal-dual methods,American Control Conf., Baltimore, MD, 2010, 4863–4868.
  19. [19] J.F. Benders, Partitioning procedures for solving mixed vari-ables programming problems, Numerische Mathematik, 4,1962, 238–252.
  20. [20] P.C. Gilmore and R.E. Gomory, A linear programming ap-proach to the cutting stock problem, Operations Research, 9,1961, 849–859.
  21. [21] J.E. Kelley, The cutting-plane method for solving convex pro-grams, Journal of the Society of Industrial Applied Mathemat-ics, 8, 1960, 703–712.
  22. [22] A.M. GeoKrion and G.W. Graves, Multicommodity distribu-tion system design by Benders decomposition, ManagementScience, 20, 1974, 822–844.
  23. [23] J.F. Cordeau, F. Pasin, and M.M. Solomon, An integratedmodel for logistics network design, Annals of Operations Re-search, 144, 2006, 59–82.
  24. [24] M. Florian, G. GuXerin, and G. Bushel, The engine schedulingproblem on a railway network, INFOR, 14, 1976, 121–138.
  25. [25] J.F. Cordeau, F. Soumis, and J. Desrosiers, A Benders de-composition approach for the locomotive and car assignmentproblem, Transportation Science, 34, 2000, 133–149.
  26. [26] J.F. Cordeau, F. Soumis, and J. Desrosiers, Simultaneous as-signment of locomotives and cars to passenger trains, Opera-tions Research, 49, 2001, 531–548.
  27. [27] X. Cai, D.C. McKinney, L.S. Lasdon, and D.W. Watkins Jr.,Solving large non-convex water resources management modelsusing generalized Benders decomposition, Operations Research,49, 2001, 235–245.
  28. [28] G. Zhao, A log-barrier method with Benders decompositionfor solving two-stage stochastic linear programs, MathematicalProgramming, 90, 2001, 507–536.
  29. [29] M. Karlsson and F. Ygge, Market-based approaches to opti-mization, Computational Intelligence, 23, 2007, 92–109.
  30. [30] A. Papavasiliou, H. Hindi, and D. Greene, Market-based controlmechanism for electric power demand response, Proc. IEEEConf. on Decision and Control, Atlanta, GA, 2010.
  31. [31] F. Kelly, A. Maulloo, and D. Tan, Rate control of commu-nication networks: Shadow prices, proportional fairness and11stability, Journal of Operations Research Society, 38, 1998,377–385.
  32. [32] S.H. Clearwater, Market-based control: A paradigm for dis-tributed resource allocation (New Jersey: World ScientificPublishing, 1996).
  33. [33] J.F. Kurose and R. Simha, A microeconomic approach tooptimal resource allocation in distributed computer systems,IEEE Transactions on Computers, 38, 1989, 705–717.
  34. [34] D. Bertsekas, Auction algorithms for network flow problems:A tutorial introduction, Computational Optimization and Ap-plications, 1, 1992, 7–66.
  35. [35] A.Th. Schreiber, Knowledge engineering and management:The common KADS methodology (Cambridge: The MIT Press,2000).
  36. [36] F. Ygge, Market-oriented programming and its applicationto power load management, Ph.D. Thesis, Department ofComputer Science, Lund University, Lund, Sweden, 1998.
  37. [37] R. Buyya, D. Abramson, J. Giddy, and H. Stockinger, Eco-nomic models for resource management and scheduling in gridcomputing, The Journal of Concurrency and Computation,14, 2002, 1507–1542.
  38. [38] Z. Tan and J.R. Gurd, Market-based grid resource allocationusing a stable continuous double auction, Proc. 8th IEEE/ACMInt. Conf. on Grid Computing, Austin, TX, 2007, 283–290.
  39. [39] J.E. Stiglitz, Pareto optimality and competition, Pareto Opti-mality and Competition, 36, 1981, 235–251.
  40. [40] M.L. Fisher, R. Jaikumar, and L.N.V. Wassenhove, A multiplieradjustment method for the generalized assignment problem,Management Science, 32(9), 1986, 1095–1103.
  41. [41] D.W. Pentico, Assignment problems: A golden anniversarysurvey, European Journal of Operational Research, 176, 2007,774–793.
  42. [42] M.D. Grigoriadis, D.J. Tang, and L.S. Woo, Considerations inthe optimal synthesis of some communications networks, 45thJoint National ORSA/TIMS Meeting, San Juan, PR, 1974.
  43. [43] M.L. Fisher and R. Jaikumar, A generalized assignment heuris-tic for vehicle routing, Networks, 11, 1981, 109–124.
  44. [44] V. Balachandran, An integer generalized transportation modelfor optimal job assignment in computer networks, OperationsResearch, 24(4), 1976, 742–759.
  45. [45] D. Gross and C.E. Pinkus, Optimal allocation of ships to yardsfor regular overhauls, Technical Memorandum, 63095, 1972.
  46. [46] B.P. Gerkey and M.J. Mataric, Multi-robot task allocation:Analyzing the complexity and optimality of key architectures,Proc. IEEE Int. Conf. on Robotics and Automation, ICRA’03,3, 2003, 3862–3868.
  47. [47] B. HomChaudhuri and M. Kumar, Market based allocationof power in smart grid, Proc. American Control Conf., SanFrancisco, CA, 2011, 3251–3256.
  48. [48] B. HomChaudhuri, M. Kumar, and V. Devabhaktuni, A marketbased distributed optimization for power allocation in smartgrid, Proc. Dynamic System and Control Conf., Arlington,VA, 2011.
  49. [49] S. Zhao, B. HomChaudhuri, and M. Kumar, A method fordistributed optimization for task allocation, Proc. ASME 2009Dynamic Systems and Control Conf., Hollywood, CA, 2009.
  50. [50] M. Kojima, S. Mizuno, and A. Yoshise, A primal-dual interiorpoint algorithm for linear programming (New York: Springer-Verlag, 1988).

Important Links:

Go Back