Decentralized supply chain formation using max-sum loopy belief propagation

Michael Winsper*, Maria Chli

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

Supply chain formation is the process by which a set of producers within a network determine the subset of these producers able to form a chain to supply goods to one or more consumers at the lowest cost. This problem has been tackled in a number of ways, including auctions, negotiations, and argumentation-based approaches. In this paper we show how this problem can be cast as an optimization of a pairwise cost function. Optimizing this class of energy functions is NP-hard but efficient approximations to the global minimum can be obtained using loopy belief propagation (LBP). Here we detail a max-sum LBP-based approach to the supply chain formation problem, involving decentralized message-passing between supply chain participants. Our approach is evaluated against a well-known decentralized double-auction method and an optimal centralized technique, showing several improvements on the auction method: it obtains better solutions for most network instances which allow for competitive equilibrium (Competitive equilibrium in Walsh and Wellman is a set of producer costs which permits a Pareto optimal state in which agents in the allocation receive non-negative surplus and agents not in the allocation would acquire non-positive surplus by participating in the supply chain) while also optimally solving problems where no competitive equilibrium exists, for which the double-auction method frequently produces inefficient solutions. © 2012 Wiley Periodicals, Inc.

Original languageEnglish
Pages (from-to)281-309
Number of pages29
JournalComputational Intelligence
Volume29
Issue number2
Early online date4 Jul 2012
DOIs
Publication statusPublished - May 2013

Fingerprint

Belief Propagation
Competitive Equilibrium
Supply Chain
Supply chains
Decentralized
Double Auction
Auctions
Argumentation
Message passing
Global Minimum
Message Passing
Energy Function
Cost functions
Cost Function
Costs
Pairwise
NP-complete problem
Non-negative
Subset
Optimization

Bibliographical note

Winsper, M. , & Chli, M. (2012). Decentralized supply chain formation using max-sum loopy belief propagation. Computational intelligence, 29(2), which has been published in final form at http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8640.2012.00446.x/abstract

Keywords

  • loopy belief propagation
  • max-sum algorithm
  • supply chain formation

Cite this

@article{a74d544985a4456fa337b4a46b964a3a,
title = "Decentralized supply chain formation using max-sum loopy belief propagation",
abstract = "Supply chain formation is the process by which a set of producers within a network determine the subset of these producers able to form a chain to supply goods to one or more consumers at the lowest cost. This problem has been tackled in a number of ways, including auctions, negotiations, and argumentation-based approaches. In this paper we show how this problem can be cast as an optimization of a pairwise cost function. Optimizing this class of energy functions is NP-hard but efficient approximations to the global minimum can be obtained using loopy belief propagation (LBP). Here we detail a max-sum LBP-based approach to the supply chain formation problem, involving decentralized message-passing between supply chain participants. Our approach is evaluated against a well-known decentralized double-auction method and an optimal centralized technique, showing several improvements on the auction method: it obtains better solutions for most network instances which allow for competitive equilibrium (Competitive equilibrium in Walsh and Wellman is a set of producer costs which permits a Pareto optimal state in which agents in the allocation receive non-negative surplus and agents not in the allocation would acquire non-positive surplus by participating in the supply chain) while also optimally solving problems where no competitive equilibrium exists, for which the double-auction method frequently produces inefficient solutions. {\circledC} 2012 Wiley Periodicals, Inc.",
keywords = "loopy belief propagation, max-sum algorithm, supply chain formation",
author = "Michael Winsper and Maria Chli",
note = "Winsper, M. , & Chli, M. (2012). Decentralized supply chain formation using max-sum loopy belief propagation. Computational intelligence, 29(2), which has been published in final form at http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8640.2012.00446.x/abstract",
year = "2013",
month = "5",
doi = "10.1111/j.1467-8640.2012.00446.x",
language = "English",
volume = "29",
pages = "281--309",
journal = "Computational Intelligence",
issn = "0824-7935",
publisher = "Wiley-Blackwell",
number = "2",

}

Decentralized supply chain formation using max-sum loopy belief propagation. / Winsper, Michael; Chli, Maria.

In: Computational Intelligence, Vol. 29, No. 2, 05.2013, p. 281-309.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Decentralized supply chain formation using max-sum loopy belief propagation

AU - Winsper, Michael

AU - Chli, Maria

N1 - Winsper, M. , & Chli, M. (2012). Decentralized supply chain formation using max-sum loopy belief propagation. Computational intelligence, 29(2), which has been published in final form at http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8640.2012.00446.x/abstract

PY - 2013/5

Y1 - 2013/5

N2 - Supply chain formation is the process by which a set of producers within a network determine the subset of these producers able to form a chain to supply goods to one or more consumers at the lowest cost. This problem has been tackled in a number of ways, including auctions, negotiations, and argumentation-based approaches. In this paper we show how this problem can be cast as an optimization of a pairwise cost function. Optimizing this class of energy functions is NP-hard but efficient approximations to the global minimum can be obtained using loopy belief propagation (LBP). Here we detail a max-sum LBP-based approach to the supply chain formation problem, involving decentralized message-passing between supply chain participants. Our approach is evaluated against a well-known decentralized double-auction method and an optimal centralized technique, showing several improvements on the auction method: it obtains better solutions for most network instances which allow for competitive equilibrium (Competitive equilibrium in Walsh and Wellman is a set of producer costs which permits a Pareto optimal state in which agents in the allocation receive non-negative surplus and agents not in the allocation would acquire non-positive surplus by participating in the supply chain) while also optimally solving problems where no competitive equilibrium exists, for which the double-auction method frequently produces inefficient solutions. © 2012 Wiley Periodicals, Inc.

AB - Supply chain formation is the process by which a set of producers within a network determine the subset of these producers able to form a chain to supply goods to one or more consumers at the lowest cost. This problem has been tackled in a number of ways, including auctions, negotiations, and argumentation-based approaches. In this paper we show how this problem can be cast as an optimization of a pairwise cost function. Optimizing this class of energy functions is NP-hard but efficient approximations to the global minimum can be obtained using loopy belief propagation (LBP). Here we detail a max-sum LBP-based approach to the supply chain formation problem, involving decentralized message-passing between supply chain participants. Our approach is evaluated against a well-known decentralized double-auction method and an optimal centralized technique, showing several improvements on the auction method: it obtains better solutions for most network instances which allow for competitive equilibrium (Competitive equilibrium in Walsh and Wellman is a set of producer costs which permits a Pareto optimal state in which agents in the allocation receive non-negative surplus and agents not in the allocation would acquire non-positive surplus by participating in the supply chain) while also optimally solving problems where no competitive equilibrium exists, for which the double-auction method frequently produces inefficient solutions. © 2012 Wiley Periodicals, Inc.

KW - loopy belief propagation

KW - max-sum algorithm

KW - supply chain formation

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

UR - http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8640.2012.00446.x/abstract

U2 - 10.1111/j.1467-8640.2012.00446.x

DO - 10.1111/j.1467-8640.2012.00446.x

M3 - Article

VL - 29

SP - 281

EP - 309

JO - Computational Intelligence

JF - Computational Intelligence

SN - 0824-7935

IS - 2

ER -