Decentralised supply chain formation: a belief propagation-based approach

Michael Winsper, Maria Chli

Research output: Chapter in Book/Published conference outputConference publication


Decentralised supply chain formation involves determining the set of producers within a network able to supply goods to one or more consumers at the lowest cost. This problem is frequently tackled using auctions and negotiations. In this paper we show how it can be cast as an optimisation of a pairwise cost function. Optimising this class of functions is NP-hard but good approximations to the global minimum can be obtained using Loopy Belief Propagation (LBP). Here we detail a LBP-based approach to the supply chain formation problem, involving decentralised message-passing between potential participants. Our approach is evaluated against a well-known double-auction method and an optimal centralised technique, showing several improvements: it obtains better solutions for most networks that admit a competitive equilibrium Competitive equilibrium as defined in [3] is used as a means of classifying results on certain networks to allow for minor inefficiencies in their auction protocol and agent bidding strategies. while also solving problems where no competitive equilibrium exists, for which the double-auction method frequently produces inefficient solutions.
Original languageEnglish
Title of host publicationFrontiers in artificial intelligence and applications
EditorsHelder Coelho, Rudi Studer, Michael Wooldridge
Place of PublicationAmsterdam (NL)
Number of pages2
ISBN (Print)978-1-60750-605-8
Publication statusPublished - 2010
Event19th European Conference on Artificial Intelligence - Lisbon, Portugal
Duration: 16 Aug 201020 Aug 2010


Conference19th European Conference on Artificial Intelligence
Abbreviated titleECAI 2010
Internet address


Dive into the research topics of 'Decentralised supply chain formation: a belief propagation-based approach'. Together they form a unique fingerprint.

Cite this