## Introduction

The **Knapsack Problem** is a classic 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.

## What is mathematical optimization?

Mathematical optimization, also known as mathematical programming, is a powerful technique for solving complex decision-making problems.

The **Knapsack Problem** is a specific type of mathematical optimization problem with many real-world applications in the fields of finance (e.g., portfolio optimization), logistics (e.g., cargo loading), and, as we'll see in our example, planning for camping trips 🎒.

## 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:

Food item | Weight (g) | Volume (cm³) | Calories |
---|---|---|---|

Granola Bars | 240 | 400 | 900 |

Potato Chips | 135 | 400 | 650 |

Beef Jerky | 2800 | 1500 | 5000 |

Almonds | 410 | 410 | 950 |

Apples | 182 | 190 | 95 |

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:

- Let $w_i$ be the weight of item $i$ in grams
- Let $v_i$ be the volume of item $i$ in cm³
- Let $c_i$ be the calorie content of item $i$
- Let $W$ be the maximum weight capacity (9500 g)
- 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:

$\sum_{i \in I} w_i x_i \leq W$Total volume constraint:

$\sum_{i \in I} v_i x_i \leq V$Non-negativity constraint (we can't pack a negative number of items):

$x_i \geq 0, \forall i \in I$### Objective function

Our goal is to maximize the total calories:

$\text{Maximize} \space \space \space \sum_{i \in I} c_i x_i$## 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!

For example, for Prof. A, this parameter would be denoted by $S_{\text{Prof. A}}$ and would equal $(\text{Maths, Physics}$