[Gurobi] 구로비로 P-center 문제 풀기 with Python :: gurobipy

 

Gurobi 설치

 

https://kimhongsi.tistory.com/entry/Gurobi-%EC%B5%9C%EC%A0%81%ED%99%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8-%EA%B5%AC%EB%A1%9C%EB%B9%84-%EB%AC%B4%EB%A3%8C-%ED%95%99%EC%83%9D%ED%8C%90-%EB%8B%A4%EC%9A%B4%EB%A1%9C%EB%93%9C

[Gurobi] 최적화 프로그램 구로비 무료 학생판(academic license) 다운로드

 

준비물

구로비가 설치된 파이썬 환경

        *설치방법* : pip install gurobipy 입력

pip install gurobipy

pip install colour

 

https://kimhongsi.tistory.com/entry/Gurobi-%EA%B5%AC%EB%A1%9C%EB%B9%84%EB%A1%9C-P-median-%EB%AC%B8%EC%A0%9C-%ED%92%80%EA%B8%B0

[Gurobi] 구로비로 P-median 문제 (PMP) 풀기 with Python :: gurobipy

p-center이 아닌 p-median이 필요한 경우 이곳을 참조 

 

P-center 

 

 

 

P-center 구로비 코드

 

https://www.youtube.com/watch?v=AYe5xQOm5hU 

기본 환경 설정 

from gurobipy import *
import numpy as np
import matplotlib.pyplot as plt
#노드 개수:
N=21

#x.y 좌표:
np.random.seed(1)
X = list (np.random.random(N)*100)
Y = list(np.random.random(N)*100)

#수요량
demanda = list (np.random.randint (low=10,high=50,size=N))
#시각화:
plt.figure(figsize=(12,5))
plt.scatter(X,Y,color='blue')

for i in range(len(X)):
    plt.annotate('$d_{%d}=%d$'%(i, demanda[i]),(X[i]-0.5,Y[i]-5))
    
plt.xlabel("X axis")
plt.ylabel("Y axis")
plt.title("nodes")
plt.show()


# 세트:
nodos = [i for i in range(N)]
ubicaciones = [i for i in nodos]
arcos = [(i,j) for i in nodos for j in ubicaciones]

#최대 위치 수:
P=5

#거리 행렬:
distancia = {(i,j): np.hypot (X[i]-X[j],Y[i]-Y[j]) for i in nodos for j in ubicaciones}

 

 

 

# relative weighs:
demanda_total = sum(demanda)

w = {i:demanda[i]/demanda_total for i in nodos}
w

model = Model('P-Center')

# 결정 변수
x = model.addVars(arcos, vtype = GRB.BINARY, name = 'x')
y = model.addVars(ubicaciones, vtype = GRB.BINARY, name = 'y')
z = model.addVar(vtype = GRB.CONTINUOUS, name = 'z')

# 목적함수
model.setObjective(z, GRB.MINIMIZE)

# 제약조건
model.addConstrs (quicksum(distancia[i,j]*x[i,j]*w[i] for i in nodos) <=z for j in ubicaciones)
model.addConstrs (quicksum(x[i,j] for j in ubicaciones) == 1 for i in nodos)
model.addConstr(quicksum(y[j] for j in ubicaciones) <= P)


# M formulation:
M = len(ubicaciones)
model.addConstrs(quicksum(x[i, j] for i in nodos) - M*y[j] <=0 for j in ubicaciones)

model.optimize()

 

#arcos activos:
arcos_activos = [k for k in arcos if x[k].x > 0.9]
print(arcos_activos)

 

 

#ubicaciones Activos:
ubicaciones_activos = [k for k in ubicaciones if y[k].x > 0.9]
print(ubicaciones_activos)

 

 

#Gráficar la solución
from colour import Color
plt.figure(figsize=(12,5))
plt.scatter(X,Y,color='blue')

for n in ubicaciones_activos:
    plt.scatter (X[n],Y[n],color='green',marker='D')
    
for i in range (len(X)):
    plt.annotate('$d_{%d}=%d$'  % (i,demanda[i]),(X[i]-0.5,Y[i]-5))
    
for n in arcos_activos:
    i=n[0]
    j=n[1]
    plt.plot([X[i],X[j]],[Y[i],Y[j]])
plt.xlabel ("X axis")
plt.ylabel("Y axis")
plt.title("Nodes")
plt.show()