Solving the Knapsack Problem with Python and OR-Tools

Introduction

The Knapsack Problem is a mathematical optimization problem in computer science and operations research.

It's named after the scenario of choosing which items to pack in a knapsack (or backpack) to maximize the value of the items while staying within the weight limit of the knapsack.

In this tutorial, we'll explore how to use Python and Google's OR-Tools library to solve the Knapsack Problem. We'll use mathematical optimization (also known as mathematical programming), a powerful technique for solving complex decision-making problems.

Intended audience

This blog post is intended for beginner-to-intermediate Python developers.

You don't need any prior knowledge of mathematical optimization or OR-Tools, but it will help if you understand basic Python concepts like loops, functions and lists.

Problem description

Emily is planning a weekend camping trip in the woods. She can carry a maximum of 9.5 kg, and has 5500 cm3 of space to carry supplies in her bag.

Emily can pick as many items as she wants from the following collection of supplies:

Our task is to work out: what is the largest number of calories she can bring with them, given her constraints?

Mathematics

To solve this problem using mathematical optimization, we need to translate our constraints and goals into mathematical language. Let's break this down step by step.

Sets

In this problem, we have one main set:

Let $I$ be the set of all available food items

Parameters

We'll define the following parameters:

1. Let $w_i$ be the weight of item $i$ in grams
2. Let $v_i$ be the volume of item $i$ in cm³
3. Let $c_i$ be the calorie content of item $i$
4. Let $W$ be the maximum weight capacity (9500 g)
5. Let $V$ be the maximum volume capacity (5500 cm³)

Decision variables

For each item, we need to decide how many units to include:

Let $x_i$ be an integer variable representing the number of units of item $i$ to include

Constraints

We can express our constraints mathematically as follows:

Total weight constraint:

Total volume constraint:

Non-negativity constraint (we can't pack a negative number of items):

Objective function

Our goal is to maximize the total calories:

Solving with Python

Now that we've formulated the problem mathematically, let's implement the solution using Python and OR-Tools.

First, we'll import the necessary libraries:

from ortools.linear_solver import pywraplp
import pandas as pd

Next, let's define our data:

data = {
    'item': ['Granola bars', 'Potato chips', 'Beef jerky', 'Almonds', 'Apples'],
    'weight': [240, 135, 2800, 410, 182],
    'volume': [400, 400, 1500, 410, 190],
    'calories': [900, 650, 5000, 950, 95]
}

df = pd.DataFrame(data)

Now, let's create our solver and define the variables:

# Create the solver
solver = pywraplp.Solver.CreateSolver('SCIP')

# Create variables
x = {}
for i in df.index:
    x[i] = solver.IntVar(0, solver.infinity(), f'x_{i}')

# Print variables to verify
print('Number of variables =', solver.NumVariables())

Next, we'll add our constraints:

max_weight = 9500  # 9.5 kg in grams
max_volume = 5500  # in cm³

# Weight constraint
solver.Add(solver.Sum([df.loc[i, 'weight'] * x[i] for i in df.index]) <= max_weight)

# Volume constraint
solver.Add(solver.Sum([df.loc[i, 'volume'] * x[i] for i in df.index]) <= max_volume)

# Print constraints to verify
print('Number of constraints =', solver.NumConstraints())

Now, let's define our objective function:

# Objective function
objective = solver.Objective()

for i in df.index:
    objective.SetCoefficient(x[i], df.loc[i, 'calories'])

objective.SetMaximization()

Finally, we can solve the problem and print the results:

# Solve the problem
status = solver.Solve()

# Print solution
if status == pywraplp.Solver.OPTIMAL:
    print('Solution:')
    print('Objective value =', solver.Objective().Value())
    for i in df.index:
        if x[i].solution_value() > 0:
            print(f"{df.loc[i, 'item']}: {x[i].solution_value()}")
    print('Total weight:', sum(df.loc[i, 'weight'] * x[i].solution_value() for i in df.index), 'g')
    print('Total volume:', sum(df.loc[i, 'volume'] * x[i].solution_value() for i in df.index), 'cm³')
else:
    print('The problem does not have an optimal solution.')

When we run this code, we get the following output:

Number of variables = 5
Number of constraints = 2

Solution:
Objective value = 22800.0
Granola bars: 13.0
Potato chips: 21.0
Total weight: 5955.0 g
Total volume: 5500.0 cm³

Interpreting the results

Our optimization model suggests that Emily should pack:

• 13 units of granola bars
• 21 units of potato chips

This combination will provide her with 22,800 calories, while staying within the weight limit (5.955 kg out of 9.5 kg) and exactly meeting the volume limit (5500 cm³). Interestingly, the model didn't select any beef jerky, almonds, or apples. This is because the granola bars and potato chips provide the best calorie-to-weight-and-volume ratio among the available options.

Conclusion

In this article, we've explored how to solve a real-world optimization problem using mathematical programming techniques with Python and Google OR-Tools. We've seen how to:

• Formulate a problem mathematically
• Implement the solution using OR-Tools
• Interpret the results

This approach can be applied to a wide range of optimization problems beyond just packing for camping trips. Whether you're optimizing supply chains, financial portfolios, or resource allocation, the principles remain the same.

Remember, while our model provides a mathematically optimal solution, real-world considerations might lead to different choices. For example, Emily might want to include a variety of foods for nutritional balance, even if it's not mathematically optimal.

Happy optimizing, and happy camping!