作者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/cn.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