作者mangomoo (阿毛)
看板Python
標題[問題] Gurobi限制式無法順利跑出最佳解
時間Sun Jan 1 15:11:47 2023
第一次寫Gurobi，遇到一些問題想請大大們幫忙看看 QQ
這個程式的目標是要最佳化撿料路徑，完整程式碼如下。
from gurobipy import*
N = [0, 1, 2, 3, 4, 5] #料件在倉庫中的location(0是depot)
S = [1] #共撿1個配置的機台
#Material list with location n
I, K = multidict({1:11, 2:12, 3:13, 4:42, 5:41})
#距離列表
R1 = {(0,1): 3, (0,2): 6, (0,3): 5, (0,4):4, (0,5): 2,\
(1,2): 3, (1,3): 4, (1,4): 3, (1,5): 3,\
(2,3): 3, (2,4): 6, (2,5): 4, (3,4): 3, (3,5): 7, (4,5): 6}
R = {}
for i,j in R1:
R[j,i]=R1[i,j]
R[i,j]=R1[i,j] #把0,1 -> 1,0
#Capacity
C = 10
#撿料的次數，可能由1~10
L = [l for l in range(1,60)]
#BOM list(要撿的1個配置中，所需要的料件如下)
BOM = {1:[11,12,13,42,41]}
#S所需數量
S, D = multidict({1:2})
#Decision variable
model = Model("Picking path")
x = {}
q = {}
u = {}
for l in L:
for i in range(len(N)+1):
q[i,l]=model.addVar(vtype="C", name="q(%s,%s)" %(i,l))
for j in range(len(N)+1):
x[i,j,l]=model.addVar(vtype="B", name="x(%s,%s,%s)" %(i,j,l))
for l in L:
for i in range(len(N)+1):
u[i,l]=model.addVar(vtype="C", name="u(%s)" %i)
model.update()
#Constraints
BigM = 10**6
for l in L:
model.addConstr(quicksum(x[0,j,l] for j in N if j!=0)*BigM >=
quicksum(q[j,l] for j in N), name="A.3")
model.addConstr(quicksum(x[i,0,l] for i in N if i!=0)*BigM >=
quicksum(q[j,l] for j in N), name="A.4")
for j in N:
model.addConstr(quicksum(x[i,j,l] for i in N if i!=j)\
-quicksum(x[j,v,l] for v in N if v!=j)==0, name="A.2")
model.addConstr(quicksum(x[i,j,l] for i in N if i!=j)*BigM >= q[j,l],
name="A.5")
model.addConstr(q[j,l] <= C, name="A.6")
for i in range(1,len(N)):
for s in S:
for k in K:
model.addConstr(quicksum(q[i,l] for l in L)\
==quicksum(D[s] for s in BOM if K[i] in BOM[s]),
name="A.7")
#subtour的限制式
for l in L:
model.addConstr(u[0,l]==0)
for i in range(len(N)+1):
for j in N:
if i!=j:
model.addConstr(u[i,l]-u[j,l] + (len(N)+1)*x[i,j,l] <=
(len(N)+1), name="A.8")
#Objective
model.setObjective(quicksum(R[i,j]*x[i,j,l] for i in N for j in N for l in L
if i!=j), GRB.MINIMIZE)
model.optimize()
目前跑出來的解，他會有2個小迴圈，0-5和5-0，以及1-2-3-4-1。
但我希望他是走1個迴圈，從0出發走完五個點後再回0。
x(0,5,33) 1.0
q(1,33) 2.0
x(1,2,33) 1.0
q(2,33) 2.0
x(2,3,33) 1.0
q(3,33) 2.0
x(3,4,33) 1.0
q(4,33) 2.0
x(4,1,33) 1.0
q(5,33) 2.0
x(5,0,33) 1.0
麻煩大大們幫忙看看我的限制式哪邊出了問題，感謝大家 > <
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.175.9.46 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1672557109.A.4F1.html
1F：推 jasonfghx: 出社會了沒辦法用groubi 01/09 16:12
2F：→ jasonfghx: 寫pulp還可以教 01/09 16:13
3F：推 illousion: 快速看一下問題應該在subtour 這個限制式數量是指數成 01/11 00:30
4F：→ illousion: 長 對於每個可能產生迴圈的點都要加一條去切掉 01/11 00:30
5F：→ illousion: 但是你的寫法 for l in L 這個是多項式寫法 不可能對 01/11 00:30
6F：→ illousion: 迴圈限制式處理方式都是一開始先不加 求解後從限制式裡 01/11 00:31
7F：→ illousion: 找 看哪一條違反了現在的解再加回去 01/11 00:31
8F：→ illousion: 這種作法叫 separation/delayed constraint generation 01/11 00:32
9F：→ illousion: 具體使用gurobi要用lazyconstraint callback 01/11 00:32
10F：→ illousion: 你要先懂數學原理 再懂callback寫法 才能處理這種問題 01/11 00:32