19
$\begingroup$

I am wondering what are the fastest ways(faster than classical dynamic programming) to solve the knapsack problem (to optimality) with $n$ items when $n$ is nearly equal to $10000$ ?

Apart from classic local search, is there any heuristics that are efficient ? Edit: I asked for both exact and approximation methods

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Hi Best_fit, I'm a bit puzzled (and judging from the comments below some other readers are as well) whether you need the optimal solution (in this case you can't use heuristics or approximation algorithms as they do not give you a optimality certificate) or whether "near optimal" solutions are ok? $\endgroup$
    – JakobS
    Nov 20, 2019 at 15:35
  • $\begingroup$ Hi, I am asking for the two types of methods in fact, both approximate and exact. $\endgroup$
    – Joffrey L.
    Nov 20, 2019 at 17:50

3 Answers 3

Reset to default
19
$\begingroup$

For the knapsack problem, you just use the Pisinger's code. It implements an exact algorithm, it is the fastest algorithm known in the literature, and it is open-source: http://hjemmesider.diku.dk/~pisinger/codes.html

Improve this answer
$\endgroup$
2
  • $\begingroup$ Which of the algorithms in the linked page are you referring to? $\endgroup$
    – David M.
    Nov 26, 2019 at 4:20
  • $\begingroup$ The COMBO algorithm is the standard problem. The rest are variation of it, more details are in the referenced papers/Pisinger's (et al) book on Knapsack Problems. $\endgroup$
    – Tue Christensen
    Nov 26, 2019 at 6:26
9
$\begingroup$

A comprehensive comparison of different approaches to solving the knapsack problem is given in the recent paper1 by Ezugwu et al., where the authors compare the performance of the following approaches both in small size and large size problems:

  1. Genetic algorithms,
  2. Simulated annealing,
  3. Branch and bound,
  4. Dynamic programming,
  5. Greedy search algorithm,
  6. Hybrid genetic algorithm-simulated annealing

This paper can be a good start point for your search.

(1) Ezugwu, Absalom E., et al. "A Comparative Study of Meta-Heuristic Optimization Algorithms for 0–1 Knapsack Problem: Some Initial Results." IEEE Access 7 (2019): 43979-44001.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Because @Best_fit is interested in exact methods, points 3 and 4 seem most relevant. After checking out the paper, it is not yet clear to me if these algorithms are really used by Ezugwu et al. to find optimal solutions. This is because positive optimality gaps for both BB and DP are reported in some of the tables. $\endgroup$
    – Kevin Dalmeijer
    Nov 20, 2019 at 12:02
  • 1
    $\begingroup$ @KevinDalmeijer the authors claimed that 6.approach is efficient and I mentioned in my answer that “this paper can be a good start point” to search for the actual answer. Also I tried to emphasize that some heuristics perform good in big size problems (as stated in the paper and asked in the question). But thank you very much for your effort in checking the paper and answer in detail. $\endgroup$
    – Oguz Toragay
    Nov 20, 2019 at 14:27
  • 1
    $\begingroup$ I completely agree that this comparative study is a good starting point. I only wanted to point out a peculiarity that I found while reading it :) $\endgroup$
    – Kevin Dalmeijer
    Nov 20, 2019 at 14:51
2
$\begingroup$

You don't give that bit of information, but you might be able to use a far more efficient algorithm when knapsack size (let's call it $S$) is small enough (small enough to create an array of each possible value you could get) and all the items have positive (or zero) weight.

For example, if maximum knapsack size is $10^7$ units, you could easily create an array of that size.

This way you go from $O(2^n)$ to $O(S\cdot n)$. I believe that would be called memoization (I can paste my implementation if that's what you're looking for).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.