The multiple knapsack problem is linear, it can be solved efficiently with tools like linear integer programming.
But just because you’re stuffing items into bins doesn’t mean you have a knapsack problem. Sometimes you have a problem that very much looks like a knapsack problem until you’re 90% done coding it into OR-Tools when you realise you need to take the absolute value of something, and the true nature of your nonlinear predicament is revealed.
Enter derivative-free optimisation, where algorithms couldn’t care less about the linearity, differentiability, or really anything about your objective function. Nevergrad is a Python package containing a number of such algorithms that nicely solved my quasi knapsack problem.
Here’s my approach to using nevergrad to optimise a multiple knapsack problem.
I’ll use the same parameters as in the OR-Tools knapsack tutorial.
weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
bin_capacities = [100, 100, 100, 100, 100]
Instead tracking item-bin assignments using n_bins * n_items boolean variables, I found it simpler and faster to use a single discrete categorical variable for each item. Each variable can take a value of 0 to 4 to represent assignment to the corresponding bin, and 5 to represent not being assigned to any bin.
In nevergrad Choice represents an unordered categorical variable.
n_bins = len(bin_capacities)
n_items = len(weights)
bins = list(range(n_bins + 1))
variables = [ng.p.Choice(bins) for _ in range(n_items)]
The objective we want to maxmise is the value of the packed items. Nevergrad only does minimisation so the negative of the objective is returned.
def objective(*assignments):
value = 0
for i_item, assigned_bin in enumerate(assignments):
if assigned_bin != n_bins: # Ignore items not assigned to any bin.
value += values[i_item]
return -1 * value
Using a single categorical variable for each item has another benefit: it removes the need for a constraint that each item can only be assigned to at most one bin.
The only constraint we need is on bin capacity.
bin_weights = [0] * n_bins
for i_item, assigned_bin in enumerate(assignments):
if assigned_bin != n_bins: # Ignore items not assigned to any bin.
bin_weights[assigned_bin] += weights[i_item]
fill = [weight - capacity for weight, capacity in zip(bin_weights, bin_capacities)]
overfill = sum([max(x, 0) for x in fill])
Nevergrad does have a mechanism for constraints (register_cheap_constraint). But for constraints like this that are expensive and use a lot of the same looping as the objective function, I found it worked better to add the constraint to the objective with a hefty penalty for violation.
def objective(*assignments):
value = 0
bin_weights = [0] * n_bins
for i_item, assigned_bin in enumerate(assignments):
if assigned_bin != n_bins: # Ignore items not assigned to any bin.
value += values[i_item]
bin_weights[assigned_bin] += weights[i_item]
# Constraint violation reduces value.
fill = [weight - capacity for weight, capacity in zip(bin_weights, bin_capacities)]
overfill = sum([max(x, 0) for x in fill])
value -= overfill * sum(bin_capacities)
return -1 * value
Nevergrad has a growing number of different solvers, I found DiscreteOnePlusOne works much better than the others at this discrete optimisation problem.
A hefty budget (number of iterations) is needed to solve this problem. It’s much slower than linear optimisation algorithms.
parametrization = ng.p.Instrumentation(*variables)
optimizer = ng.optimizers.DiscreteOnePlusOne(
parametrization=parametrization,
budget=5000,
)
recommendation = optimizer.minimize(objective)
Running the optimisation takes a few minutes, and for a problem of this size does find the optimal solution of 395.
best_assignment = recommendation.value[0]
best_value = -1 * objective(*best_assignment)
print(best_value)
Output:
395
import nevergrad as ng
# Problem setup.
weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
bin_capacities = [100, 100, 100, 100, 100]
# Solver variables.
n_bins = len(bin_capacities)
n_items = len(weights)
bins = list(range(n_bins + 1))
variables = [ng.p.Choice(bins) for _ in range(n_items)]
def objective(*assignments):
value = 0
bin_weights = [0] * n_bins
for i_item, assigned_bin in enumerate(assignments):
if assigned_bin != n_bins: # Ignore items not assigned to any bin.
value += values[i_item]
bin_weights[assigned_bin] += weights[i_item]
# Constraint violation reduces value.
fill = [weight - capacity for weight, capacity in zip(bin_weights, bin_capacities)]
overfill = sum([max(x, 0) for x in fill])
value -= overfill * sum(bin_capacities)
return -1 * value
parametrization = ng.p.Instrumentation(*variables)
optimizer = ng.optimizers.DiscreteOnePlusOne(
parametrization=parametrization,
budget=5000,
)
recommendation = optimizer.minimize(objective)
best_assignment = recommendation.value[0]
best_value = -1 * objective(*best_assignment)
print(best_value)