Python_Pulp_GMRACR.txt

"""
This is a Python Implementation for GMRACR (GMRA with Conflicting Roles) using Pulp, i.e., Problem 5 in [1].
Please cite:
[1] H. Zhu, "Group Role Assignment with Constraints (GRA+): A New Category of Assignment Problems," IEEE Trans. on Systems, Man, and Cybernetics: Systems (In Press), 2022, DOI: 10.1109/TSMC.2022.3199096.
[2] H. Zhu, E-CARGO and Role-Based Collaboration: Modeling and Solving Problems in the Complex World, Wiley-IEEE Press, NJ, USA, Dec. 2021.
[3] H. Zhu, M.C. Zhou, and R. Alkins, “Group Role Assignment via a Kuhn-Munkres Algorithm-based Solution”, IEEE Trans. on Systems, Man, and Cybernetics, Part A: Systems and Humans, vol. 42, no. 3, May 2012, pp. 739-750.
[4] H. Zhu, D. Liu, S. Zhang, Y. Zhu, L. Teng, S. Teng, “Solving the Many to Many Assignment Problem by Improving the Kuhn-Munkres Algorithm with Backtracking”, Theoretical Computer Science, vol. 618, March 2016, pp. 30-41.
[5] H. Zhu, D. Liu, S. Zhang, S. Teng, and Y. Zhu, “Solving the Group Multi-Role Assignment Problem by Improving the ILOG Approach”, IEEE Trans. on Systems, Man, and Cybernetics: Systems, vol. 47, no. 12, Dec. 2017, pp. 3418-3424.
"""

import pulp
import time

class GMRACR:
    def __init__(self, nagent, nrole, QM, RA, LA, RC):
        self.m = nagent
        self.n = nrole
        self.L = RA
        self.Q = QM
        self.LA = LA
        self.RC = RC

    @property
    def resolve(self):
        Agents = range(self.m)
        Roles = range(self.n)
        gra = pulp.LpProblem("GRA Model", pulp.LpMaximize)
        Assignments = [i*n+j for i in Agents for j in Roles]
        mn=self.m*self.n
        vars = pulp.LpVariable.dicts("Assignment", range (mn), 0, 1, pulp.LpInteger)
        # The objective function is added to 'prob' first
        gra += (
            pulp.lpSum([vars[index] * self.Q[int(index / n)][index % n] for index in Assignments]),
            "Sum_of_Assignments",
        )
        for j in Roles:
            gra += (
                pulp.lpSum([vars[i*n+j] for i in Agents]) == self.L[j],
                "each_role%s" % j,
            )
        for i in Agents:
            gra += (
                pulp.lpSum([vars[i*n+j] for j in Roles]) <= self.LA[i],
                "each_agent%s" % i,
            )
        for j1 in Roles:
            for j2 in Roles:
                if 1 == self.RC[j1][j2]:
                    for i in Agents:
                        gra += (
                            pulp.lpSum([vars[i*n+j1] + vars[i*n+j2]]) <= 1,
                            "role conflict_{}_{}_{}".format(i, j1, j2),
                        )
        gra.solve()
        T = [None]*mn
        for v in gra.variables():
            print(v.name, " ", v.varValue)
            ind = int(v.name[11:len(v.name)])
            if abs(1 - v.varValue) < 0.0001:
                T[ind]=1
            else:
                T[ind]=0
        return T

def printDMatrix(x, m, n):
        txt = "{:.2f}"
        for i in range(m):
            for j in range(n):
                print(txt.format(x[i][j]), " ", end='')
            print()
def printIMatrix(x, m, n):
        txt = "{:2}"
        for i in range(m):
            for j in range(n):
                print(txt.format(x[i][j]), " ", end='')
            print()
def sigmaL(L):
        total = 0
        for j in range(len(L)):
            total += L[j]
        return total
import copy
def getWQ(m, n, Q, W):
        maxQ = 1
        WQ = copy.deepcopy(Q)
        for i in range(m):
            for j in range(n):
                WQ[i][j] = Q[i][j] * W[j]
                if WQ[i][j] > maxQ:
                    maxQ = WQ[i][j]
        for i in range(m):
            for j in range(n):
                WQ[i][j] = WQ[i][j] / maxQ
        return WQ

m = 6
n = 4
L = [2, 3, 5, 2]
LA = [2, 3, 2, 2, 1, 2]
Q = [
    [0.96, 0.51, 0.45, 0.64],
    [0.22, 0.33, 0.68, 0.33],
    [0.35, 0.80, 0.58, 0.35],
    [0.84, 0.85, 0.86, 0.36],
    [0.96, 0.90, 0.88, 0.87],
    [0.78, 0.67, 0.80, 0.62]]
C = [
    [0, 0, 1, 0],
    [0, 0, 1, 0],
    [1, 1, 0, 0],
    [0, 0, 0, 0]]
t1 = int(round(time.time() * 1000))
PulpGMRACR = GMRACR(m, n, Q, L, LA, C)
T = PulpGMRACR.resolve
t2 = int(round(time.time() * 1000))
diff1 = t2 - t1
print("Q=")
printDMatrix(Q, m, n)
print("C=")
printIMatrix(C, n, n)
mat = []
while T != []:
    mat.append(T[:n])
    T = T[n:]
print("T=")
printIMatrix(mat, m,n)
print("L=", L)
print("LA=", LA)
v1 = 0
for i in range(m):
        for j in range(n):
            v1+= Q[i][j] * mat[i][j]
print("Total GRACAR =", "{:.2f}".format(v1), " ", "Time = ", diff1, "ms")
del PulpGMRACR