Contact Blog Consulting

Multiple knapsack packing with nevergrad

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.

Data

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]

Variables

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)]

Objective

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

Constraints

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

Solver

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)

Result

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

Full code

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)