Knapsack Problem (HiGHS)

Problem Definition

We consider the Knapsack Problem (KP). Given a set of \(n\) items, each of which having a weight and a profit, the goal is to select of subset of items such that the total weight does not exceed a given capacity and the total profit is maximized.

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

We model the KP with the following binary linear program:

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

Implementation with idol

In this example, we show how to model the Knapsack Problem with idol and how to solve it using the HiGHS solver.

//
// Created by henri on 06/04/23.
//
#include <iostream>
#include "idol/problems/knapsack-problem/KP_Instance.h"
#include "idol/modeling.h"
#include "idol/optimizers/mixed-integer-optimization/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, "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 << save_primal(model) << std::endl;

    return 0;
}