The knapsack problem applied to industry

We have all heard the question: what would you take to a deserted island? The idea sounds simple, but it forces us to choose between several items that provide a benefit while consuming a limited capacity in our backpack.

If there are only a few items, the decision can be made manually. However, when the number of options grows, many combinations offer similar benefits and similar costs. Choosing the best one is no longer obvious.

This type of problem is known in operations research as the knapsack problem.

To visualize it, understand it and solve it in an educational way, I developed an application that allows different configurations, tests several algorithms and compares the result obtained by each technique.

The natural next step would be to connect this logic to a SCADA application, so decisions could be automated and converted into real actions on PLCs.

Industry constantly faces similar decision problems. Some clear examples:

• Activating production lines with limited energy: deciding which lines to enable without exceeding electrical consumption limits.
• Selecting maintenance tasks during shutdowns: choosing which jobs to execute when available time is limited.
• Managing truck loads: maximizing transported value without exceeding weight, volume or logistics priorities.

The basic model seeks to maximize the total value of selected items without exceeding a capacity constraint.

As the number of items increases, the number of possible combinations grows exponentially.

This makes finding the exact solution computationally unfeasible in many cases. In practice, evaluating every combination can become impossible when there are many items or many constraints.

That is why approximate algorithms are often used: they provide good solutions quickly, even if they do not always guarantee the perfect one.

When the number of items is low or moderate, exact solutions can be used. When the problem grows, more efficient methods become necessary.

• They evaluate all possible combinations or explore the search space in a controlled way.
• They are reliable, but can become slow when there are many items.
• They rely on techniques such as dynamic programming or branch and bound.
• Google OR-Tools can apply these techniques to small or medium-sized problems.

• They do not always guarantee the best solution, but they are fast and practical.
• They use simple rules, such as selecting items with the best value-to-weight ratio.
• They are very useful in industrial systems that require real-time response.

• They are more advanced algorithms inspired by processes such as evolution, simulated annealing or swarms.
• They fit large, complex problems with multiple constraints.
• They can provide solutions very close to the optimum with low computational cost.

OR-Tools, Google's open-source library, combines several of these techniques and can solve the knapsack problem exactly or approximately depending on the case size and urgency. It is lightweight, fast and a good fit for industrial Python solutions.

The application aims to make the problem visible in an educational way and show different open-source algorithms for solving it. I built it with Copilot Agent in Visual Studio Code, using Streamlit.

The application lets you define the number of items, assign random benefits and weights, set the maximum knapsack capacity and run different algorithms to compare how each one solves the problem.

With the application we can:

• Modify the number of items, benefits and weights.
• Select different solving algorithms.
• Compare the results obtained by each algorithm.

Here is a video example:

PHS Knapsack is built with Streamlit and developed in Visual Studio Code. The source code is available on GitHub:

Download PHS Knapsack

Once downloaded and opened in Visual Studio Code, the basic steps are:

1. Install Python

2. Create a virtual environment:

3. Activate the environment:

4. Install requirements:

5. Run the application:

I also strongly recommend using Copilot Agent to continue developing the application, add new algorithms and adapt it to real plant scenarios.