MARKET-BASED DISTRIBUTED OPTIMIZATION APPROACHES FOR THREE CLASSES OF RESOURCE ALLOCATION PROBLEMS

摘要

Allocation of resources to tasks is a challenging problem especially when the number of tasks or resources is large. This is primarily due to the fact that a large number of resources to be allocated result in an optimization problem that involves a large number of decision variables. Most of the optimization algorithms suffer from the curse of dimensionality that raises the issue of scalability of algorithms for large-scale problems. One of the techniques to overcome this issue that has been considered in literature is to carry out the optimization in a hierarchical, distributed, or decentralized manner. In particular, distributed resource allocation is a promising paradigm of special relevance to many engineered systems which have emerged to be complex networked systems. In this paper, the market-based distributed optimization technique is presented and its application on three different classes of problems is shown. The market-based resource allocation is inspired by concepts from the economic market, where resources are allocated to activities through the process of competitive buying and selling. The different classes of problems used in this paper include: (i) allocation of indivisible resources, (ii) allocation of divisible resources, and (iii) non-linear task allocation problems. The paper presents different market mechanisms and demonstrates how those mechanisms are used to solve the three different classes of problems. The proposed market-based distributed optimization techniques have been evaluated with the help of extensive numerical studies, and the comparative results obtained from centralized methods are presented in this paper.