Solving complex bin packing problem with GEKKO
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?
Solution
Here is a related optimization problem and solution for circle packing optimization:
More specific answers can be suggested with a complete and minimal example. Here is a version with sample data that reproduces the error:
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]}
- In C how would an ARM compiler optimize this struct?
- How is the function get called with -O2?
- php postgres from query to fetching rows in theory
- Constants and compiler optimization in C++
- Is dereferencing a member from a struct pointer in loop optimized as loop invariant?
- Is there any performance difference between calling a local variable and calling an object's instance variable?
- Disable specific compiler optimization
- Can the compiler optimize this snippet of code?
- Will gcc optimize away repeated function calls upon the same variable with same output for each call?
- Can a modern C compiler optimize a combination of bit accesses?
- Compiler Optimization for methods that only call another method
- How to program a MIP solver to find balanced Gray code for mixed radices?
- Does putting less number of curly braces really helps?
- Should we prefer temporary variables over user defined variables in c++
- Compiler optimizations in gcc
- Can a compliant Java compiler optimize this code?
- Does copy elision exist in C?
- How to optimize SQL query and create index
- Optimize SQL Queries on Big Table
- Speeding Up Index-Match for Large Dataset
- How do you determine the number of defined elements in an array?
- Producer consumer using a bounded Channel<T>, with strict memory allocation requirements
- JavaScript library more efficient than Rickshaw for realtime visualizations
- Is it more efficient to do a Less Than comparison then to do a Less Than Or Equal To comparison?
- Can Java compiler optimize adding to a set in recursive methods
- Which is fastest for importing large datasets that also need an update?
- Do I need to make multiple executables for targeting different instruction sets?
- Does building the compiler from source result in better optimization?
- Will the C# compiler optimize this code?
- Is [[likely]] redundant if [[unlikely]] exists in if-else branch in C++20?