In this first article is introduced a systematic way to approach and solve optimization problems. Then, the multi-knapsack problem itself is introduced. Then we apply the rules defined before on how to solve optimization problems and obtain the optimal solution to the multi-knapsack problem, formulated as a Mixed Integer problem and using Python-MIP package. Let's now introduce simple steps one can follow to approach optimization problems with optimization solvers.
Main steps while creating an optimization model to solve a business problem
Once a business problem that could benefit from optimization has been identified, we can define a systematic approach based on 3 steps for solving all kind of optimization problems with optimization solvers. These 3 steps are highlighted in the figure below.
Figure 1 : The 3 main steps for solving a business problem through optimization
In more details, these 3 steps are:
Create the conceptual mathematical model that defines the different variables, constraints, etc. in the business problem. This step consists in writing down on paper the equations that define our problem.
Translate the conceptual mathematical model into a computer program. For most programming languages used for optimization, the computer program will largely resembles the mathematical equations one would write on paper.
Solve the mathematical model using a math programming solver. The solver available for Mathematical Programming (solvers such as GLPK, Gurobi, CPLEX...) relies on very sophisticated algorithms. Important algorithms and ideas used in these solvers are, among many others: simplex method, branch & bound, use of heuristics...
Let's see those 3 steps for the case of the multi-knapsack problem.
The multi-knapsack problem
The objective here is, given a set of n items and a set of m knapsacks, to maximize the total value of the items put in the knapsacks without exceeding their capacity.
Below, wi represents the weight of item i, pi the value of item i while cj represents the capacity of knapsack j.
Figure 2: Description of the multi-knapsack problem
The multi-knapsack is an extension of the classical knapsack problem where instead of considering only one knapsack, we consider as many as we want. This allows to easily extend the complexity of this problem.
While the problem is relatively easy to define mathematically, it belongs to the class of NP-hard problems. Without going into the details of what defines NP-hard problems, we can easily see that the complexity of the knapsack problems explodes when the number of knapsacks and items increases. Indeed, we have mn available combinations we would need to test should we want to apply a brute-force approach for solving this problem. Just with 10 knapsacks and 80 items, there are 1080 combinations, which is the estimation of the number of atoms in the universe! And 10 knapsacks and 80 items is still quite limited... Let's now try to create the conceptual mathematical model by defining the problem with equations.
Creating the conceptual mathematical model
A quick translation of the multi-knapsack problem with equation can be written as the following:
Now that we managed to translate the problem into a set of equations, let's translate this mathematical model so that it is understood by a computer program. Below, we will make use of the Python package Python-MIP which is open-source and provides tools for modeling and solving Mixed-Integer Linear Programming Problems (MIP), relying on fast open source solvers.
Translating the mathematical model into a computer program with Python-MIP
Before solving the problem, we have to generate an instance for it (have data defining the problem). To do so, you can use the following code that will generate an instance of this problem with 40 items to store in 5 bags.
import pandas as pd
import numpy as np
import pickle
def data_generator_knapsack(number_bags, number_items, minimum_weight_item, maximum_weight_item, minimum_value_item, maximum_value_item, max_weight_bag):
data = {}
weights = np.random.randint(minimum_weight_item, maximum_weight_item, size = number_items)
values = np.random.randint(minimum_value_item, maximum_value_item, size = number_items)
data['weights'] = weights
data['values'] = values
data['items'] = list(range(len(weights)))
data['num_items'] = len(weights)
data['bins'] = list(range(number_bags))
data['bin_capacities'] = np.random.randint(0, max_weight_bag, size = number_bags) + np.int(np.mean(data['weights']))
return(data)
number_bags = 5
number_items = 40
minimum_weight_item = 0
maximum_weight_item = 75
minimum_value_item = 0
maximum_value_item = 75
max_weight_bag = 150
data = data_generator_knapsack(number_bags, number_items, minimum_weight_item, maximum_weight_item, minimum_value_item, maximum_value_item, max_weight_bag)
Let's now import the package used to have access to the MIP solver, here using the python package Python-MIP:
from mip import Model, xsum, maximize, BINARY
Now, we can translate the mathematical model so that it is understood by Python-MIP.
def mip_solve_knapsack(data):
model = Model("knapsack")
x = [[model.add_var(var_type=BINARY) for i in data['items']] for j in data['bins']]
model.objective = maximize(xsum((xsum(data['values'][i] * x[j][i] for i in data['items']) for j in data['bins'])))
for j in data['bins']:
model += xsum(data['weights'][i] * x[j][i] for i in data['items']) <= data['bin_capacities'][j]
# Each item can be in at most one bin
for i in data['items']:
model += xsum(x[j][i] for j in data['bins']) <= 1
model.optimize()
return(model)
Remark how close it is from the original equations! These solvers are very powerful and yet easy to use directly in Python. The code is indeed very close to the original equations.
Solving the mathematical model with Python-MIP
Using the mip_solve_knapsack function defined in the previous section, we can access to important information regarding the problem, such as the final objective value and the values of xij telling us what were the best combinations of items inside knapsacks.
Some Mathematical Optimization packages
In the notebook associated to this article, the package Python-MIP was used. Python-MIP is free, but many other packages exist for solving optimization problems on Python (and other languages of course like Julia). For instance OR-Tools from Google is a well-recognized free solver, with detailed documentation.
On the other side, Gurobi is a very popular commercial solution for mathematical optimization and its documentation is extremely rich, with quick introductions about Mathematical Programming, Linear Programming and Mixed-Integer Programming. Importantly, it has a large number of modeling examples from all industry fields directly available on Google Colab allowing to better grasp notions of Mathematical Modelling and to improve modeling skills to tackle all kind of optimization problems with Python. This resource can be of use even if one doesn't plan to use this commercial software but rather a free package such as OR-Tools.
Conclusion
In this article was introduced the multi-knapsack problem, an NP-complete problem, very difficult to solve when taking many items and bags.
The approach to solve the multi-knapsack problem relied on Python-MIP, a free optimization package using powerful MILP solvers to solve very efficiently all kinds of optimization problems.
In the next part of this series on the multi-knapsack problem, well studied in the field of Operations Research and at the heart of many real optimization problems, we'll highlight how Deep Reinforcement Learning can be used in order to solve combinatorial optimization problems such as this one. Stay tuned!