Optimization classic: knapsack problem

    Consider the following situation. Suppose you want to go abroad, but you don’t change the currency - you can only carry goods with you for sale on the free market “there”. It is allowed to take no more than 20 kg with you on the plane. The question arises - what goods to take in order to carry the maximum value, given the weight limit? Vodka ($ 17 / 1.5 kg), a large nesting doll ($ 30 / 2.5 kg), balalaika ($ 75/6 kg) or something else and in what quantities?

    The solution is to find a product with the best price / weight ratio and take it in the maximum quantity.
    Let's see - 3 balalaikas * $ 75 + 1 bottle * $ 17 = $ 242 (total weight 19.5 kg). Remained unused half a kilo, which can be used in a different way:
    2 balalaikas * $ 75 + 2 large nesting dolls * $ 30 + 2 bottles * $ 17 = $ 244 (total weight 20 kg).

    Those. "By eye" may not always turn out the most profitable option. In addition, often there are additional restrictions (more than 2 bottles can not be taken out, only 1 balalaika is on sale), and with a large number of goods manual counting is difficult. Therefore, the task is formalized for solving on a computer.

    The task 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 cost, taking into account the restrictions on the maximum weight (weight of the "backpack").

    If a task can only take or not take a specific 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 aslinear programming problem , for example, by the simplex method.
    Due to the integer number of objects, the task becomes an integer linear programming task 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 will be discussed in a special material).

    In our case, it is proposed to solve the problem 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 on Google Code ( http://code.google.com/p/pulp-or/ ).

    Using PuLP, we get the following code:
    1. #-*- coding: cp1251 -*-
    2. # импортируем функции PuLP
    3. from pulp import *
    4.  
    5. # Создаем новую задачу Линейного программирования (LP) с максимизацией целевой функции
    6. prob = LpProblem("Knapsack problem", LpMaximize)
    7.  
    8. # Переменные оптимизации, целые
    9. x1 = LpVariable("x1", 0, 10, 'Integer')
    10. x2 = LpVariable("x2", 0, 10, 'Integer')
    11. x3 = LpVariable("x3", 0, 10, 'Integer')
    12.  
    13. # Целевая функция ("ценность рюкзака")
    14. prob += 17*x1 + 30*x2 + 75*x3, "obj"
    15.  
    16. # Ограничение ("вес рюкзака")
    17. prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1"
    18.  
    19. # Запускаем решатель
    20. prob.solve()
    21.  
    22. # Выводим статус задачи
    23. print "Status:", LpStatus[prob.status]
    24.  
    25. # Выводим получившиеся оптимальные значения переменных
    26. for v in prob.variables():
    27.   print v.name, "=", v.varValue
    28.  
    29. # Выводим оптимальное значение целевой функции
    30. 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: 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 PuLP documentation (PDF)
    ~$ python knapsack.py
    Status: Optimal
    x1 = 2.0
    x2 = 2.0
    x3 = 2.0
    objective = 244.0$




    Also popular now: