The Knapsack Problem: Applied in Industry

We have all heard the question: What would you take to a deserted island? This question involves choosing from a limited number of items that provide a benefit while also having a weight in our "backpack".

If there are few items, the decision may be simple. However, when the number of options is high, there are numerous combinations that can be beneficial and have similar costs - or weights. In this second case, it is not easy to determine which of all is the best combination.

This type of problem is known in operations research as "The Knapsack Problem".

To visualize, understand, and even solve this type of problem, I have developed an application that allows for different configurations of the problem and solves it using various techniques. Additionally, it allows for comparison between the different algorithms used.

The next step would be to connect it to a SCADA application, so that decisions can be made automatically, executing the corresponding actions in our PLCs.

In industry, we continuously face decision problems similar to this:

• Activation of production lines with limited energy: choosing which lines to activate without exceeding electrical consumption limits.
• Selection of maintenance tasks during technical stops: limited time.
• Management of truck loads: maximizing the transported value.

This type of problem is modeled as follows:

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, it is impossible to evaluate all combinations when there are many elements.

Therefore, we resort to approximate algorithms that provide good solutions in a short time, even if they are not perfect.

When the number of items is low or moderate, an exact solution can be used. But when the problem grows, it is necessary to resort to more efficient methods.

• Evaluate all possible combinations to find the best one.
• They are reliable but slow when there are many items.
• They are based on techniques such as dynamic programming or branch and bound.
• Google's OR-Tools allows applying these techniques efficiently in small or medium problems.

• Do not guarantee the best solution, but are fast and practical.
• Use simple rules to find good combinations (e.g., selecting items with better value/weight).
• Very useful in industrial systems that require real-time results.

• More advanced algorithms inspired by nature (genetic, simulated annealing, particle swarm…).
• Ideal for large and complex problems with multiple constraints.
• Provide solutions very close to optimal with low computational cost.

OR-Tools, Google's open-source library, combines several of these techniques and allows solving the knapsack problem both exactly and approximately, depending on the size and urgency of the problem.
It is lightweight, fast, and perfect for integrating with industrial solutions in Python.

The developed application aims to make the problem visible in an educational way, as well as to present the different algorithms (open source) that exist to solve it. For this, I have developed with Co-Pilot "Agent" in Visual Code, an application in Streamlit that shows all of this.

The application is very simple, and basically what we do is determine the number of items we can put in our backpack, giving them random benefits, weights, and with a maximum weight for the backpack. With this, we execute the different algorithms and see how each one solves the problem, to understand the differences between them.

With the application we can:

• Modify the number of items, benefits, and weights of the elements.
• Select between different resolution algorithms.
• Compare the algorithms used.

Here is a video with an example: