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:
Instance¶
We will use an instance stored in a file called knapsack.data.txt. This file reads
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\).