Документация Engee

Пример задачи о рюкзаке

Цель данного руководства — продемонстрировать формулирование и решение простой задачи оптимизации.

Требуемые пакеты

Для этого руководства требуются следующие пакеты.

using JuMP
import HiGHS

Формулировка

Задача о рюкзаке — это классическая задача оптимизации: имея набор предметов и контейнер фиксированной вместимости, нужно выбрать подмножество предметов с наибольшей суммарной ценностью, которые поместятся в контейнер без превышения его вместимости.

Название задачи намекает на аналогию со сборами в поездку: вместимости соответствует ограничение по весу багажа, а цель — упаковать наиболее выгодную комбинацию вещей.

Задачу о рюкзаке можно сформулировать как целочисленную линейную программу:

где  — вместимость и есть выбор между предметами, причем предмет имеет вес и ценность . Переменная решения равна 1, если предмет выбран, и 0 в противном случае.

Эту формулировку можно более лаконично записать так:

Данные

Данные для задачи состоят из двух векторов (один для ценности, а другой для весов), а также вместимости.

Всего имеется пять объектов:

n = 5;

В нашем примере вместимость равна 10 единицам:

capacity = 10.0;

а данные по ценности и стоимости выглядят так:

profit = [5.0, 3.0, 2.0, 7.0, 4.0];
weight = [2.0, 8.0, 4.0, 2.0, 5.0];

Формулировка на языке JuMP

Начнем строить модель JuMP для нашей задачи о рюкзаке.

Сначала создадим объект Model для сохранения элементов модели по мере их создания. Также зададим решатель, который будет вызван для решения модели после ее построения.

model = Model(HiGHS.Optimizer)
A JuMP Model
├ solver: HiGHS
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

Далее нам нужны переменные решения, представляющие выбираемые предметы:

@variable(model, x[1:n], Bin)
5-element Vector{VariableRef}:
 x[1]
 x[2]
 x[3]
 x[4]
 x[5]

Теперь необходимо ограничить эти переменные так, чтобы их общий вес был не больше заданной вместимости:

@constraint(model, sum(weight[i] * x[i] for i in 1:n) <= capacity)
2 x[1] + 8 x[2] + 4 x[3] + 2 x[4] + 5 x[5] ≤ 10

Наконец, наша цель — максимизировать совокупную ценность выбранных предметов:

@objective(model, Max, sum(profit[i] * x[i] for i in 1:n))
5 x[1] + 3 x[2] + 2 x[3] + 7 x[4] + 4 x[5]

Давайте выведем понятное человеку описание модели и проверим, выглядит ли модель так, как ожидалось:

print(model)
Max 5 x[1] + 3 x[2] + 2 x[3] + 7 x[4] + 4 x[5]
Subject to
 2 x[1] + 8 x[2] + 4 x[3] + 2 x[4] + 5 x[5] ≤ 10
 x[1] binary
 x[2] binary
 x[3] binary
 x[4] binary
 x[5] binary

Теперь можно решить задачу оптимизации и проверить результаты.

optimize!(model)
@assert is_solved_and_feasible(model)
solution_summary(model)
* Solver : HiGHS

* Status
  Result count       : 1
  Termination status : OPTIMAL
  Message from the solver:
  "kHighsModelStatusOptimal"

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : NO_SOLUTION
  Objective value    : 1.60000e+01
  Objective bound    : 1.60000e+01
  Relative gap       : 0.00000e+00

* Work counters
  Solve time (sec)   : 7.57217e-04
  Simplex iterations : 1
  Barrier iterations : -1
  Node count         : 1

Выбранные предметы:

items_chosen = [i for i in 1:n if value(x[i]) > 0.5]
3-element Vector{Int64}:
 1
 4
 5

Написание функции

После интерактивной работы желательно реализовать модель в виде функции.

С помощью функции можно обеспечить четко определенные входные данные для модели, прошедшие проверку, и правильное протекание процесса решения.

function solve_knapsack_problem(;
    profit::Vector{Float64},
    weight::Vector{Float64},
    capacity::Float64,
)
    n = length(weight)
    # Векторы ценности и весов должны быть одинаковой длины.
    @assert length(profit) == n
    model = Model(HiGHS.Optimizer)
    set_silent(model)
    @variable(model, x[1:n], Bin)
    @objective(model, Max, profit' * x)
    @constraint(model, weight' * x <= capacity)
    optimize!(model)
    @assert is_solved_and_feasible(model)
    println("Objective is: ", objective_value(model))
    println("Solution is:")
    for i in 1:n
        print("x[$i] = ", round(Int, value(x[i])))
        println(", c[$i] / w[$i] = ", profit[i] / weight[i])
    end
    chosen_items = [i for i in 1:n if value(x[i]) > 0.5]
    return chosen_items
end

solve_knapsack_problem(; profit = profit, weight = weight, capacity = capacity)
3-element Vector{Int64}:
 1
 4
 5

Мы видим, что в данном примере выбранные предметы (1, 4 и 5) имеют наилучшее соотношение ценности к весу.

Дальнейшие действия

Можно попробовать сделать следующее:

  • Вызовите функцию с другими данными. Что происходит при увеличении вместимости?

  • Что происходит, когда векторы ценности и весов разной длины?

  • Вместо создания двоичной переменной с помощью Bin мы могли бы написать @variable(model, 0 <= x[1:n] <= 1, Int). Убедитесь в том, что при такой формулировке находится то же самое решение. Что произойдет, если нам разрешат взять несколько штук одного предмета?