Knapsack Problem - Optimization in Python with Gurobi (Part 4)

In this video, we introduce Integer Programming via Knapsack Problem and show how to implement it in Python by using gurobipy.

This video series introduces several Mathematical Optimization Problems and shows how to solve them in Python via gurobipy package (Python interface to Gurobi).

❔Answers to
↪︎ What is integer programming?
↪︎ What is knapsack problem?
↪︎ How can I formulate knapsack problem?
↪︎ How can I solve the binary knapsack problem in Python by using Gurobi?

⌚ Content:
↪︎ 0:00 - Intro
↪︎ 0:20 - What is integer programming
↪︎ 1:12 - Explanation of the binary knapsack problem
↪︎ 2:30 - Formulation of this optimization problem
↪︎ 3:29 - Solving the model

🌎 Follow Coding Perspective:

🎥 Video series:

[DS-uozy]

Code for everyone to copy!:

#1 creating the data (weights and values)
w = [4, 2, 5, 4, 5, 1, 3, 5]
v = [10, 5, 18, 12, 15, 1, 2, 8]
C = 15
N = len(w)
#2 Import gurobi package
from gurobipy import *
#3 create an optimization model
knapsack_model = Model('knapsack')
#4 add decision variables
x = knapsack_model.addVars(N, vtype=GRB.BINARY, name="x")
#5 define the objective function
obj_fn = sum(v[i]*x[i] for i in range(N))
knapsack_model.setObjective(obj_fn, GRB.MAXIMIZE)
#6 add the constraints
for i in range(N)) <= C)
#7 solve the model and output the solution
knapsack_model.setParam('OutputFlag', False)
knapsack_model.optimize()
print('Optimization is done. Objective function Value: %.2f' % knapsack_model.objVal)
for v in knapsack_model.getVars():
print('%s: %g' % (v.varName, v.x))

[GevheriHere]

Keep it up bro! Greetings from Gaziantep ;)

[CodingPerspective]

0:20 - What is integer programming
1:12 - Explanation of the binary knapsack problem
2:30 - Formulation of this optimization problem
3:29 - Solving the model in Python

[guilhermecadori]

Hi. Nice video. The only comment I have is that if you use range(N) you would be considering that length is 7 instead of 8, isn't it?

[christinejoyarce]

Hi! Awesome videos!!
Do you have a github account where we can access your jupyter notebooks? :)