英文:
Solving complex bin packing problem with GEKKO
问题
以下是您的代码的翻译部分：
“”“
初始化求解器
“”“
solver = GEKKO(remote=False)
solver.options.SOLVER = 1 # 也可以尝试0和3
“”“
创建数据模型
“”“
data = {}
data['items'] = list(range(len(group)))
data['pallets'] = list(range(len(group)))
data['pallet_length'] = pallet_dimensions[0] # 托盘的x维度
data['pallet_width'] = pallet_dimensions[1] # 托盘的y维度
data['pallet_area'] = pallet_dimensions[2]
“”“
变量
“”“
# x[i, b] = 1，如果物品i放入托盘b中。
x = {}
for i in data['items']:
for b in data['pallets']:
x[(i, b)] = solver.Var(0, lb=0, ub=1, integer=True)
# y[b] = 1，如果使用托盘b
y = {}
for j in data['pallets']:
y[j] = solver.Var(0, lb=0, ub=1, integer=True)
# 托盘b中堆叠i的中心X和Y坐标
cx = {}
cy = {}
for b in data['pallets']:
for i, stack in enumerate(group):
cx[(i, b)] = solver.Var(lb=stack._radius,
ub=data['pallet_length']-stack._radius,
integer=True)
cy[(i, b)] = solver.Var(lb=stack._radius,
ub=data['pallet_width'] -stack._radius,
integer=True)
“”“
约束
“”“
# 每个物品必须放入一个托盘中。
for i in data['items']:
solver.Equation( sum( x[(i, b)] for b in data['pallets'] ) == 1 )
# 托盘尺寸约束，堆叠物品的面积
# 不能超过托盘面积。
for b in data['pallets']:
solver.Equation( sum( x[(i, b)] * stack.area for i, stack in enumerate(group) ) <= y[b] * data['pallet_area'] )
# 强制没有堆叠物品的重叠。堆叠之间的距离
# 大于或等于它们半径的总和。
for b in data['pallets']:
for i in range(len(group) - 1):
for j in range(i + 1, len(group)):
# sqrt( (x2-x1)^2 + (y2-y1)^2 ) >= r2+r1
solver.Equation(solver.sqrt( (cx[(j, b)]-cx[(i, b)])**2 +
(cy[(j, b)]-cy[(i, b)])**2 ) >=
(group[i]._radius + group[j]._radius) )
“”“
目标
“”“
# 最小化使用的托盘数。
solver.Minimize( solver.sum( [y[b] for b in data['pallets']] ) )
“”“
解决
“”“
solver.solve( disp=True )
如果您有任何关于代码实现逻辑中的错误或问题的疑问，请随时提出，我会尽力协助您解决问题。
英文:
I am trying to solve a 2D circle bin packing problem, where the objective is to minimize the number of bins used. The items are circles with varying sizes and the required amount of bins is not known. So from a worst-case scenario the upper bound for number of bins is equal to number of items to be packed.
The variables include
x[i,b]whether itemiis packed in binby[b]whether binbis usedcx[i,b]andcy[i,b], center coordinates for itemiin binb.
When I run my model, GEKKO says that there is no solution found. I have implemented the same methodology in OR-Tools, but because it does not support non-linear equations it is not feasible for my use case, when the number of items or bins needed grows.
My code is currently following:
"""
Initialize solver
"""
solver = GEKKO(remote=False)
solver.options.SOLVER = 1 # Try also 0 and 3
"""
Create data model
"""
data = {}
data['items'] = list(range(len(group)))
data['pallets'] = list(range(len(group)))
data['pallet_length'] = pallet_dimensions[0] # x-dimension of pallet
data['pallet_width'] = pallet_dimensions[1] # y-dimension of pallet
data['pallet_area'] = pallet_dimensions[2]
"""
Variables
"""
# x[i, b] = 1 if item i is packed in pallet b.
x = {}
for i in data['items']:
for b in data['pallets']:
x[(i, b)] = solver.Var(0, lb=0, ub=1, integer=True)
# y[b] = 1 if pallet b is used
y = {}
for j in data['pallets']:
y[j] = solver.Var(0, lb=0, ub=1, integer=True)
# Center X and Y coodinates for stack i in pallet b
cx = {}
cy = {}
for b in data['pallets']:
for i, stack in enumerate(group):
cx[(i,b)] = solver.Var(lb=stack._radius,
ub=data['pallet_length']-stack._radius,
integer=True)
cy[(i,b)] = solver.Var(lb=stack._radius,
ub=data['pallet_width'] -stack._radius,
integer=True)
"""
Constaints
"""
# Each item must be in exactly one pallet.
for i in data['items']:
solver.Equation( sum( x[(i, b)] for b in data['pallets'] ) == 1 )
# Pallet size constraint, the area of packed stacks
# cannot exceed the pallet area.
for b in data['pallets']:
solver.Equation( sum( x[(i, b)] * stack.area for i, stack in enumerate(group) ) <= y[b] * data['pallet_area'] )
# Enforce no overlap on stack items. Distance between stack
# i and j equal or over to the sum of their radii.
for b in data['pallets']:
for i in range(len(group) - 1):
for j in range(i + 1, len(group)):
# sqrt( (x2-x1)^2 + (y2-y1)^2 ) >= r2+r1
solver.Equation(solver.sqrt( (cx[(j,b)]-cx[(i,b)])**2 +
(cy[(j,b)]-cy[(i,b)])**2 ) >=
(group[i]._radius + group[j]._radius) )
"""
Objective
"""
# Minimize the number of bins used.
solver.Minimize( solver.sum( [y[b] for b in data['pallets']] ) )
"""
Solve
"""
solver.solve( disp=True )
It looks like the no-overlap constraint is not working, because the model works if I remove that. But it is the most important part. Can you either find an error or an problem with my implementation logic?
答案1
得分: 0
这是与圆装箱优化相关的优化问题和解决方案：
可以通过一个完整且简化的示例提供更具体的答案。以下是包含重现错误的示例数据版本：
from gekko import GEKKO
"""
添加测试数据
"""
托盘尺寸 = [1,3,2]
group = [None]*5
半径 = 0.2
面积 = 0.1
"""
初始化求解器
"""
solver = GEKKO(remote=False)
solver.options.SOLVER = 1 # 也尝试0和3
"""
创建数据模型
"""
data = {}
data['items'] = list(range(len(group)))
data['pallets'] = list(range(len(group)))
data['pallet_length'] = 托盘尺寸[0] # 托盘的x维度
data['pallet_width'] = 托盘尺寸[1] # 托盘的y维度
data['pallet_area'] = 托盘尺寸[2]
"""
变量
"""
# x[i, b] = 1，如果项目i装在托盘b中。
x = {}
for i in data['items']:
for b in data['pallets']:
x[(i, b)] = solver.Var(0, lb=0, ub=1, integer=True)
# y[b] = 1，如果使用托盘b
y = {}
for j in data['pallets']:
y[j] = solver.Var(0, lb=0, ub=1, integer=True)
# 托盘b中堆栈i的中心X和Y坐标
cx = {}
cy = {}
for b in data['pallets']:
for i, stack in enumerate(group):
cx[(i,b)] = solver.Var(lb=半径,
ub=data['pallet_length']-半径,
integer=True)
cy[(i,b)] = solver.Var(lb=半径,
ub=data['pallet_width'] -半径,
integer=True)
"""
约束
"""
# 每个项目必须放在一个托盘中。
for i in data['items']:
solver.Equation( sum( x[(i, b)] for b in data['pallets'] ) == 1 )
# 托盘尺寸约束，堆叠的堆栈的面积不能超过托盘面积。
for b in data['pallets']:
solver.Equation(sum(x[(i,b)]*面积 for i, stack in enumerate(group))
<= y[b] * data['pallet_area'])
# 强制不重叠的堆栈项目。堆栈i和j之间的距离等于或大于它们的半径之和。
for b in data['pallets']:
for i in range(len(group) - 1):
for j in range(i + 1, len(group)):
# sqrt( (x2-x1)^2 + (y2-y1)^2 ) >= r2+r1
solver.Equation(solver.sqrt( (cx[(j,b)]-cx[(i,b)])**2 +
(cy[(j,b)]-cy[(i,b)])**2 ) >=
(半径 + 半径) )
"""
目标
"""
# 最小化使用的托盘数。
solver.Minimize( solver.sum( [y[b] for b in data['pallets']] ) )
"""
求解
"""
solver.solve( disp=True )
结果
----------------------------------------------
使用APOPT求解器的稳态优化
----------------------------------------------
Iter: 1 I: -1 Tm: 0.00 NLPi: 2 Dpth: 0 Lvs: 0 Obj: 0.00E+00 Gap: NaN
警告：没有更多可能的试验点，也没有整数解
最大迭代次数
---------------------------------------------------
求解器 : APOPT (v1.0)
解决时间 : 0.026099999999999984 秒
目标值 : 0.
未成功，错误代码 0
---------------------------------------------------
创建文件：infeasibilities.txt
使用命令apm_get(server,app,'infeasibilities.txt')检索文件
@error: 找不到解决方案
Traceback (most recent call last):
File "C:\Users\johnh\Desktop\test.py", line 86, in <module>
solver.solve( disp=True )
File "C:\Users\johnh\Python311\Lib\site-packages\gekko\gekko.py", line 2140, in solve
raise Exception(apm_error)
Exception: @error: 找不到解决方案
一些修改可能有助于找到解决方案。我包括了来自AirSquid的建议，并进行了一些额外的更改。
- 使用IPOPT进行初始化
solver.options.SOLVER = 3
solver.solve( disp=True )
solver.options.SOLVER = 1
solver.solve( disp=True )
- 尝试不等式约束。在解决方案中仍然应该等于1.0，但是对于求解器来说，在不可行空间中查找解决方案更容易。
# 每个项目必须放在一个托盘中。
for i in data['items']:
solver.Equation( sum( x[(i, b)] for b in data['pallets'
<details>
<summary>英文:</summary>
Here is a related optimization problem and solution for [circle packing optimization][1]:
[![circle packing][2]][2]
More specific answers can be suggested with a complete and minimal example. Here is a version with sample data that reproduces the error:
```python
from gekko import GEKKO
"""
Add test data
"""
pallet_dimensions = [1,3,2]
group = [None]*5
radius = 0.2
area = 0.1
"""
Initialize solver
"""
solver = GEKKO(remote=False)
solver.options.SOLVER = 1 # Try also 0 and 3
"""
Create data model
"""
data = {}
data['items'] = list(range(len(group)))
data['pallets'] = list(range(len(group)))
data['pallet_length'] = pallet_dimensions[0] # x-dimension of pallet
data['pallet_width'] = pallet_dimensions[1] # y-dimension of pallet
data['pallet_area'] = pallet_dimensions[2]
"""
Variables
"""
# x[i, b] = 1 if item i is packed in pallet b.
x = {}
for i in data['items']:
for b in data['pallets']:
x[(i, b)] = solver.Var(0, lb=0, ub=1, integer=True)
# y[b] = 1 if pallet b is used
y = {}
for j in data['pallets']:
y[j] = solver.Var(0, lb=0, ub=1, integer=True)
# Center X and Y coodinates for stack i in pallet b
cx = {}
cy = {}
for b in data['pallets']:
for i, stack in enumerate(group):
cx[(i,b)] = solver.Var(lb=radius,
ub=data['pallet_length']-radius,
integer=True)
cy[(i,b)] = solver.Var(lb=radius,
ub=data['pallet_width'] -radius,
integer=True)
"""
Constaints
"""
# Each item must be in exactly one pallet.
for i in data['items']:
solver.Equation( sum( x[(i, b)] for b in data['pallets'] ) == 1 )
# Pallet size constraint, the area of packed stacks
# cannot exceed the pallet area.
for b in data['pallets']:
solver.Equation(sum(x[(i,b)]*area for i, stack in enumerate(group))
<= y[b] * data['pallet_area'])
# Enforce no overlap on stack items. Distance between stack
# i and j equal or over to the sum of their radii.
for b in data['pallets']:
for i in range(len(group) - 1):
for j in range(i + 1, len(group)):
# sqrt( (x2-x1)^2 + (y2-y1)^2 ) >= r2+r1
solver.Equation(solver.sqrt( (cx[(j,b)]-cx[(i,b)])**2 +
(cy[(j,b)]-cy[(i,b)])**2 ) >=
(radius + radius) )
"""
Objective
"""
# Minimize the number of bins used.
solver.Minimize( solver.sum( [y[b] for b in data['pallets']] ) )
"""
Solve
"""
solver.solve( disp=True )
Results
----------------------------------------------
Steady State Optimization with APOPT Solver
----------------------------------------------
Iter: 1 I: -1 Tm: 0.00 NLPi: 2 Dpth: 0 Lvs: 0 Obj: 0.00E+00 Gap: NaN
Warning: no more possible trial points and no integer solution
Maximum iterations
---------------------------------------------------
Solver : APOPT (v1.0)
Solution time : 0.026099999999999984 sec
Objective : 0.
Unsuccessful with error code 0
---------------------------------------------------
Creating file: infeasibilities.txt
Use command apm_get(server,app,'infeasibilities.txt') to retrieve file
@error: Solution Not Found
Traceback (most recent call last):
File "C:\Users\johnh\Desktop\test.py", line 86, in <module>
solver.solve( disp=True )
File "C:\Users\johnh\Python311\Lib\site-packages\gekko\gekko.py", line 2140, in solve
raise Exception(apm_error)
Exception: @error: Solution Not Found
A few modifications may help find a solution. I've included the suggestions from AirSquid and also made a few additional changes.
- Initialize with IPOPT
solver.options.SOLVER = 3
solver.solve( disp=True )
solver.options.SOLVER = 1
solver.solve( disp=True )
- Try an inequality constraint. It should still be equal to 1.0 at the solution, but it is easier for the solver to find a solution by looking in the infeasible space.
# Each item must be in exactly one pallet.
for i in data['items']:
solver.Equation( sum( x[(i, b)] for b in data['pallets'] ) >= 1 )
Here is a complete script with a successful solution:
from gekko import GEKKO
"""
Add test data
"""
pallet_dimensions = [5,3,2]
group = [None]*3
radius = 0.1
area = 0.1
"""
Initialize solver
"""
solver = GEKKO(remote=False)
solver.options.SOLVER = 1 # Try also 0 and 3
"""
Create data model
"""
data = {}
data['items'] = list(range(len(group)))
data['pallets'] = list(range(len(group)))
data['pallet_length'] = pallet_dimensions[0] # x-dimension of pallet
data['pallet_width'] = pallet_dimensions[1] # y-dimension of pallet
data['pallet_area'] = pallet_dimensions[2]
"""
Variables
"""
# x[i, b] = 1 if item i is packed in pallet b.
x = {}
for i in data['items']:
for b in data['pallets']:
x[(i, b)] = solver.Var(0.5, lb=0, ub=1, integer=True)
# y[b] = 1 if pallet b is used
y = {}
for j in data['pallets']:
y[j] = solver.Var(0.1, lb=0, ub=1, integer=True)
# Center X and Y coodinates for stack i in pallet b
cx = {}
cy = {}
for b in data['pallets']:
for i, stack in enumerate(group):
cx[(i,b)] = solver.Var(lb=radius,
ub=data['pallet_length']-radius)
cy[(i,b)] = solver.Var(lb=radius,
ub=data['pallet_width'] -radius)
"""
Constaints
"""
# Each item must be in exactly one pallet.
for i in data['items']:
solver.Equation( sum( x[(i, b)] for b in data['pallets'] ) >= 1 )
# Pallet size constraint, the area of packed stacks
# cannot exceed the pallet area.
for b in data['pallets']:
solver.Equation(sum(x[(i,b)]*area for i, stack in enumerate(group))
<= y[b] * data['pallet_area'])
# Enforce no overlap on stack items. Distance between stack
# i and j equal or over to the sum of their radii.
for b in data['pallets']:
for i in range(len(group) - 1):
for j in range(i + 1, len(group)):
# sqrt( (x2-x1)^2 + (y2-y1)^2 ) >= r2+r1
solver.Equation((cx[(j,b)]-cx[(i,b)])**2 +
(cy[(j,b)]-cy[(i,b)])**2 >=
(radius + radius)**2 )
"""
Objective
"""
# Minimize the number of bins used.
solver.Minimize( solver.sum( [y[b] for b in data['pallets']] ) )
"""
Solve
"""
solver.options.SOLVER = 3
solver.solve( disp=True )
solver.options.SOLVER = 1
solver.solve( disp=True )
print(x)
Results for x
{(0, 0): [0.0], (0, 1): [0.0], (0, 2): [1.0],
(1, 0): [0.0], (1, 1): [0.0], (1, 2): [1.0],
(2, 0): [0.0], (2, 1): [0.0], (2, 2): [1.0]}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论