The knapsack problem example

Страница в процессе перевода.

This tutorial was generated using Literate.jl. Download the source as a .jl file.

The purpose of this tutorial is to demonstrate how to formulate and solve a simple optimization problem.

Required packages

This tutorial requires the following packages:

using JuMP
import HiGHS

Formulation

The knapsack problem is a classical optimization problem: given a set of items and a container with a fixed capacity, choose a subset of items having the greatest combined value that will fit within the container without exceeding the capacity.

The name of the problem suggests its analogy to packing for a trip, where the baggage weight limit is the capacity and the goal is to pack the most profitable combination of belongings.

We can formulate the knapsack problem as the integer linear program:

where is the capacity, and there is a choice between items, with item having weight , profit . Decision variable is equal to 1 if the item is chosen and 0 if not.

This formulation can be written more compactly as:

Data

The data for the problem consists of two vectors (one for the profits and one for the weights) along with a capacity.

There are five objects:

n = 5;

For our example, we use a capacity of 10 units:

capacity = 10.0;

and the profit and cost data:

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

JuMP formulation

Let’s begin constructing the JuMP model for our knapsack problem.

First, we’ll create a Model object for holding model elements as we construct each part. We’ll also set the solver that will ultimately be called to solve the model, once it’s constructed.

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

Next we need the decision variables representing which items are chosen:

@variable(model, x[1:n], Bin)

5-element Vector{VariableRef}:
 x[1]
 x[2]
 x[3]
 x[4]
 x[5]

We now want to constrain those variables so that their combined weight is less than or equal to the given capacity:

@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

Finally, our objective is to maximize the combined profit of the chosen items:

@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]

Let’s print a human-readable description of the model and check that the model looks as expected:

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

We can now solve the optimization problem and inspect the results.

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)   : 1.06597e-03
  Simplex iterations : 1
  Barrier iterations : -1
  Node count         : 1

The items chosen are

items_chosen = [i for i in 1:n if value(x[i]) > 0.5]

3-element Vector{Int64}:
 1
 4
 5

Writing a function

After working interactively, it is good practice to implement your model in a function.

The function can be used to ensure that the model is given well-defined input data with validation checks, and that the solution process went as expected.

function solve_knapsack_problem(;
    profit::Vector{Float64},
    weight::Vector{Float64},
    capacity::Float64,
)
    n = length(weight)
    # The profit and weight vectors must be of equal length.
    @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

We observe that the chosen items (1, 4, and 5) have the best profit to weight ratio in this particular example.

Next steps

Here are some things to try next:

Call the function with different data. What happens as the capacity increases?
What happens if the profit and weight vectors are different lengths?
Instead of creating a binary variable with Bin, we could have written @variable(model, 0 <= x[1:n] <= 1, Int). Verify that this formulation finds the same solution. What happens if we are allowed to take more than one of each item?