Decentralised supply chain formation: a belief propagation-based approach

Michael Winsper, Maria Chli

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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)
PublisherIOS
Pages1125-1126
Number of pages2
Volume215
ISBN (Print)978-1-60750-605-8
DOIs
Publication statusPublished - 2010
Event19th European Conference on Artificial Intelligence - Lisbon, Portugal
Duration: 16 Aug 201020 Aug 2010
http://ecai2010.appia.pt/

Conference

Conference19th European Conference on Artificial Intelligence
Abbreviated titleECAI 2010
CountryPortugal
CityLisbon
Period16/08/1020/08/10
Internet address

Fingerprint

Propagation
Decentralized supply chain
Competitive equilibrium
Auctions
Double auction
Bidding strategy
Costs
Approximation
NP-hard
Problem solving
Cost function
Supply chain
Inefficiency

Cite this

Winsper, M., & Chli, M. (2010). Decentralised supply chain formation: a belief propagation-based approach. In H. Coelho, R. Studer, & M. Wooldridge (Eds.), Frontiers in artificial intelligence and applications (Vol. 215, pp. 1125-1126). Amsterdam (NL): IOS. https://doi.org/10.3233/978-1-60750-606-5-1125
Winsper, Michael ; Chli, Maria. / Decentralised supply chain formation : a belief propagation-based approach. Frontiers in artificial intelligence and applications. editor / Helder Coelho ; Rudi Studer ; Michael Wooldridge. Vol. 215 Amsterdam (NL) : IOS, 2010. pp. 1125-1126
@inproceedings{71fed4f35a814fe189a3ccc15d6bb9ea,
title = "Decentralised supply chain formation: a belief propagation-based approach",
abstract = "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.",
author = "Michael Winsper and Maria Chli",
year = "2010",
doi = "10.3233/978-1-60750-606-5-1125",
language = "English",
isbn = "978-1-60750-605-8",
volume = "215",
pages = "1125--1126",
editor = "Helder Coelho and Rudi Studer and Michael Wooldridge",
booktitle = "Frontiers in artificial intelligence and applications",
publisher = "IOS",
address = "Netherlands",

}

Winsper, M & Chli, M 2010, Decentralised supply chain formation: a belief propagation-based approach. in H Coelho, R Studer & M Wooldridge (eds), Frontiers in artificial intelligence and applications. vol. 215, IOS, Amsterdam (NL), pp. 1125-1126, 19th European Conference on Artificial Intelligence, Lisbon, Portugal, 16/08/10. https://doi.org/10.3233/978-1-60750-606-5-1125

Decentralised supply chain formation : a belief propagation-based approach. / Winsper, Michael; Chli, Maria.

Frontiers in artificial intelligence and applications. ed. / Helder Coelho; Rudi Studer; Michael Wooldridge. Vol. 215 Amsterdam (NL) : IOS, 2010. p. 1125-1126.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Decentralised supply chain formation

T2 - a belief propagation-based approach

AU - Winsper, Michael

AU - Chli, Maria

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77956055148&partnerID=8YFLogxK

UR - http://www.booksonline.iospress.nl/Content/View.aspx?piid=17971

U2 - 10.3233/978-1-60750-606-5-1125

DO - 10.3233/978-1-60750-606-5-1125

M3 - Conference contribution

AN - SCOPUS:77956055148

SN - 978-1-60750-605-8

VL - 215

SP - 1125

EP - 1126

BT - Frontiers in artificial intelligence and applications

A2 - Coelho, Helder

A2 - Studer, Rudi

A2 - Wooldridge, Michael

PB - IOS

CY - Amsterdam (NL)

ER -

Winsper M, Chli M. Decentralised supply chain formation: a belief propagation-based approach. In Coelho H, Studer R, Wooldridge M, editors, Frontiers in artificial intelligence and applications. Vol. 215. Amsterdam (NL): IOS. 2010. p. 1125-1126 https://doi.org/10.3233/978-1-60750-606-5-1125