Tecnologia de subastas para la formacion automatizada de cadenas de suministro
RB-LBP: Scaling Up Decentralized supply chain formation
Publication Type:
Conference PaperSource:
5th International Workshop on Optimization in Multi-Agent Systems @AAMAS (OPTMAS), Valencia (2012)Abstract:
Supply Chain Formation (SCF) is the process of determining the participants in a supply chain, who will exchange what with whom, and the terms of the exchanges. Decentralized SCF appears as a highly intricate task because agents only possess local information and have limited knowledge about the capabilities of other agents. The decentralized SCF problem has been recently cast as an optimization problem that can be efficiently approximated using max-sum loopy belief propagation. Along this direction, in this paper we propose a novel encoding of the problem into a binary factor graph (containing only binary variables) as well as an alternative algorithm. We empirically show that our approach allows to significantly increase scalability, hence allowing to form supply chains in market scenarios with a large number of participants and high competition.
A scalable Message-Passing Algorithm for Supply Chain Formation
Publication Type:
Conference PaperSource:
AAAI Conf. on Artificial Intelligence, Toronto, Canada (2012)URL:
http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/5005/5480Abstract:
Supply Chain Formation (SCF) is the process of determining the participants in a supply chain, who will exchange what with whom, and the terms of the exchanges. Decentralized SCF appears as a highly intricate task because agents only possess local information and have limited knowledge about the capabilities of other agents. The decentralized SCF problem has been recently cast as an optimization problem that can be efficiently approximated using max-sum loopy belief propagation. Along this direction, in this paper we propose a novel encoding of the problem into a binary factor graph (containing only binary variables) as well as an alternative algorithm. We empirically show that our approach allows to significantly increase scalability, hence allowing to form supply chains in market scenarios with a large number of participants and high competition.
PDFFile:
Scalable decentralized supply chain formation through binarized belief propagation
Publication Type:
Conference PaperSource:
International Joint Conference on Autonomous Agents and Multi-agent Systems, Valencia (2012)URL:
http://www.ifaamas.org/Proceedings/aamas2012/papers/Z2_13.pdfAbstract:
Supply Chain Formation (SCF) is the process of determining the participants in a supply chain, who will exchange what with whom, and the terms of the exchanges. Decentralized SCF appears as a highly intricate task because agents only possess local information, have limited knowledge about the capabilities of other agents, and prefer to preserve privacy. Very recently, the decentralized SCF problem has been cast as an optimization problem that can be e ciently approximated using max-sum loopy belief propagation. Unfortunately, the memory and communication requirements of this approach largely hinder its scalability. This paper presents a novel encoding of the problem into a binary factor graph (containing only binary variables) along with an alternative algorithm. These allow to scale up to form supply chains in markets with higher degrees of competition.
Divide-and-Coordinate by Egalitarian Utilities: turning DCOPs into egalitarian worlds
Egalitarian Utilities Divide-and-Coordinate: Stop arguing about decisions, let's share rewards!
Divide and Coordinate: solving DCOPs by agreement
Publication Type:
Conference PaperSource:
Proc. of the 9th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'10), IFAAMAS, Canada, p.149-156 (2010)Keywords:
DCOP; Multi-agent Optimization; Divide and Coordinate; DaCSA; approximate algorithms; boundsAbstract:
In this paper we investigate an approach to provide approximate, anytime algorithms for DCOPs that can provide quality guaran- tees. At this aim, we propose the divide-and-coordinate (DaC) ap- proach. Such approach amounts to solving a DCOP by iterating (1) a divide stage in which agents divide the DCOP into a set of simpler local subproblems and solve them; and (2) a coordinate stage in which agents exchange local information that brings them closer to an agreement. Next, we formulate a novel algorithm, the Divide and Coordinate Subgradient Algorithm (DaCSA), a computational realization of DaC based on Lagrangian decompositions and the dual subgradient method. By relying on the DaC approach, DaCSA provides bounded approximate solutions. We empirically evaluate DaCSA showing that it is competitive with other state-of- the-art DCOP approximate algorithms and can eventually outperform them while providing useful quality guarantees.
