# -*- coding: utf-8 -*-
#programmer: Khadija HS
#date: June 2017
#name: B-C-MCT PLNE Model (Khadija.HS,2017) <---> BCMCT1.py
"""
Solve the B-C-MCTP (fixed Z & min Delta) sub-pb of 3-PSDPP (K-HS et al.,2016), where:
X: list of input tiles (tile x)
Y: list of output tiles (tile y)
Ry: requirement relation between X & Y
<---> is a List of Y list, each sub List define the input tiles required by each y
<---> rxy: incidence matrix (0-1): Input Tiles/Output Tiles (Configuration of each output tile % input tile)
<---> Ry is a list of list where Row <--- x & Column <--- y
alpha: prefetches times (uniform)
beta: computations times (uniform)
Delta: the Total completion time (to be determined)
"""
from gurobipy import *
""" Find Yx: set of output tiles y that required the input tile x """
def OuputTileTe(Ry,X):
Yx=[]
for x in X:
Yx.append(OuputTileTex(Ry,x))
return Yx
""" Find B: List Ts for x """
def OuputTileTex(Ry,x):
B=[]
for y in range(len(Ry)):
if x in Ry[y]:
B.append(y)
return B
""" Find N: Max Value of N ( <---> sum(len(Ry),y in Y)) """
def NbPrefetchTile(S):
N=0
for k in range(0,len(S)):
N += len(S[k])
return N
""" BCMCT1 - Model"""
def BCMCT1(X,Y,Z,Ry,alpha,beta):
# DET VBLES: M,N,Z1,T,K,L
M=list(range(len(Y))) # List of Computation steps
nb=NbPrefetchTile(Ry) # Number of prefetches (Big Value of N)
N=range(nb) # List of Prefetches steps
ListZ=range(Z) # List of Buffers
T=range(alpha*len(X) + beta*len(Y)) # List of Start Date times (Computation+Prefetches)
K=range(alpha) # Interval Time of a prefetch step
L=range(beta) # Interval Time of a compute step
# DET VBLES: A,T1,B,Yx
A=alpha*nb + beta*len(Y) # Big Value of Total Completion Time
T1=range(A) # List of Start Date times (Computation+Prefetches)
minLen=min([len(elt) for elt in Ry]) #1,alpha+1
B=alpha*minLen + beta*len(Y) # Value of LB2
Yx=OuputTileTe(Ry,X) # List of output tile y, for x, x in X
# MODEL
M1=Model("BCMCT1")
# CONSTANT VARIABLES
r=[[0]*len(Y) for i in range(len(X))]
for x in X:
for y in Y:
if x in Ry[Y.index(y)]:
r[x][y]=1
# DECISION VARIABLES
c,p,q,U,W,a={},{},{},{},{},{}
for y in Y:
for j in M:
c[y,j]=M1.addVar(vtype=GRB.BINARY,name="c[%s,%s]"%(y,j)) #obj=beta,
for x in X:
for t in T:
p[x,t]=M1.addVar(vtype=GRB.BINARY,name="p[%s,%s]"%(x,t)) #obj=1,
for x in X:
for t in T:
q[x,t]=M1.addVar(vtype=GRB.BINARY,name="q[%s,%s]"%(x,t)) #obj=1,
for j in M:
U[j]=M1.addVar(vtype='I',name="U_%s"%j)
W[j]=M1.addVar(obj=1,vtype='I',name="W_%s"%j)
for j in M:
a[j]=M1.addVar(vtype=GRB.BINARY,name="a[%s]"%j)
# MODEL UPDATE
M1.update()
# OBJECTIVE
Obj=W[len(M)-1]
M1.setObjective(Obj, GRB.MINIMIZE)
# CONSTRAINTS
""" (1): Computation's Assignement Constraints """
""" (a) """
for j in M:
M1.addConstr(quicksum(c[y,j] for y in Y)==1,'ComputeAssign1_%s'%j)
""" (b) """
for y in Y:
M1.addConstr(quicksum(c[y,j] for j in M)==1,'ComputeAssign2_%s'%y)
""" (2): Buffer's Constraints """
for t in T:
M1.addConstr(quicksum(p[x,t] for x in X) <= Z,'BufferNb_%s'%t)
""" 3): Computation/Prefetch's Constraints """
""" (a) """
for t in T:
M1.addConstr(quicksum(q[x,t] for x in X) <= 1,'PrefetchTileA_%s'%t)
""" (b) """
for x in X:
for t in T[1:]:
for k in K:
M1.addConstr(p[x,t] - p[x,t-1] <= q[x,t-k],'PrefetchTileB_%s_%s_%s'%(x,t,k))
""" (c) """
for y in Y:
for j in M:
for x in X:
for t in T:
M1.addConstr(3 - r[x][y] - c[y,j] - a[j] + p[x,t] >= 1, 'TileRequirement_%s_%s_%s_%s'%(y,j,x,t))
""" (5): Computation Time's Constraint """
""" (a) """
for j in M:
M1.addConstr(W[j] == U[j] + beta,'ComputeTime1_%s'%j)
""" (b) """
for j in M[1:]:
M1.addConstr(W[j-1] <= U[j],'ComputeTime2_%s'%j)
# SOLUTION
M1.__data=c,p,q,U,W,a
return M1
