检索结果-内蒙古大学图书馆

Using the max-sum algorithm for Supply Chain Emergence in Dynamic Multiunit Environments

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2015年第3期45卷 422-435页

作者： Chli, Maria Winsper, Michael Aston Univ Dept Comp Sci Birmingham B4 7ET W Midlands England

Supply chain formation (SCF) is the process of determining the set of participants and exchange relationships within a network with the goal of setting up a supply chain that meets some predefined social objective. Many proposed solutions for the SCF problem rely on centralized computation, which presents a single point of failure and can also lead to problems with scalability. Decentralized techniques that aid supply chain emergence offer a more robust and scalable approach by allowing participants to deliberate between themselves about the structure of the optimal supply chain. Current decentralized supply chain emergence mechanisms are only able to deal with simplistic scenarios in which goods are produced and traded in single units only and without taking into account production capacities or input-output ratios other than 1: 1. In this paper, we demonstrate the performance of a graphical inference technique, max-sum loopy belief propagation (LBP), in a complex multiunit unit supply chain emergence scenario which models additional constraints such as production capacities and input-to-output ratios. We also provide results demonstrating the performance of LBP in dynamic environments, where the properties and composition of participants are altered as the algorithm is running. Our results suggest that max-sum LBP produces consistently strong solutions on a variety of network structures in a multiunit problem scenario, and that performance tends not to be affected by on-the-fly changes to the properties or composition of participants.

关键词： max-sum algorithm mechanism design supply chain formation (SCF)

来源：评论

学校读者我要写书评

暂无评论

Bounded approximate decentralised coordination via the max-sum algorithm

引用

ARTIFICIAL INTELLIGENCE 2011年第2期175卷 730-759页

作者： Rogers, A. Farinelli, A. Stranders, R. Jennings, N. R. Univ Southampton Sch Elect & Comp Sci Southampton Hants England Univ Verona Dept Comp Sci I-37100 Verona Italy

In this paper we propose a novel approach to decentralised coordination, that is able to efficiently compute solutions with a guaranteed approximation ratio. Our approach is based on a factor graph representation of the constraint network. It builds a tree structure by eliminating dependencies between the functions and variables within the factor graph that have the least impact on solution quality. It then uses the max-sum algorithm to optimally solve the resulting tree structured constraint network, and provides a bounded approximation specific to the particular problem instance. In addition, we present two generic pruning techniques to reduce the amount of computation that agents must perform when using the max-sum algorithm. When this is combined with the above mentioned approximation algorithm, the agents are able to solve decentralised coordination problems that have very large action spaces with a low computation and communication overhead. We empirically evaluate our approach in a mobile sensor domain, where mobile agents are used to monitor and predict the state of spatial phenomena (e.g., temperature or gas concentration). Such sensors need to coordinate their movements with their direct neighbours to maximise the collective information gain, while predicting measurements at unobserved locations. When applied in this domain, our approach is able to provide solutions which are guaranteed to be within 2% of the optimal solution. Moreover, the two pruning techniques are extremely effective in decreasing the computational effort of each agent by reducing the size of the search space by up to 92%. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Decentralised coordination max-sum algorithm DCOP

来源：评论

学校读者我要写书评

暂无评论

Remote Radio Head Activation and User Association in Dense C-RANs

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2020年第10期69卷 12216-12228页

作者： Wu, Zhikun Fei, Zesong Zheng, Zhong Li, Bin Han, Zhu Beijing Inst Technol Sch Informat & Elect Beijing 100081 Peoples R China Guilin Univ Elect Technol Guangxi Wireless Broadband Commun & Signal Proc K Guilin 541004 Peoples R China Nanjing Univ Informat Sci & Technol Sch Comp & Software Nanjing 210044 Peoples R China Univ Houston Dept Elect & Comp Engn Houston TX 77004 USA

Cloud radio access networks (C-RANs) is a promising technology for improving the performance of future mobile networks. In this paper, we focus on the joint remote radio head (RRH) activation and user association problem in dense C-RANs. Considering that a certain required minimum data rate may not be satisfied universally for all users in some situation, we aim to first maximize the number of users whose minimum data rate constraints can be guaranteed, and then maximize the system profit, which is a combination of the system throughput and the total power consumption. Due to the NP-hard feature of the problem, the conventional algorithms are impractical when the network size is large due to large computational complexity. Therefore, we adopt the max-sum algorithm to efficiently solve the joint RRH activation and user association problem, which can be implemented efficiently in a distributed manner. The signaling overhead of the max-sum algorithm can be reduced further by simplifying message updating rules and by shortening messages exchanged between nodes. Considering the fact that the high density of RRH deployment may hinder the convergence rate of the max-sum algorithm, we also propose a simplified algorithm by decomposing the original problem into two sub-problems, and each can be solved by the max-sum algorithm individually. Simulation results prove the efficiencies of the proposed algorithms.

关键词： Cloud radio access networks association activation distributed max-sum algorithm

来源：评论

学校读者我要写书评

暂无评论

On implementation of min-sum algorithm and its modifications for decoding low-density parity-check (LDPC) codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2005年第4期53卷 549-554页

作者： Zhao, JG Zarkeshvari, F Banihashemi, AH Carleton Univ BCWS Ottawa ON K1S 5B6 Canada Carleton Univ Dept Syst & Comp Engn Ottawa ON K1S 5B6 Canada

The effects of clipping and quantization on the performance of the min-sum algorithm for the decoding of low-density parity-check (LDPC) codes at short and intermediate block lengths are studied. It is shown that in many cases, only four quantization bits suffice to obtain close to ideal performance over a wide range of signal-to-noise ratios. Moreover, we propose modifications to the min-sum algorithm that improve the performance by a few tenths of a decibel with just a small increase in decoding complexity. A quantized version of these modified algorithms is also studied. It is shown that, when optimized, modified quantized min-sum algorithms perform very close to, and in some cases even slightly outperform, the ideal belief-propagation algorithm at observed error rates.

关键词： clipping iterative decoding algorithms low-density parity-check (LDPC) codes max-product algorithm max-sum algorithm min-sum algorithm modified min-sum algorithms quantization

来源：评论

学校读者我要写书评

暂无评论

Hybrid Approximate Message Passing

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2017年第17期65卷 4577-4592页

作者： Rangan, Sundeep Fletcher, Alyson K. Goyal, Vivek K. Byrne, Evan Schniter, Philip NYU Dept Elect & Comp Engn Brooklyn NY 11201 USA Univ Calif Los Angeles Dept Stat Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90095 USA Boston Univ Dept Elect & Comp Engn Boston MA 02215 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA

Gaussian and quadratic approximations of message passing algorithms on graphs have attracted considerable recent attention due to their computational simplicity, analytic tractability, and wide applicability in optimization and statistical inference problems. This paper presents a systematic framework for incorporating such approximate message passing (AMP) methods in general graphical models. The key concept is a partition of dependencies of a general graphical model into strong and weak edges, with the weak edges representing small, linearizable couplings of variables. AMP approximations based on the central limit theorem can be readily applied to aggregates of many weak edges and integrated with standard message passing updates on the strong edges. The resulting algorithm, which we call hybrid generalized approximate message passing (HyGAMP), can yield significantly simpler implementations of sum-product and max-sum loopy belief propagation. By varying the partition of strong and weak edges, a performance-complexity tradeoff can be achieved. Group sparsity and multinomial logistic regression problems are studied as examples of the proposed methodology.

关键词： Approximate message passing belief propagation sum-product algorithm max-sum algorithm group sparsity multinomial logistic regression

来源：评论

学校读者我要写书评

暂无评论

Toward Optimal Remote Radio Head Activation, User Association, and Power Allocation in C-RANs Using Benders Decomposition and ADMM

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2019年第7期67卷 5008-5023页

作者： Wu, Zhikun Fei, Zesong Yu, Ye Han, Zhu Beijing Inst Technol Sch Informat & Elect Beijing 100081 Peoples R China Univ Houston Dept Elect & Comp Engn Houston TX 77004 USA

To satisfy the rapidly growing demands of wireless communications, new structures have been proposed for the fifth-generation (5G) mobile communication networks, such as cloud radio access networks (C-RANs), which have advantages including high energy efficiency, large network capacity, and high flexibility. This paper concentrates on the problem of remote radio head (RRH) activation, user association, and power allocation in C-RANs. To tackle the problem with l(0) norm, we transform it into a mixed-integer nonlinear programming (MINLP) problem. Instead of solving it by centralized solvers, we propose a novel algorithm based on Benders decomposition, which can obtain the optimal solution of the MINLP problem. To solve the primal problem in Benders decomposition efficiently, we adopt the alternating direction method of multipliers (ADMM) to achieve a parallel implementation. To further reduce the complexity of solving the MINLP problem, a distributed two-stage iterative algorithm combining the ADMM and the max-sum algorithm is also proposed. The simulation results demonstrate that the first proposed algorithm can obtain the optimal solution, and the second proposed algorithm outperforms conventional algorithms significantly.

关键词： Cloud radio access networks user association power allocation benders decomposition alternating direction method of multipliers max-sum algorithm

来源：评论

学校读者我要写书评

暂无评论

Identification of Vulnerable Lines in Smart Grid Systems Based on Affinity Propagation Clustering

引用

IEEE INTERNET OF THINGS JOURNAL 2019年第3期6卷 5163-5171页

作者： Gao, Qinghe Wang, Yawei Cheng, Xiuzhen Yu, Jiguo Chen, Xi Jing, Tao George Washington Univ Dept Comp Sci Washington DC 20052 USA Beijing Jiaotong Univ Sch Elect & Informat Engn Beijing 100044 Peoples R China Qilu Univ Technol Sch Comp Sci & Technol Shandong Acad Sci Jinan 250353 Shandong Peoples R China Natl Supercomp Ctr Jinan Shandong Comp Sci Ctr Jinan 250014 Shandong Peoples R China Qufu Normal Univ Sch Informat Sci & Engn Rizhao 276826 Peoples R China GEIRI North Amer Dev & Planning Dept San Jose CA 95134 USA

In smart grid systems, vulnerable lines may lead to cascading failures which can cause large-scale blackouts. Successfully detecting vulnerable lines can increase the stability of the smart grid systems and reduce the risk of cascading failures. By modeling a smart grid system into a directed graph, we investigate the problem of vulnerable line identification from a clustering perspective. By jointly considering the topological parameters and the electrical properties, we propose an affinity propagation-based bus clustering algorithm to classify buses into clusters, where the center of each cluster represents the most influential bus in each partition. According to the clustering results, we design a vulnerable line identification scheme, which captures different types of potential critical lines in the smart grid system. Experiments over the IEEE-39 bus system demonstrate the effectiveness and correctness of our proposed algorithm.

关键词： Affinity propagation (AP) cascading failure factor graph machine learning max-sum algorithm smart grid

来源：评论

学校读者我要写书评

暂无评论

DECENTRALIZED SUPPLY CHAIN FORMATION USING max-sum LOOPY BELIEF PROPAGATION

引用

COMPUTATIONAL INTELLIGENCE 2013年第2期29卷 281-309页

作者： Winsper, Michael Chli, Maria Aston Univ Birmingham B4 7ET W Midlands England

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.

关键词： loopy belief propagation max-sum algorithm supply chain formation

来源：评论

学校读者我要写书评

暂无评论

Node and Link Allocation in Network Virtualization Based on Distributed Constraint Optimization

引用

JOURNAL OF NETWORK AND SYSTEMS MANAGEMENT 2018年第1期26卷 127-146页

作者： Gularte, Alexander R. Mendizabal, Odorico M. Barbosa, Raquel M. Adamatti, Diana F. Univ Fed Rio Grande Ctr Ciencias Computacionais Ave Italia S-NKm 08 Rio Grande RS Brazil

Virtual Networks (VNs) offer a flexible and economic approach to deploy customer suited networks. However, defining how resources of a physical network are used to support VNs requirements is a NP-hard problem. For this reason, heuristics have been used on mapping of virtual networks. Although heuristics do not ensure the optimal solution, they implement fast solutions and showed satisfactory results. This work presents a modeling of the node and link allocation problem using Distributed Constraint Optimization Problem (DCOP) with factor graphs, which is a formalism widely used in real distributed optimization problems. In our approach, we use the max-sum algorithm to solve the DCOP. Correctness criteria for this approach are discussed and verifications are conducted through model checking.

关键词： Distributed constraint optimization problem max-sum algorithm Virtual network embedding Resource allocation Verification Model checking

来源：评论

学校读者我要写书评

暂无评论

Robust Coordinated Reinforcement Learning for MAC Design in Sensor Networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2019年第10期37卷 2211-2224页

作者： Nisioti, Elem Thomos, Nikolaos Univ Essex Sch Comp Sci & Elect Engn Colchester CO4 3SQ Essex England

In this paper, we propose a medium access control (MAC) design method for wireless sensor networks based on decentralized coordinated reinforcement learning. Our solution maps the MAC resource allocation problem first to a factor graph, and then, based on the dependencies between sensors, transforms it into a coordination graph, on which the max-sum algorithm is employed to find the optimal transmission actions for sensors. We have theoretically analyzed the system and determined the convergence guarantees for decentralized coordinated learning in sensor networks. As part of this analysis, we derive a novel sufficient condition for the convergence of max-sum on graphs with cycles and employ it to render the learning process robust. In addition, we reduce the complexity of applying max-sum to our optimization problem by expressing coordination as a multiple knapsack problem (MKP). The complexity of the proposed solution can be, thus, bounded by the capacities of the MKP. Our simulations reveal the benefits coming from adaptivity and sensors' coordination, both inherent in the proposed learning-based MAC.

关键词： Medium access control Q-learning coordination graphs irregular repetition slotted ALOHA wireless sensor networks POMDP max-sum algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：