# Determine the start time
StartTime = time.process_time()
# Define our Linear Program
Solver = pywraplp.Solver('Solver', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
# Define the Preference Coefficient P[i,j], for Residence Assistant i working in Shift j
n=18
m=33
P = np.zeros(shape=(n, m), dtype=int)
blocks = ["RA 1", "RA 2", "RA 3", "RA 4", "RA 5", "RA 6", "RA 7", "RA 8", "RA 9",
"RA 10", "RA 11", "RA 12","RA 13", "RA 14", "RA 15", "RA 16", "RA 17", "RA 18"]
for j in range(m):
for i in range(n):
P[i,j] = InputData[blocks[i]][j]
# Define the binary variable X[i,j], which will equal 1 if Residence Assistant i is assigned to Shift j
X = {}
for i in range(n):
for j in range(m):
X[i,j] = Solver.IntVar(0, 1, 'X[%d, %d]' % (i,j))
# Set up our Happiness Function, which maximizes the total number of Happiness Points
HappinessFunction = Solver.Sum(P[i,j]*X[i,j] for i in range(n) for j in range(m))
Solver.Maximize(HappinessFunction)
# Include our first constraint: Nobody works more than one block break or special weekend
for i in range(n):
Solver.Add(Solver.Sum([X[i,j] for j in [8,16,24,26,30,32]]) <= 1)
# Include our second constraint: Each week must be covered by exactly two RAs
for j in range(m):
Solver.Add(Solver.Sum([X[i,j] for i in range(n)]) == 2)
# Include our third constraint: Each RA must work at least 6 points and at most 7 points
for i in range(n):
Solver.Add(Solver.Sum([X[i,j] for j in range(m)]) + Solver.Sum([X[i,2*j] for j in range(16)])
+ Solver.Sum([X[i,j] for j in [8,16,24,26,30,32] ]) >= 6)
for i in range(n):
Solver.Add(Solver.Sum([X[i,j] for j in range(m)]) + Solver.Sum([X[i,2*j] for j in range(16)])
+ Solver.Sum([X[i,j] for j in [8,16,24,26,30,32] ]) <= 7)
# Solve the Integer Linear program
Output = Solver.Solve()
TotalPoints = round(Solver.Objective().Value())
# Determine the total time of running the program.
TotalTime = round(time.process_time() - StartTime, 4)
# Output one of the possible optimal solutions.
print("Python returns a solution with", TotalPoints, "Total Happiness Points in", TotalTime, "seconds")
pd.options.mode.chained_assignment = None
OutputData = InputData.copy()
for i in range(n):
for j in range(m):
if X[i,j].solution_value()==0:
OutputData[blocks[i]][j] = ""
OutputData