Python_Pulp_GRACCA.txt

"""
This is a Python Implementation for GRACCA (GRA with Conflicting or Cooperative Agents) using Pulp,
i.e., Problem 7 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.
"""

import pulp
import time

class GRACCA:
    def __init__(self, nagent, nrole, QM, RA, ACC):
        self.m = nagent
        self.n = nrole
        self.L = RA
        self.Q = QM
        self.ACC = ACC

    @property
    def resolve(self):
        Agents = range(self.m)
        Roles = range(self.n)
        mn=self.m*self.n
        mm=self.m*self.m
        mmn=self.m*self.m*self.n
        gra = pulp.LpProblem("GRA Model", pulp.LpMaximize)
        Assignments = [i*n+j for i in Agents for j in Roles]
        Assignments1= [(j * mm) + (i2 * self.m) + i1 for i1 in Agents for i2 in Agents for j in Roles]

        vars = pulp.LpVariable.dicts("Assignment", range (mn), 0, 1, pulp.LpInteger)
        vars1 = pulp.LpVariable.dicts("Assignment1", range (mmn), 0, 1, pulp.LpInteger)
        # The objective function is added to 'prob' first
        gra += (
            pulp.lpSum([vars[index] * self.Q[int(index / self.n)][index % self.n] for index in Assignments] +
            [vars1[index1] * self.ACC[int((index1-int(index1/mm)*mm) % self.m)][int((index1-int(index1/mm)*mm) / self.m)] for index1 in Assignments1]),
            "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]) <= 1,
                "each_agent%s" % i,
            )
        for i1 in Agents:
            for i2 in Agents:
                    for j in Roles:
                        gra += (
                            vars1[(j * m * m) + (i2 * m) + i1] * 2 <= pulp.lpSum([vars[i1*n+j] + vars[i2*n+j]]),
                            "agent conflict1_{}_{}_{}".format(i1, i2, j),
                        )
                        gra += (
                            pulp.lpSum([vars[i1 * n + j] + vars[i2 * n + j]])<=vars1[(j * m * m) + (i2 * m) + i1] + 1,
                            "agent conflict2_{}_{}_{}".format(i1, i2, j),
                        )
        gra.solve()
        T = [None] * mn
        T1 = [None] * mmn
        for v in gra.variables():
            #            print(v.name, " ", v.varValue)
            if v.name[0:11] == "Assignment_":
                ind = int(v.name[11:len(v.name)])
                if abs(1 - v.varValue) < 0.0001:
                    T[ind] = 1
                else:
                    T[ind] = 0
            if v.name[0:11] == "Assignment1":
                ind = int(v.name[12:len(v.name)])
                if abs(1 - v.varValue) < 0.0001:
                    T1[ind] = 1
                else:
                    T1[ind] = 0
        return (T, T1)

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, 1, 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]]
ACC = [
    [0.0, 0.3, 0.2, -0.2, 0.0, 0.0],
    [0.3, 0.0, -0.5, 0.0,  0.0, 0.0],
    [0.0, 0.3, 0.2, -0.2, 0.0, 0.0],
    [0.3, 0.0, -0.5, 0.0,  0.0, 0.0],
    [0.2, -0.5, 0.0, 0.3, 0.0, 0.0],
    [-0.2, 0, 0.3, 0.0, 0.0, 0.0]]
t1 = int(round(time.time() * 1000))
PulpGRACCA = GRACCA(m, n, Q, L, ACC)
(T, T1) = PulpGRACCA.resolve
t2 = int(round(time.time() * 1000))
diff1 = t2 - t1
print("Q=")
printDMatrix(Q, m, n)
print("ACC=")
printIMatrix(ACC, n, n)
mat = []
while T != []:
    mat.append(T[:n])
    T = T[n:]
print("T=")
printIMatrix(mat, m,n)
print("L=", L)
v1 = 0
for i in range(m):
        for j in range(n):
            v1+= Q[i][j] * mat[i][j]
for i1 in range(m):
    for i2 in range(m):
        for j in range(n):
                v1+= ACC[i1][i2] * T1[(j * m * m) + (i2 * m) + i1]
print("Total GRACCA =", "{:.2f}".format(v1), " ", "Time = ", diff1, "ms")
del PulpGRACCA