I am trying to find a way to have as few boxes as possible that fit bags of chemicals. A box cannot have weight more than 3.3 kg but have to be higher than 2.7 kg. I came across Google's OR tools but I am struggling to program the constraints.
When I input weights of my bags into the OR tool's bin packing program (following) with both the upper limit for box weight 'bin_capacity_upper_limit' and 'bin_capacity_lower_limit', I get no solution.
Is there someway to get an approximate solution? Perhaps by isolating the bags that are preventing from getting an optimal solution. I am new to OR tools or optimization in general. I will appreciate any help or suggestion.
from ortools.linear_solver import pywraplp
def create_data_model():
"""Create the data for the example."""
data = {}
weights = [1.0, 1.001, 1.09, 1.002, 1.006, 1.007, 1.0, .674, 1.002 , .22, .36, .24, 1.20, .4, .947, .987, .456]
data['weights'] = weights
data['items'] = list(range(len(weights)))
data['bins'] = data['items']
data['bin_capacity_upper_limit'] = 3.3
data['bin_capacity_lower_limit'] = 2.7
return data
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('SCIP')
data = create_data_model()
# Variables
# x[i, j] = 1 if item i is packed in bin j.
x = {}
for i in data['items']:
for j in data['bins']:
x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))
# y[j] = 1 if bin j is used.
y = {}
for j in data['bins']:
y[j] = solver.IntVar(0, 1, 'y[%i]' % j)
# Constraints
# Each item must be in exactly one bin.
for i in data['items']:
solver.Add(sum(x[i, j] for j in data['bins']) == 1)
# The amount packed in each bin cannot exceed its capacity.
for j in data['bins']:
solver.Add(
sum(x[(i, j)] * data['weights'][i] for i in data['items']) <= y[j] *
data['bin_capacity_upper_limit'])
solver.Add(
sum(x[(i, j)] * data['weights'][i] for i in data['items']) >= y[j] *
data['bin_capacity_lower_limit'])
# Objective: minimize the number of bins used.
solver.Minimize(solver.Sum([y[j] for j in data['bins']]))
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
num_bins = 0
for j in data['bins']:
if y[j].solution_value() == 1:
bin_items = []
bin_weight = 0
for i in data['items']:
if x[i, j].solution_value() > 0:
bin_items.append(i)
bin_weight += data['weights'][i]
if bin_items:
num_bins += 1
print('Bin number', j)
print(' Items packed:', bin_items)
print(' Total weight:', bin_weight)
print()
print()
print('Number of bins used:', num_bins)
print('Time = ', solver.WallTime(), ' milliseconds')
else:
print('The problem does not have an optimal solution.')
First, it's worth noting: your implementation is quite slow because it doesn't take advantage of the fact that your bin capacity limits place lower and upper bounds on the number of bins used. Introducing this moved my feasibility check from "multiple minutes so I decided to terminate it" to 0.21 seconds.
Next: as @sascha says, you need to choose what you mean by an approximate solution and exactly how you mean to sacrifice items. I present one approach here which only needs to sacrifice one option and completes in 0.03 seconds. I do not have or-tools so I demonstrate in PuLP.
import pulp
import numpy as np
weights = np.array((
1. , 1.001, 1.09 , 1.002, 1.006, 1.007, 1. , 0.674, 1.002,
0.22 , 0.36 , 0.24 , 1.2 , 0.4 , 0.947, 0.987, 0.456))
items = np.arange(len(weights))
bin_capacity_upper_limit = 3.3
bin_capacity_lower_limit = 2.7
absolute_lower = round(np.ceil(weights.sum() / bin_capacity_upper_limit))
absolute_upper = round(np.ceil(weights.sum() / bin_capacity_lower_limit))
bins = np.arange(absolute_upper)
def prove_infeasible():
solver = pulp.LpProblem(name='chemical_knapsack_exact', sense=pulp.LpMinimize)
# x[i, j] = 1 if item i is packed in bin j.
assignments = pulp.LpVariable.dicts(
name='assign', cat=pulp.LpBinary,
indices=[(i, j) for i in items for j in bins])
# y[j] = 1 if bin j is used. All bins below the lower bound are used (those vars are fixed).
bins_used = [
pulp.LpVariable(
name=f'bin_{j}', cat=pulp.LpBinary,
lowBound=1 if j < absolute_lower else 0)
for j in bins]
for i in items:
# Each item must be in exactly one bin.
solver.addConstraint(
name=f'assign_excl_{i}',
constraint=pulp.lpSum([
assignments[i, j]
for j in bins
]) == 1)
for j in bins:
# The amount packed in each bin cannot exceed its capacity.
weight = pulp.lpDot(weights,
[assignments[i, j] for i in items])
used = bins_used[j]
solver.addConstraint(
name=f'weight_hi_{j}',
constraint=weight <= used*bin_capacity_upper_limit)
solver.addConstraint(
name=f'weight_lo_{j}',
constraint=weight >= used*bin_capacity_lower_limit)
# Objective: minimize the number of bins used.
solver.objective = pulp.lpSum(bins_used)
solver.solve()
assert solver.status == pulp.LpStatusInfeasible
def solve_approximate():
"""
Preserve as exact the originally intended number of bins, and the lower and upper capacity
limits. This implies that absolute_upper is still true.
Sacrifice some items to achieve feasibility. This means that absolute_lower is no longer true
because some of the weights may be unused.
"""
solver = pulp.LpProblem(name='chemical_knapsack_approx', sense=pulp.LpMaximize)
# x[i, j] = 1 if item i is packed in bin j.
assignments = pulp.LpVariable.dicts(
name='assign', cat=pulp.LpBinary,
indices=[(i, j) for i in items for j in bins])
# y[j] = 1 if bin j is used.
bins_used = pulp.LpVariable.dicts(
name=f'bin', cat=pulp.LpBinary, indices=bins)
for i in items:
# Each item must be in up to one bin.
solver.addConstraint(
name=f'assign_excl_{i}',
constraint=pulp.lpSum([
assignments[i, j]
for j in bins
]) <= 1)
for j in bins:
# The amount packed in each bin cannot exceed its capacity.
weight = pulp.lpDot(weights,
[assignments[i, j] for i in items])
used = bins_used[j]
solver.addConstraint(
name=f'weight_hi_{j}',
constraint=weight <= used*bin_capacity_upper_limit)
solver.addConstraint(
name=f'weight_lo_{j}',
constraint=weight >= used*bin_capacity_lower_limit)
# Objective: minimize the number of bins used and maximize the number of items packed.
# Tweak value and cost to taste.
item_value = 1
bin_cost = 1
solver.objective = item_value*pulp.lpSum(assignments.values()) - bin_cost*pulp.lpSum(bins_used)
print(solver)
solver.solve()
assert solver.status == pulp.LpStatusOptimal
for j in bins:
assigned = np.array([assignments[i,j].value() for i in items], dtype=int)
print(f'Bin {j} is', ' used,' if bins_used[j].value() else 'unused,',
f'{assigned.sum()} items, {assigned.dot(weights):.4f} weight')
for i in items:
bin_idx = next((j for j in bins if assignments[i,j].value()), None)
print(f'Item {i} is', 'unused' if bin_idx is None else f'in bin {bin_idx}')
prove_infeasible()
solve_approximate()
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
...
Result - Problem proven infeasible
No feasible solution found
Enumerated nodes: 0
Total iterations: 1931
Time (CPU seconds): 0.21
Time (Wallclock seconds): 0.21
chemical_knapsack_approx:
MAXIMIZE
1*assign_(0,_0) + ... + 1*assign_(9,_3) + 1*assign_(9,_4) + 1*assign_(9,_5) + -1*bin_0 + -1*bin_1 + -1*bin_2 + -1*bin_3 + -1*bin_4 + -1*bin_5 + 0
SUBJECT TO
assign_excl_0: assign_(0,_0) + assign_(0,_1) + assign_(0,_2) + assign_(0,_3)
+ assign_(0,_4) + assign_(0,_5) <= 1
...
weight_hi_0: assign_(0,_0) + 1.001 assign_(1,_0) + 0.36 assign_(10,_0)
+ 0.24 assign_(11,_0) + 1.2 assign_(12,_0) + 0.4 assign_(13,_0)
+ 0.947 assign_(14,_0) + 0.987 assign_(15,_0) + 0.456 assign_(16,_0)
+ 1.09 assign_(2,_0) + 1.002 assign_(3,_0) + 1.006 assign_(4,_0)
+ 1.007 assign_(5,_0) + assign_(6,_0) + 0.674 assign_(7,_0)
+ 1.002 assign_(8,_0) + 0.22 assign_(9,_0) - 3.3 bin_0 <= 0
weight_lo_0: assign_(0,_0) + 1.001 assign_(1,_0) + 0.36 assign_(10,_0)
+ 0.24 assign_(11,_0) + 1.2 assign_(12,_0) + 0.4 assign_(13,_0)
+ 0.947 assign_(14,_0) + 0.987 assign_(15,_0) + 0.456 assign_(16,_0)
+ 1.09 assign_(2,_0) + 1.002 assign_(3,_0) + 1.006 assign_(4,_0)
+ 1.007 assign_(5,_0) + assign_(6,_0) + 0.674 assign_(7,_0)
+ 1.002 assign_(8,_0) + 0.22 assign_(9,_0) - 2.7 bin_0 >= 0
...
Result - Optimal solution found
Objective value: 12.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.03
Time (Wallclock seconds): 0.03
Bin 0 is used, 3 items, 3.0780 weight
Bin 1 is used, 4 items, 3.1740 weight
Bin 2 is unused, 0 items, 0.0000 weight
Bin 3 is used, 4 items, 3.0760 weight
Bin 4 is unused, 0 items, 0.0000 weight
Bin 5 is used, 5 items, 3.2580 weight
Item 0 is in bin 3
Item 1 is in bin 0
Item 2 is in bin 0
Item 3 is in bin 5
Item 4 is unused
Item 5 is in bin 1
Item 6 is in bin 1
Item 7 is in bin 3
Item 8 is in bin 3
Item 9 is in bin 1
Item 10 is in bin 5
Item 11 is in bin 5
Item 12 is in bin 5
Item 13 is in bin 3
Item 14 is in bin 1
Item 15 is in bin 0
Item 16 is in bin 5
Possibly more useful to the domain problem is to maximize total packed weight instead of number of packed items:
# Objective: minimize the number of bins used and maximize the weight packed.
# Tweak value and cost to taste.
item_value = 1
bin_cost = 1
repeated_weights = np.tile(weights, (absolute_upper, 1)).T.ravel()
solver.objective = (
item_value*pulp.lpDot(assignments.values(), repeated_weights)
- bin_cost*pulp.lpSum(bins_used))
Bin 0 is used, 5 items, 3.2960 weight
Bin 1 is used, 4 items, 3.2540 weight
Bin 2 is unused, 0 items, 0.0000 weight
Bin 3 is used, 3 items, 3.2920 weight
Bin 4 is used, 4 items, 3.2940 weight
Bin 5 is unused, 0 items, 0.0000 weight
Item 0 is in bin 0
Item 1 is in bin 1
Item 2 is in bin 3
Item 3 is in bin 0
Item 4 is in bin 1
Item 5 is in bin 1
Item 6 is in bin 4
Item 7 is in bin 0
Item 8 is in bin 3
Item 9 is in bin 0
Item 10 is in bin 4
Item 11 is in bin 1
Item 12 is in bin 3
Item 13 is in bin 0
Item 14 is in bin 4
Item 15 is in bin 4
Item 16 is unused
This is actually sped up and produces a more compact solution if you add an ordering criterion for bins so that all unused bins go on the end. All together,
import pulp
import numpy as np
weights = np.array((
1. , 1.001, 1.09 , 1.002, 1.006, 1.007, 1. , 0.674, 1.002,
0.22 , 0.36 , 0.24 , 1.2 , 0.4 , 0.947, 0.987, 0.456))
items = np.arange(len(weights))
bin_capacity_upper_limit = 3.3
bin_capacity_lower_limit = 2.7
absolute_lower = round(np.ceil(weights.sum() / bin_capacity_upper_limit))
absolute_upper = round(np.ceil(weights.sum() / bin_capacity_lower_limit))
bins = np.arange(absolute_upper)
def prove_infeasible():
solver = pulp.LpProblem(name='chemical_knapsack_exact', sense=pulp.LpMinimize)
# x[i, j] = 1 if item i is packed in bin j.
assignments = pulp.LpVariable.dicts(
name='assign', cat=pulp.LpBinary,
indices=[(i, j) for i in items for j in bins])
# y[j] = 1 if bin j is used. All bins below the lower bound are used (those vars are fixed).
bins_used = [
pulp.LpVariable(
name=f'bin_{j}', cat=pulp.LpBinary,
lowBound=1 if j < absolute_lower else 0)
for j in bins]
for i in items:
# Each item must be in exactly one bin.
solver.addConstraint(
name=f'assign_excl_{i}',
constraint=pulp.lpSum([
assignments[i, j]
for j in bins
]) == 1)
for j in bins:
# The amount packed in each bin cannot exceed its capacity.
weight = pulp.lpDot(weights,
[assignments[i, j] for i in items])
used = bins_used[j]
solver.addConstraint(
name=f'weight_hi_{j}',
constraint=weight <= used*bin_capacity_upper_limit)
solver.addConstraint(
name=f'weight_lo_{j}',
constraint=weight >= used*bin_capacity_lower_limit)
# Objective: minimize the number of bins used.
solver.objective = pulp.lpSum(bins_used)
solver.solve()
assert solver.status == pulp.LpStatusInfeasible
def solve_approximate():
"""
Preserve as exact the originally intended number of bins, and the lower and upper capacity
limits. This implies that absolute_upper is still true.
Sacrifice some items to achieve feasibility. This means that absolute_lower is no longer true
because some of the weights may be unused.
"""
solver = pulp.LpProblem(name='chemical_knapsack_approx', sense=pulp.LpMaximize)
# x[i, j] = 1 if item i is packed in bin j.
assignments = pulp.LpVariable.dicts(
name='assign', cat=pulp.LpBinary,
indices=[(i, j) for i in items for j in bins])
# y[j] = 1 if bin j is used.
bins_used = pulp.LpVariable.dicts(
name=f'bin', cat=pulp.LpBinary, indices=bins)
for i in items:
# Each item must be in up to one bin.
solver.addConstraint(
name=f'assign_excl_{i}',
constraint=pulp.lpSum([
assignments[i, j]
for j in bins
]) <= 1)
for j0, j1 in zip(bins[:-1], bins[1:]):
solver.addConstraint(
name=f'binorder_{j0},{j1}',
constraint=bins_used[j0] >= bins_used[j1])
for j in bins:
# The amount packed in each bin cannot exceed its capacity.
weight = pulp.lpDot(weights,
[assignments[i, j] for i in items])
used = bins_used[j]
solver.addConstraint(
name=f'weight_hi_{j}',
constraint=weight <= used*bin_capacity_upper_limit)
solver.addConstraint(
name=f'weight_lo_{j}',
constraint=weight >= used*bin_capacity_lower_limit)
# Objective: minimize the number of bins used and maximize the weight packed.
# Tweak value and cost to taste.
item_value = 1
bin_cost = 1
repeated_weights = np.tile(weights, (absolute_upper, 1)).T.ravel()
solver.objective = (
item_value*pulp.lpDot(assignments.values(), repeated_weights)
- bin_cost*pulp.lpSum(bins_used))
print(solver)
solver.solve()
assert solver.status == pulp.LpStatusOptimal
for j in bins:
assigned = np.array([assignments[i,j].value() for i in items], dtype=int)
print(f'Bin {j} is', ' used,' if bins_used[j].value() else 'unused,',
f'{assigned.sum()} items, {assigned.dot(weights):.4f} weight')
for i in items:
bin_idx = next((j for j in bins if assignments[i,j].value()), None)
print(f'Item {i} is', 'unused' if bin_idx is None else f'in bin {bin_idx}')
prove_infeasible()
solve_approximate()
Result - Optimal solution found
Objective value: 9.13600000
Enumerated nodes: 476
Total iterations: 19947
Time (CPU seconds): 1.22
Time (Wallclock seconds): 1.22
Option for printingOptions changed from normal to all
Total time (CPU seconds): 1.23 (Wallclock seconds): 1.22
Bin 0 is used, 3 items, 3.2910 weight
Bin 1 is used, 4 items, 3.2510 weight
Bin 2 is used, 5 items, 3.3000 weight
Bin 3 is used, 4 items, 3.2940 weight
Bin 4 is unused, 0 items, 0.0000 weight
Bin 5 is unused, 0 items, 0.0000 weight
Item 0 is in bin 2
Item 1 is in bin 0
Item 2 is in bin 0
Item 3 is in bin 1
Item 4 is in bin 2
Item 5 is in bin 1
Item 6 is in bin 3
Item 7 is in bin 2
Item 8 is in bin 1
Item 9 is in bin 2
Item 10 is in bin 3
Item 11 is in bin 1
Item 12 is in bin 0
Item 13 is in bin 2
Item 14 is in bin 3
Item 15 is in bin 3
Item 16 is unused