Integer Programming
Contents
10. Integer Programming¶
This is an example of solving a integer resource allocation problem with pulp library.
import pulp
from pulp import LpProblem, LpVariable, lpSum, LpMaximize, LpStatus, value
import pandas as pd
import numpy as np
import IPython
from IPython.display import display
print(pulp.__version__)
print(pd.__version__)
print(IPython.__version__)
# dicionario para cada plantonista
plantonista = {
'andre' : {"s1" : 0, "s2" : 2, "s3" : 3, "s4" : 5, "s5" : 4},
'kiyota' : {"s1" : 3, "s2" : 1, "s3" : 0, "s4" : 4, "s5" : 2},
'fabio' : {"s1" : 3, "s2" : 2, "s3" : 1, "s4" : 4, "s5" : 5},
'natalia' : {"s1" : 0, "s2" : 2, "s3" : 0, "s4" : 4, "s5" : 5},
'junior' : {"s1" : 4, "s2" : 1, "s3" : 2, "s4" : 5, "s5" : 3},
'manu' : {"s1" : 5, "s2" : 3, "s3" : 1, "s4" : 4, "s5" : 2},
"sarda" : {"s1" : 4, "s2" : 2, "s3" : 5, "s4" : 1, "s5" : 3},
"corbalan": {"s1" : 1, "s2" : 3, "s3" : 0, "s4" : 5, "s5" : 4},
"leo" : {"s1" : 1, "s2" : 2, "s3" : 4, "s4" : 3, "s5" : 5},
"nefs" : {"s1" : 2, "s2" : 4, "s3" : 1, "s4" : 5, "s5" : 0},
"victor" : {"s1" : 1, "s2" : 2, "s3" : 3, "s4" : 4, "s5" : 5},
"denis" : {"s1" : 5, "s2" : 0, "s3" : 2, "s4" : 1, "s5" : 4},
"juliane" : {"s1" : 0, "s2" : 3, "s3" : 1, "s4" : 5, "s5" : 4},
"izumi" : {"s1" : 0, "s2" : 4, "s3" : 2, "s4" : 5, "s5" : 1},
}
# lista de semanas
semana = list(list(plantonista.items())[0][1].keys())
# lista de plantonistas
plantonistas = list(plantonista.keys())
# cria a variável prob
prob = LpProblem("Calendario-plantonistas", LpMaximize)
week_vars = [LpVariable.dicts(f"{plant}",
semana,lowBound=0,
upBound=1,cat='Integer') for plant in plantonista]
# função objetivo
prob +=lpSum([[plantonista[i][j]*week_vars[l][j] for l,i in enumerate(plantonistas)] for j in semana]), "Satisfação total dos plantonistas"
# restrição para nenhum plantonista ficar mais de duas vezes no periodo
for i in range(len(plantonistas)):
prob += lpSum([week_vars[i][j] for j in semana]) <= 2, f"max_per_plantonista {plantonistas[i]}"
# restrição para nenhum plantonista ficar por semanas seguidas
for i in range(len(plantonistas)):
for s in range(len(semana)):
if s+1 == len(semana):
break
else:
prob += lpSum([week_vars[i][semana[s]]+week_vars[i][semana[s+1]]]) <= 1, f"non_sequence_week_plantonista {plantonistas[i]}_seq{s+1}"
# restrição para que não haja dois plantonistas por semana
for j in semana:
prob += lpSum([week_vars[i][j] for i in range(len(plantonistas))]) <=2, f"max_plantonistas_week_{j}"
# restrição para que tenha pelo menos um plantonista em todas as semanas
for j in semana:
prob += lpSum([week_vars[i][j] for i in range(len(plantonistas))]) >=1, f"min_plantonistas_week_{j}"
10.1. Lista de restrições¶
for items in prob.constraints.items():
print(f"{items[0] :<38}: {items[1]}")
10.2. Solução e resultados¶
# chama o solver
prob.solve()
# cria um arquivo csv com o calendario final
X_vars = {k:[] for k in plantonistas}
semanas = [f"Semana_{i}" for i in range(len(semana))]
for v in prob.variables():
X_vars[v.name.split("_")[0]] +=[v.varValue]
result_df = pd.DataFrame(X_vars,index=semanas).transpose().astype(int)
result_df['Total_do_plantonista'] = result_df.sum(axis=1)
10.3. logs¶
print("Status:", LpStatus[prob.status])
print("Satisfação da galera = ", value(prob.objective),"\n")
print("Número de plantonistas em cada semana:")
display(result_df.sum(axis=0))
print("Disponibilidade inicial dos plantonistas:")
disponibilidades = pd.DataFrame(plantonista).T
disponibilidades.columns = semanas
disponibilidades.head(14)
X = pd.DataFrame(X_vars,index=semanas).transpose().astype(int)
for s in X.columns:
print(f"Selecionados na {s}: {' e '.join(X[X[s]!=0].index.tolist())}")
print(f"Plantonistas não selecionados: {', '.join(result_df[result_df['Total_do_plantonista']==0].index.tolist())}")
print(f"Plantonistas selecionados 1x : {', '.join(result_df[result_df['Total_do_plantonista']==1].index.tolist())}")
print(f"Plantonistas selecionados 2x : {', '.join(result_df[result_df['Total_do_plantonista']==2].index.tolist())}")
disponibilidades.loc[["andre","izumi"]]
result_df.loc[["andre","izumi"]]
print("Semanas mais desejadas")
display(disponibilidades.sum(axis=0).sort_values(ascending=False))
result_df_ = result_df.drop(result_df.columns[-1],axis=1)
result_df_.replace(1,"SELECIONADO",inplace=True)
print("Calendário final:")
display(result_df_.head(14))