How to reproduce the code of the paper “Enhanced Multi‑attribute Combinative Double Auction (EMCDA) for Resource Allocation in Cloud Computing”?

Question

I am interested in the paper Enhanced Multi-attribute Combinative Double Auction (EMCDA) for Resource Allocation in Cloud Computing by Vinothiyalakshmi and Anitha (2022).

I want to implement their proposed algorithm, which is a multi-attribute combinative double auction algorithm for resource allocation in cloud computing. I am using Python as the programming language.

However, I have some difficulties in understanding and implementing the algorithm.

1. how to model the customers and providers as bidders with multiple attributes, such as price, quality, reliability, etc.
2. how to use the normalization factors to calculate the utility and price for each bid.
3. how to find the optimal matching between customers and providers using the Hungarian algorithm.

Can anyone help me with these difficulties? How can I model the bidders, calculate the utility and price, and find the optimal matching? Any suggestions or references are appreciated. Thank you very much!

Answer 1

I hope this helps for the start.

You can represent a customer or provider as a Python class. Each instance of this class will represent a specific customer or provider.

class Bidder:
    def __init__(self, price, quality, reliability):
        self.price = price
        self.quality = quality
        self.reliability = reliability

Normalization is used to bring different attributes to a comparable scale. One common approach is min-max normalization:

def normalize(value, min_value, max_value):
    return (value - min_value) / (max_value - min_value)

def calculate_utility(price, quality, reliability, weights, mins, maxs):
    norm_price = normalize(price, mins["price"], maxs["price"])
    norm_quality = normalize(quality, mins["quality"], maxs["quality"])
    norm_reliability = normalize(reliability, mins["reliability"], maxs["reliability"])
    
    utility = (weights["price"] * norm_price +
               weights["quality"] * norm_quality +
               weights["reliability"] * norm_reliability)
    return utility

The Hungarian algorithm is used for finding the optimal assignment for a bipartite graph, which is appropriate for matching customers and providers.

You can use the scipy library which has an implementation of the Hungarian algorithm.

First, you'd create a cost matrix where each entry represents the "cost" of assigning a particular customer to a provider. The size of this matrix is × n×m, where n is the number of customers and m is the number of providers.

Here row_ind and col_ind will give you the optimal matching between customers and providers.

from scipy.optimize import linear_sum_assignment

# Create a cost matrix based on negative utility 
# (since Hungarian finds minimal cost and we want to maximize utility)
cost_matrix = ...

# Find optimal assignment
row_ind, col_ind = linear_sum_assignment(cost_matrix)