A multi-criteria approach to approximate solution of multiple-choice knapsack problem (Q721960)

Given sets \(N_{1},\dots, N_{k}\) of items with cardinalities \(|N_{i}|=n_{i}\) for \(i=1,\dots,k\), profits \(p_{ij} \geq 0\) and costs \(c_{ij} \geq 0\) for \(i=1,\dots,k\), \(j=1,\dots, n_{i}\), the multiple choice knapsack problem (MCKP) consists in choosing exactly one item from each set \(N_{i}\) so that the total cost does not exceed a given bound \(b \geq 0\) and the total profit is maximized. The authors present a method to find approximate solutions to the MCKP which consists in transforming the MCKP into a bi-objective optimization problem (BP), a linear scalarization of which, (BS(\(\lambda\))), allowing to be solved explicitly by a closed-form formula. The method is tested on large-scale, uncorrelated and weakly-correlated problem instances, and the results show that the optimal value of the MCKP is approximated by an accuracy comparable to that of the greedy algorithm.