The Knapsack Problem Is All Around Us | Hacker News Reader

The Knapsack Problem Is All Around Us

smithsonianmag.com

128 pointsjgrahamc43 comments

What I find interesting about the knapsack problem, and the traveling salesman problem as well, is that they're fast to satisfy, but incredibly time-consuming to solve.

Once upon a time, I had a 4x8 sheet of small plastic parts to route out on a ShopBot. The naive layout from the vector drawing program was incredibly inefficient, and we ended up downloading a general-purpose traveling-salesman-solver written in Java.

It converged upon a dramatically better solution in a few seconds, and didn't really improve it in the next few minutes. So we just stopped it and ran the good-enough route, while leaving the solver running for two days out of pure curiosity.

Now, it was visibly not perfect, there were a couple skips where we could see a shorter way to do it. And it did eventually find those routes.

So if all you need is a reasonable route for your traveling salespersons, or an acceptably efficient packing arrangement for your shipping container, this is achievable and easy, if you're willing to leave that last 1-2% sitting on the table.

There is software like concorde that solves traveling salesman problems really fast and optimal: http://www.math.uwaterloo.ca/tsp/methods/opt/opt.htm

Still these type of problems are much trickier in practise, e.g. with time windows or even with multiple salesmen (then it is a vehicle routing problem).

For these problems still specialized software exists like jsprit (shameless plug!) and others:

https://github.com/graphhopper/jsprit/blob/master/docs/Other...

Interestingly related to my favorite approach at a solution: genetic algorithms.

You don’t know if you’ve converged on THE solution but you can know you have a solution.

> It converged upon a dramatically better solution in a few seconds, and didn't really improve it in the next few minutes.

Which in turn is, I think, a manifestation of the Secretary Problem.

https://en.wikipedia.org/wiki/Secretary_problem

I think this is more the general behaviour of heuristics. They are not guaranteed to give you the optimal solution as they are forced to 'converge'.

Humans have bin packing hardware in the visual systems. They very rapidly are able to find a pretty good solution to, say, stick stuff in the back of the car, but if you give them an abstract equivalent problem to solve it's as hard as anything else to solve.

First time I encountered this in the wild was years ago when my sister, who worked as auditor, approached me with a problem she hoped I could help her solve. She would often be given a spreadsheet full of values and she would have a target or aggregate value she was trying to match. Could I write a script to find the set of values from the spreadsheet that would add up to her target value?

Piece of cake I thought. After a couple hours of fruitless coding I realized some research might help. After a few more hours of googling, I finally figured out the name for this type of problem. Actually, I first came across the term "subset sum problem" which led to "knapsack problem". That led to an introduction to the concept of "nondeterministic polynomial time".

Eventually I found a diophantine algorithm someone had written in Rexx and managed to translate it to Python. It worked! Sorta. (I was surprised by how many different matching combinations a random set of numbers could generate for a given value.)

By the time I returned to my sister with my solution, I think she had found a Excel plugin that did it for her.

Subset sum is something that comes up quite often when bookkeepers need to reconcile accounts and there's some transactions missing. And indeed, the Excel solvers work well enough. These days I'm no longer surprised to find out that a classic selection problem has an Excel plug-in to solve it. There's even one for the multiple knapsack apparently.

You can create a solution for the knapsack problem using Excel Solver.

I imagine that MOST excel sheets are small enough for some variation of brute force to work. Lots of times a very rough approximation is a good enough place to start.

Reminds me a bit of when my dad asked me what was a good sort algorithm to use for his problem. When he asked I was mentally trying to weigh complexity to implement vs performance (he was a firmware programmer, it had to be in assembly).

Then I remembered to ask: how many things are you going to sort? He said 10. Always 10.

So, yeah. I didn't really even know the answer at the time.

I had to check 10! just to see how bad this could be. At 10 it's 3,628,800. Depending on how beefy the system is and how costly the operation is, pure brute force but simple might be good enough.

A nice solution that is easy to implement in Excel is using a sorting network, that sorts an array by doing the same exchanges for any input. Here I did it just for fun: https://imgur.com/a/qPugrJ6

wow that's pretty.

I think you could get by with ~50 checks if you just used selection sort.

I'm not sure what brute-forcing means in this context. Do you mean hard-coding every way to order 10 unique elements?

Brute force sorting would be generating permutations and checking if they're sorted. The non-deterministic version that uses random permutations is commonly called bogosort[0]

[0] https://en.wikipedia.org/wiki/Bogosort

The thread switched problems and I didn't catch that. The 10 factorial was trying out all possible packing solutions and filtering for only the ones that were 'valid' (probably with an added step of also keeping the best valid configuration).

I built the same thing for a logistics company, went down the same learning route too!

I've always thought of it as "the Skyrim problem", since it's precisely what you do in any RPG with tons of loot and finite carrying capacity

My mental algorithm is:

1) Set a value/weight ratio above which new items are picked up

2) If I run out of space and find something above that threshold, start dropping the worst-ratio'd items to make room

3) Raise the threshold accordingly

4) Repeat

Never thought to equate the two problems.. My algorithm has been: play until I get sick of the nonsensical inventory-management minigame (https://i.pinimg.com/originals/14/f1/e8/14f1e8a75445df681e72...) and then running player.setav CarryWeight 1500. Sometimes the solution is to acquire a bigger knapsack.

I don't think they're similar since knapsack has to consider volume/weight/value in practical applications. Value/weight is only two dimensions.

While this is usually a decent approximation, it's important to note this is not an optimal solution. For example:

Your bag can hold 10 kg. Item a weighs 10kg and is worth $10. Item b weighs 5kg and is worth $6.

Item b is more value dense, but picking up item a is optimal.

This is true, but in the Skyrim case nearly all items are small enough that a 'near optimal' answer is the indicated algorithm, with that extra space a more literal 'garbage collection' free zone.

In videogames, making the user GC isn't fun, and therefore reducing the number of GCs is more optimal than strictly solving the problem.

The counterexample is not apt; you can see by the phrasing of the original algorithm that items arrive in a stream over time. The goal is to maximize the value of the knapsack once the entire stream (of indefinite length) is consumed.

Item B is better than item A, even when you're just choosing from those two items, because more items will come along later to fill the space that item B leaves empty.

Here's a more explicit description of the problem space:

- Items arrive in a stream.

- Picking up an item is free.

- Overlooking an item is free.

- Discarding an item is expensive.

- Once an item is overlooked or discarded, it can't be picked back up.

What you're trying to do is finish the stream with the most valuable knapsack without having to go through too much discarding. An item that fills your entire inventory can never be worth picking up, unless it has an awesome value/space ratio, because picking up any other item guarantees that you have to discard that one.

Yeah, it's just a heuristic

If we're trying to reveal when we first really encountered and devoted serious thought (and by association, our age)...

I would call this the "Diablo I" problem.

Hear hear. I got a few sentences in and was like "Oh. The Diablo problem"

Where would I put this?

Right next to all the Stones of Jordan.

The Knapsack Problem is what originally led me down the path of Linear Programming, which is mind-blowingly cool. So cool, in fact, that in the 1960s, LP was used (along with other techniques) to solve a 49-city Travelling Salesman Problem. They didn't even have to check all possible solutions(!?) by using the principles of linear programming duality to prove that their solution was the most optimal.

My optimization class was one of the most interesting classes of my undergrad (industrial engineering). My professor was trying to explain why optimization was important.

"Optimizing your solution ensures someone else can't come into your industry, get the same suppliers and contract terms, and beat you"

We then went through an example for an oil refinery with different sources of oil (differing proportions of sweet and sour, and quantities available), refinery production constraints, and market prices for different end products. He showed the difference between a "naive manual optimization" and the mathematical optimal.

Ever since that class, I'm particular about what "optimize" means. Factories talk about optimizing many things at the same time (on-time delivery, profit, throughput on a machine, throughput on the bottleneck machine, minimizing labor). I can't tell you how many times I've said "pick one thing to optimize - you're not going to hit them all at once". You can make an objective function a weighting of all those factors, but they won't all be at their best possible values.

> I can't tell you how many times I've said "pick one thing to optimize - you're not going to hit them all at once".

What to optimize is actually probably one of the most interesting optimization problems out there. In a factory you always need to search for the bottleneck. That's why I think Kaizen is so important. Apply incremental optimization to the biggest issues and you will succeed.

Absolutely! My company makes thousands of unique specs with a constantly changing mix. The bottleneck is a moving target as business conditions change. It makes things more challenging for sure, but also keeps you on your toes.

I've met a few quantitative ChemE folks who did optimization for the chemical industry (exactly what you described, except not limited to petroleum products). They said it paid well, was modestly interesting, and they all work in ML at internet companies now.

I first encountered the Knapsack problem at a job interview. Intuitively I tried to solve it using what I later found out to be the greedy approximation algorithm [1], which proved unsuccessful to solve it for the interview's sample input.

Since I had not much time left I switched to an inefficient brute force approach, basically a test of all possible combinations, which wasn't well received by the interviewer back then since he was expecting a recursive dynamic solution [2].

When I started a blog last year I decided to revisit this problem while writing about complexity classes of problems, and tried to demonstrate how to translate a solver to the Knapsack problem for solving another NP-complete problem, the partition problem [3] ;)

It's indeed a very interesting and fun problem to tackle!

[1] https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approx...

[2] https://github.com/TCGV/Knapsack/blob/master/Tcgv.Combinator...

[3] https://thomasvilhena.com/2019/08/complexity-classes-of-prob...

Integer factorization is also reducible to Knapsack:

To factorize integer N invoke a Knapsack solver with knapsack size of log(N) and items of size logarithm of all prime numbers up to sqrt(N): [log 2, log 3, log 5, ...].

If N=pq (say p and q are prime) then log(N)=log(p)+log(q).

So from all possible items in the item set, only log(p) and log(q) will fill the knapsack as tight as possible leaving zero empty space in it.

Well, you mentioned integer factorization, that immediately leads me to RSA, which then leads me to PKI, and then leads me to cryptosystem. Combining it with the Knapsack problem, I was ultimately there for MH knapsack cryptosystem, which is unfortunately cracked [1].

[1]: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...

Probably one of the more practical libraries on the subject I have come across ... https://developers.google.com/optimization/bin/knapsack

Do you, or any other HN readers, know of any articles on how to solve the problem of working out the best Point of Sale checkout promotional offer?

If I have a set of retail promotional offers going such as:

Offer 1: buy two shirts from this set of shirts, and get a 50% discount

Offer 2: buy a shirt from this set of shirts, a jacket from this set of jackets, and a tie from this set of ties all for a set price of $99

Offer 3: all ties are on sale at half price

I'm trying to figure out if the google libraries linked above can be used to solve this problem, but I can't figure out how to convert the offers into values that can be used by the google library...

This was one of the first problems I tackled as a developer. My naive approach was to calculate the values of the offers independently, pick the top one, and then continue to try to apply remaining offers. Obviously, it's not the optimal solution, but I thought it worked well for the problem, because people like thinking they got a really big discount, even if their total savings might be less.

Sounds more like a Slope One variant, https://en.wikipedia.org/wiki/Slope_One

Autoplay video with sound, no thanks

Scheduling is a knapsack problem.

Reply on news.ycombinator.com