0–1 Knapsack Problem: Integer Programming

What is Knapsack Problem?

A knapsack is like a container or a bag. In the knapsack problem, you have given some items with their value and the weight assigned to each item. You have to put the items in bag which give maximum value within the total specified weight of the bag.
There are two types of knapsack problems:
1. 0/1 Knapsack problem
2. Fractional Knapsack problem

In 0/1 knapsack problem means that item will be completely added to bag or not. It means items are not divisible.
The fractional knapsack problem means that we can divide the item to calculate the value/weight ratio and then put it into the bag.

Knapsack Problem

Example: Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value.

If we compare the above problem statement of 0/1 Knapsack is a classic example where we can use Integer Programming.

Linear optimization problems that require variables to be integers are called Integer Optimization. We will implement this optimization model using Google OR. you can also use another solver to implement this.

Basic steps of solving an Integer Programming :
1. Import the linear solver wrapper
2. Declare the MIP solver
3. Define the variables.
4. Define the constraints.
5. Define the objective function.
6. Call the solver
7. Display the solution.

Let, Items given below.
values = [60,100,120]
weight = [10,20,30]
W=50 (Maximum weight limit)

Step 1 : Import and Initialize the SCIP solve
from ortools.linear_solver import pywraplp
solver =  pywraplp.Solver.CreateSolver('SCIP')

Now, we need to create the integer decision variables. That takes a value in the range of 0–1

x = solver.IntVar(0,1,'var')

We can assume this variable will work as a boolean variable also, that will turn on/off.
The constraint is all the sums should be less than the weight limit i.e
Sum(xi*wi)≤WeightLimit
where xi is the bool variable of ith items and their weight accordingly.
Let's create a new list and save this constraint in it.

weights.append(x*wt[i])

The Objective Function is to maximize the value of the item associated with it.
So, we will multiple the variable with the value of the item.
z = Maximize(sum(xi*vi))
and store into another list.

objective_value = []
objective_value.append(x*val[i])

The final step is to call the solver and display the result.
Complete code:

from ortools.linear_solver import pywraplp
solver =  pywraplp.Solver.CreateSolver('SCIP')
d_var = []
objective_value = []
weights = []
for i in range(n):
    x = solver.IntVar(0,1,'var')
    
    objective_value.append(x*val[i])
    weights.append(x*wt[i])
solver.Add(solver.Sum(weights)<=W)
solver.Maximize(solver.Sum(objective_value))
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print('Objective Value ',solver.Objective().Value())

Output

You can find the complete code here at Github.

Thank You!!!

Keep Learning…Keep Exploring