Solving a knapsack problem with HiGHS

Problem Definition

Given a set of \(n\) items, the goal is to select of subset of items to be put in a knapsack of limited capacity. Each item has a weight (the amount of space it takes in the knapsack) and a profit (the value of the item). The goal is to maximize the total profit of the items in the knapsack, while not exceeding the capacity.

For each item \(j\in\{1,\dotsc,n\}\), we let \(w_j\) denote its weight and \(p_j\) be its profit. The capacity of the knapsack is noted \(C\).

The knapsack problem can be formulated as the following binary linear problem:

\[\begin{split}\begin{align*} \max_{x} \quad & \sum_{j=1}^n p_j x_j \\ \text{s.t.} \quad & \sum_{j=1}^n w_j x_j \le C, \\ & x \in \{0,1\}^n. \end{align*}\end{split}\]

Instance

We will use an instance stored in a file called knapsack.data.txt. This file reads

5
40 50 100 95 30
2 3.14 1.98 5 3
10

The first line contains the number of items \(n\). Then, the following line contains the profits of each item, \(p_j\). The third line contains the weights of each item, \(w_j\). Finally, the last line contains the capacity of the knapsack, \(C\).

Implementation

//
// Created by henri on 06/04/23.
//
#include <iostream>
#include "idol/mixed-integer/problems/knapsack-problem/KP_Instance.h"
#include "idol/modeling.h"
#include "idol/mixed-integer/optimizers/wrappers/HiGHS/HiGHS.h"

using namespace idol;

int main(int t_argc, const char** t_argv) {

    const auto instance = Problems::KP::read_instance("knapsack.data.txt");

    const auto n_items = instance.n_items();

    Env env;

    // Create model
    Model model(env);

    auto x = model.add_vars(Dim<1>(n_items), 0, 1, Binary, 0., "x");

    model.add_ctr(idol_Sum(j, Range(n_items), instance.weight(j) * x[j]) <= instance.capacity());

    model.set_obj_expr(idol_Sum(j, Range(n_items), -instance.profit(j) * x[j]));

    // Set optimizer
    model.use(HiGHS());

    // Solve
    model.optimize();

    std::cout << "Objective value = " << model.get_best_obj() << std::endl;

    std::cout << "Solution:\n";
    std::cout << save_primal(model) << std::endl;

    return 0;
}