Classic optimization: the task of the backpack (knapsack problem)
Consider the following situation. Suppose you want to go abroad, but you do not change the currency - you can carry with you only goods for sale on the free market "there." With a plane is allowed to take no more than 20 kg. The question arises - what goods to take to transport the maximum value, given the weight limit? Vodka ($ 17 / 1.5 kg), a big Russian doll ($ 30 / 2.5 kg), a balalaika ($ 75/6 kg) or something else and in what quantities?
It suggests a solution - to find a product with the best price / weight ratio and take it in the maximum quantity.
We'll see - 3 balalaikas * $ 75 + 1 bottle * $ 17 = $ 242 (total weight 19.5 kg). It remains unused half a kilo, which can be used differently:
2 balalaikas * $ 75 + 2 big nesting dolls * $ 30 + 2 bottles * $ 17 = $ 244 (total weight 20 kg).
Those. "By eye" can not always get the most profitable option. In addition, there are often additional restrictions (more than 2 bottles can not be taken out, only 1 balalaika is on sale), and even with a large number of goods, manual counting is difficult. Therefore, the task is formalized for solving on a computer.
Problem in general (knapsack problem): There is a set of items, each with a certain weight and a certain value. From this set, you must select items with a maximum value, taking into account the restrictions on the maximum weight (the weight of the "backpack").
')
If the task can only take or not take a certain product, then the task will be binary (0-1 knapsack problem).
If the number of objects were not supposed to be integer, then the problem would be solved as a linear programming problem , for example, by a simplex method.
Due to the integer number of objects, the problem becomes an integer linear programming problem and is solved by the branch and bound method (branchAndBound or branchAndCut). This method has already been implemented in mathematical packages for many programming languages (it can be discussed in a special material).
In our case, the problem is solved using the freely distributed solver COIN-OR ( www.coin-or.org ) or GLPK ( http://www.gnu.org/software/glpk/glpk.html ), for which there is a convenient " wrapper "in Python - PuLP . PuLP is available in Google Code ( http://code.google.com/p/pulp-or/ ).
Using PuLP, we get this code:
The file can be downloaded from here: knapsack.py
As a result of the script, we get the solution:
It's nice to see that for this task we managed to find it ourselves.
Continuing the experiments, you can increase the number of variables, introduce new restrictions. In addition, a large number of other examples can be found in the documentation for PuLP (PDF)
It suggests a solution - to find a product with the best price / weight ratio and take it in the maximum quantity.
We'll see - 3 balalaikas * $ 75 + 1 bottle * $ 17 = $ 242 (total weight 19.5 kg). It remains unused half a kilo, which can be used differently:
2 balalaikas * $ 75 + 2 big nesting dolls * $ 30 + 2 bottles * $ 17 = $ 244 (total weight 20 kg).
Those. "By eye" can not always get the most profitable option. In addition, there are often additional restrictions (more than 2 bottles can not be taken out, only 1 balalaika is on sale), and even with a large number of goods, manual counting is difficult. Therefore, the task is formalized for solving on a computer.
Problem in general (knapsack problem): There is a set of items, each with a certain weight and a certain value. From this set, you must select items with a maximum value, taking into account the restrictions on the maximum weight (the weight of the "backpack").
')
If the task can only take or not take a certain product, then the task will be binary (0-1 knapsack problem).
If the number of objects were not supposed to be integer, then the problem would be solved as a linear programming problem , for example, by a simplex method.
Due to the integer number of objects, the problem becomes an integer linear programming problem and is solved by the branch and bound method (branchAndBound or branchAndCut). This method has already been implemented in mathematical packages for many programming languages (it can be discussed in a special material).
In our case, the problem is solved using the freely distributed solver COIN-OR ( www.coin-or.org ) or GLPK ( http://www.gnu.org/software/glpk/glpk.html ), for which there is a convenient " wrapper "in Python - PuLP . PuLP is available in Google Code ( http://code.google.com/p/pulp-or/ ).
Using PuLP, we get this code:
#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .
#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .#-*- coding: cp1251 -*- # PuLP from pulp import * # (LP) prob = LpProblem( "Knapsack problem" , LpMaximize) # , x1 = LpVariable( "x1" , 0, 10, 'Integer' ) x2 = LpVariable( "x2" , 0, 10, 'Integer' ) x3 = LpVariable( "x3" , 0, 10, 'Integer' ) # ( " " ) prob += 17*x1 + 30*x2 + 75*x3, "obj" # ( " " ) prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1" # prob.solve() # print "Status:" , LpStatus[prob.status] # for v in prob.variables(): print v.name, "=" , v.varValue # print ( "objective = %s$" % value (prob.objective)) * This source code was highlighted with Source Code Highlighter .
The file can be downloaded from here: knapsack.py
As a result of the script, we get the solution:
~$ python knapsack.py
Status: Optimal
x1 = 2.0
x2 = 2.0
x3 = 2.0
objective = 244.0$
It's nice to see that for this task we managed to find it ourselves.
Continuing the experiments, you can increase the number of variables, introduce new restrictions. In addition, a large number of other examples can be found in the documentation for PuLP (PDF)
Source: https://habr.com/ru/post/83918/
All Articles