Adaptive price update in distributed Lagrangian relaxation protocol

ABSTRACT

Distributed Lagrangian Relaxation Protocol (DisLRP) has been proposed to solve a distributed combinatorial maximization problem called the Generalized Mutual Assignment Problem (GMAP). In DisLRP, when updating Lagrange multipliers (prices) of goods, the agents basically control their step length, which determines the degree of update, by a static rule. A merit of this updating rule is that since it is static, it is easy to implement even without a central control. Furthermore, if we choose this static rule appropriately, we have observed empirically that DisLRP converges to a state providing a good upper bound. However, it must be difficult to devise such a good static rule for updating step length since it naturally depends on problem instances to be solved. On the other hand, in a centralized context, the Lagrangian relaxation approach has conventionally computed step length by exploiting the least upper bound obtained during the search and a lower bound obtained through preprocessing. In this paper, we achieve this approach in a distributed environment where no central control exists and name the resultant protocol Adaptive DisLRP (ADisLRP). The key ideas of this new protocol are to 1) compute global information with a spanning tree, 2) update step length simultaneously with a synchronization protocol, and 3) estimate lower bounds during the search. We also show the robustness of ADisLRP through experiments where we compared ADisLRP with the previous protocols on the critically hard benchmark instances.

REFERENCES

• 1: I. P. Androulakis and G. V. Reklaitis. Approaches to asynchronous decentralized decision making. Computers and Chemical Engineering, 23:341--355, 1999.
• 2: Marc Bui , Franck Butelle , Christian Lavault, A distributed algorithm for constructing a minimum diameter spanning tree, Journal of Parallel and Distributed Computing, v.64 n.5, p.571-577, May 2004 [doi>10.1016/j.jpdc.2004.03.009]
• 3: D. G. Cattrysse and L. N. V. Wassenhove. A survey of algorithms for the generalized assignment problem. European Journal of Operational Research, 60:260--272, 1992.
• 4: M. B. Dias, R. Zlot, N. Kalra, and A. Stentz. Market-based multirobot coordination: a survey and analysis. Proceedings of the IEEE, 94(7):1257--1270, 2006.
• 5: M. L. Fisher. The Lagrangian relaxation method for solving integer programming problems. Management Science, 27(1):1--18, 1981.
• 6: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 7: F. C. Gärtner. A survey of self-stabilizing spanning-tree construction algorithms. Technical Report IC/2003/38, Swiss Federal Institute of Technology (EPFL), 2003.
• 8: B. P. Gerkey and M. J. Matarić. A formal analysis and taxonomy of task allocation in multi-robot systems. International Journal of Robotics Research, 23(9):939--954, 2004.
• 9: Rachel Greenstadt , Jonathan P. Pearce , Milind Tambe, Analysis of privacy loss in distributed constraint optimization, Proceedings of the 21st national conference on Artificial intelligence, p.647-653, July 16-20, 2006, Boston, Massachusetts
• 10: K. Hirayama. A distributed solution protocol that computes an upper bound for the generalized mutual assignment problem. In Proceedings of the 7th International Workshop on Distributed Constraint Reasoning, pages 102--116, 2006.
• 11: Katsutoshi Hirayama, A new approach to distributed task assignment using Lagrangian decomposition and distributed constraint satisfaction, Proceedings of the 21st national conference on Artificial intelligence, p.660-665, July 16-20, 2006, Boston, Massachusetts
• 12: K. Hirayama. An α-approximation protocol for the generalized mutual assignment problem. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-2007), pages 744--749, 2007.
• 13: E. Kutanoglu and S. D. Wu. On combinatorial auction and Lagrangian relaxation for distributed resource scheduling. IIE Transactions, 31(9):813--826, 1999.
• 14: L. S. Lasdon. Optimization theory for large systems. Dover, 2002.
• 15: Roger Mailler , Victor Lesser, Solving Distributed Constraint Optimization Problems Using Cooperative Mediation, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.438-445, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.249]
• 16: T. Matsui, M. Silaghi, K. Hirayama, M. Yokoo, and H. Matsuo. Resource constrained distributed constraint optimization with virtual variables. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI-2008), pages 120--125, 2008.
• 17: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, An asynchronous complete method for distributed constraint optimization, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860602]
• 18: R. M. Nauss. The generalized assignment problem. In J. K. Karlof, editor, Integer Programming: Theory and Practice, pages 39--55. CRC Press, 2006.
• 19: T. Nishi, M. Konishi, and S. Hasebe. An autonomous decentralized supply chain planning system for multi-stage production processes. Journal of Intelligent Manufacturing, 16:259--275, 2005.
• 20: I. H. Osman. Heuristics for the generalised assignment problem: simulated annealing and tabu search approaches. OR Spektrum, 17:211--225, 1995.
• 21: A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-2005), pages 266--271, 2005.
• 22: Marius C. Silaghi , Makoto Yokoo, Nogood based asynchronous distributed optimization (ADOPT ng), Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160894]
• 23: M. Yagiura and T. Ibaraki. Generalized assignment problem. In T. F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics, Computer&Information Science Series. Chapman&Hall/CRC, 2006.
• 24: William Yeoh , Ariel Felner , Sven Koenig, BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 25: R. Zivan. Anytime local search for distributed constraint optimization. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI-2008), pages 393--398, 2008.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

General Terms:
Algorithms

Keywords:
Lagrangian relaxation, distributed combinatorial optimization, generalized assignment, spanning tree, subgradient optimization, synchronization