Knapsack problem

sac


In this tutorial we show you how to solve the knapsack operations research problem, using XLOPTIM, the fastest and most reliable solver for Microsoft Excel.

1. Data

To download the data for this XLOPTIM use case, please click the link below:

Download data for load Knapsack problem

2. The problem

In the knapsack problem, we have a given number of items, all of which have different weights, and which will generate different profits after their sale. The knapsack capacity prevents us from choosing all the objects: a mathematical optimization problem then emerges in which the objective will be to maximize the total profit of the objects chosen while respecting the capacity of the bag.

The knapsack problem can also be generalized to several bags, the number of combinations becoming combinatorial from a number of items, it often gives rise to studies for many researchers. This problem can be used to model problems of loading of goods, but also of industrial cutting problems very often enriched with constraints which complicate the initial problem.

The knapsack capacity here is 25000. For each of the 190 items, we know their profit and their weight, given in the table below:

table1

We seek to provide a linear modeling of this knapsack problem as well as a decision support tool in XLOPTIM®.

3. Modeling

We propose a modeling according to the following 5 steps:

Step #1: What are the dimensions / clues of the problem?

  • i : 1.. 190: items

Step #2: What are the data of the problem

  • The weight of each item i:

$$W_i$$

  • The profit of each item i:

$$P_i$$

  • The knapsack capacity:

$$K$$

Step #3: What are the decision variables?

  • Do I select the object i in my bag or not:

$$X_{i}$$

Step #4: What are the constraints?

  • The total weight of knapsack does not exceed his capacity K:

$$\forall \,\ j \in [1;190], \sum_{i=1}^{190}{(X_i.W_i)} \leqslant K$$

Step #5: What is the objective of the problem?

Maximize the total profit

$$Max\sum_{i=1}^{190}{(X_i.P_i)}$$

4. Translation into XLOPTIM®

xloptim1

Definition of the main Boolean decision variables:

xloptim2

Addition of the constraint “The total weight of knapsack does not exceed its capacity K":

xloptim3

Setting the objective (maximize the total profit):

xloptim4

Calculation of the optimum:

xloptim5

which gives a value of the following optimal objective function:

xloptim6

5. Conclusion

By deciding to keep these items in the bag, the total profit generated by the items will amount to € 30,975. The displayed result is optimal and obtained after 2 seconds.

This case study gives you an example of a backpack problem. They are frequent in the industrial problems of loading but also of cutting.

You can change the size of the problem and the assumptions to vary the problem and therefore the solutions. Do not hesitate to contact us if you have any questions following the use of our XLOPTIM® solver.

To download the 14-day free trial version of the software, go to: Download the trial version