6 ms·
Algorithmic fitting of Japanese candy
- reedf1 2y agoIf this is presented at programmers, why not just say "Here is a cool practical case of a knapsack/bin packing problem."? The article seems to be intentionally avoiding this.
- jerkstate 2y agoThat's what I thought too, then I remembered when I first discovered linear optimization, when solving a practical problem like this (I used Python PuLP, and coin-or as the backend). Not every programmer went to college for computer science. Anyways, I really liked the animations.
- carom 2y agoIf anyone is facing a problem like this today, check out or-tools [1]. Bin packing is one of their exemplar problems. 1. https://developers.google.com/optimization/introduction https://developers.google.com/optimization/introduction
- jerkstate 2y agoI started with or-tools, early on I tried changing the backend and found that there were details in the problem definition that needed to be changed when switching backends. Not knowing a ton about the problem space, I thought that this inflexibility could get me into trouble later, so on the advice of a colleague I switched to PuLP, which does not require any code changes to try different solver backends, e.g. glpk or coin-or (or gurobi, a commercial solver which is supposedly very fast, although my problem did not need it)
- bemmu 2y agoFair enough. I hadn't personally encountered knapsack/bin packing problems before, so it wasn't immediately obvious this fell into such a category. Just thought I'd blog my practical encounter with the problem as I was exploring it.
- gwern 2y agoThink of it as a "you could have invented binpacking algorithm X too" post.
- zimpenfish 2y ago> "How hard could it be?" Having worked on something that required "optimal" box packing for deliveries[1], the answer is "very, and then some (and that was with the help of that fancy USMIL pallet-packing algorithm, IIRC)". [1] They wanted to use the smallest possible box plus some other constraints like "product X cannot have anything on top of it", etc.
- freeone3000 2y ago“A few minutes” seems… reasonable? Like, you can let it run for a few hours on a list, come back in the morning, see which combos work. You ship it out once a month, it’s gotta be quicker than testing them by hand.
- 0xTJ 2y agoIf I'm reading it right, that's a over a minute for only 4 candies.The "boxes" there isn't a per-customer shipping box, but the virtual boxes representing candies.
- freeone3000 2y agoYes, understood, but you’re going to ship out a maximum of fifteen or so candies or the economics doesn’t work. Even with really awful scaling, the fact you have an entire month to prepare and send the next shipment gives you a lot of computing time.
- financltravsty 2y agoNow parallelize it lol
- 0xTJ 2y agoThat's not feasible. Have a look at the equation at the bottom of that page. With 15 candies, this grows to the order 10^41.
- Cthulhu_ 2y ago(2016). Also posted 8 years ago, 50 comments: https://news.ycombinator.com/item?id=12973964 https://news.ycombinator.com/item?id=12973964
- madaxe_again 2y agoUsed to provide ecommerce solutions, from purchase through to despatch and beyond. A frequently asked for feature was box-packing - clients would complain that their packers would chuck something tiny in a huge box, use loads of packaging, and still manage to have the thing damaged on arrival due to shaking about in there. So we implemented the feature. It worked great. Clients bought it. Literally nobody used it, as humans inevitably decide they know better. Instead, we just ended up with clients reporting “the boxer told our packer to put a stick of gum in a 1m2 palletised delivery!”, as that was what the packer would report, when it had done no such thing, so all we had done was move the point of blame from minimum wage warehouse workers to ourselves. We withdrew the feature.
- zimpenfish 2y ago> Literally nobody used it, as humans inevitably decide they know better. Sadly when I was doing this, the packers were great - they'd follow the instructions from the service happily. Except the service itself would frequently output "garbage" because the product people refused to give me a timely feed of product dimensions etc.
- madaxe_again 2y agoYeah, that was the other half of the equation - nobody wanted to provide the necessary volumetric data at several clients, and the expectation was that it would somehow… just work. We even tried to make it really easy via an exception based workflow, sanity checking for wrong units etc., but nah. Whole thing was a boondoggle unlike anything else - folks had no problem rearranging their entire warehouses to come up with more efficient pick routes, but measuring boxes was a bridge too far.
- poopcat 2y agoI loved how you used your skills to address a ~seemingly~ simple problem. The explanation was also cool
- resolutebat 2y agoA friend of a friend worked at NASA on essentially this, except that instead of fitting Japanese candy in a box, they were fitting cargo into the Space Shuttle. As you can imagine this introduces a whole slew of new complications, notably mass distribution and that things must be unloaded in a certain order.
- ljlolel 2y agoThis top comment is very similar to this other comment https://news.ycombinator.com/item?id=12975858 https://news.ycombinator.com/item?id=12975858
- lkdfjlkdfjlg 2y agoI think you just exposed someone's alt account.
- deleted 2y ago[deleted]
- ljlolel 2y agoOh I thought it was maybe a bot
- lkdfjlkdfjlg 2y agoAlso plausible. When something gets reposted, repost previous popular comments. Farming technique popular on reddit.
- saagarjha 2y agoMaybe they have the same friend of a friend
- GuB-42 2y agoNot only that, but the optimal solution may involve packing at an angle, the most obvious being fitting a candy bar that is too long across the package, in diagonal. If you look at some of the best square packings, the results can be surprisingly messy[1], and few of them have been proven. It is clear that optimal algorithms are out of the question, which is the conclusion of the article, even with the constraints of orthogonal placement of simple boxes. In fact, in real life, when taking into account packages that are not simple boxes, items that can be squished a little and those that shouldn't be, etc... I wouldn't be surprised if humans were actually better than computers. [1] https://kingbird.myphotos.cc/packing/squares_in_squares.html https://kingbird.myphotos.cc/packing/squares_in_squares.html
- fuzzythinker 2y agoThe linked page doesn't link back to its parent page which has dozens more shape-in-shape packages. https://erich-friedman.github.io/packing/ https://erich-friedman.github.io/packing/
- crazygringo 2y agoI loved reading this, because it feels like it's only the start. Now I'm really curious (and if anyone can point me to resources) -- 1) Surely there are a bunch of more obvious optimizations, like don't place candies where they would fall because of gravity and nothing supporting them underneath, or always placing the candies in order of largest to smallest, and ignore anything symmetrical or rotationally equivalent to a previous solution... and how much would this reduce the search space? 2) What is the actual metric for fitting in a box "in the best way"? That lower layers are as full as possible before adding upper layers? That shifting of contents is minimized while upright? That shifting of contents is minimized in any orientation? To minimize small gaps and try to make non-used space as contiguous and compact as possible? Or is the box size arbitrary and the goal is to find the minimal box volume? 3) Is there separately a metric for "good enough"? Should the metric not to be to fit in a specified box, but rather find the smallest box of a set of standard box sizes that can fit the candies, with any arbitrary arrangement rather than a "best"? Is this a much easier problem, or is it just as hard or harder? I feel like Amazon must have solved this for all practical purposes. I suspect that it would work well and be fast if you simply place items in order from largest to smallest by volume, filling from bottom to top, quickly determine which box sizes are too small, and then just find the first arrangement that works. Curious if there are pathological cases where that wouldn't work?
- zimpenfish 2y ago> I feel like Amazon must have solved this for all practical purposes. Given that I have, more than once, received a huge box from Amazon holding an extremely small item, I don't think they have unless they're really bad at packaging stock management and had to stuff things into whatever they had available? (To be fair, it has been infrequent but then I'm just one person and I don't believe I'm a statistical anomaly which suggests that at Amazon scale, it's happening thousands of times a day.)
- crazygringo 2y ago> unless they... had to stuff things into whatever they had available I assume that's exactly what happened. You don't have to be "really bad at packaging stock management", you just have to have a supplier that is late delivering certain box sizes on a certain day. Late fulfillment is far more common than late ordering when it comes to automated systems like these. (And the more days' worth of box stock you try to maintain in case box delivery is late, the more it costs you in warehousing. So occasionally getting a box too big is probably going to be economically optimal, when the box suppliers aren't completely perfect in supplying on time.)
- alexpotato 2y agoWhile working at a Big Bank, a new policy was instituted where we had to fill out time sheets. We also had to allocate our "budgeted time" into these timesheets (Regardless of what we actually did). It ended up being a bin packing problem that no one actually did till I wrote a script to do it for me. This in turn led to some interesting conversations with my manager and the head of Capital Markets and Banking's CFO. You can read more details about it here: https://twitter.com/alexpotato/status/1296856648435326976 https://twitter.com/alexpotato/status/1296856648435326976
- Strang 2y agoFYI, Twitter links aren't really reliable any more. When I click that link, I see just one message promising a thread but no thread.
- nayuki 2y agoI see all the <canvas> elements are blank because of JavaScript code errors.
- bemmu 2y agoFixed it.
- vslira 2y agoA couple of months ago I tried using z3 to create an itinerary for my honeymoon. It seemed like a very straightforward implementation of a TSP with a few extra restrictions. It's 2024 and I had an M2 - which is basically alien tech for the period when these problems started being solved - so I figured that in 5 minutes' time I'd have the perfect walking trip in Rome. To quote TFA, how hard could it be? The whole story might become a blog post some day, but the punchline is that Moore's law ain't got nothing on NP-hard problems
- tredigi 2y ago> Moore's law ain't got nothing on NP-hard problems Fun fact, exponential growth is exactly what you need against NP-hard problems.
- bubblyworld 2y agoMoore should go collect his millenium prize =P
- lkdfjlkdfjlg 2y ago> Hey I know, I'm a programmer, I'll just write an algorithm to do it for me. How hard could it be? Hey I'm a programmer, I'll tell a computer to brute-force it. To someone who only has a hammer everything looks like a nail.
- deusum 2y agoThis would be a fascinating Code Golf challenge.
- bencyoung 2y agoI once had a financial bin packing problem at a previous company. Rather than going down a dynamic programming route which was highly exponential, we decided to use a combination of monte-carlo simulation and a very basic genetic algorithm to try and find a solution. This made use of the fact that we could try solutions extremely quickly, and also timebound the overall time taken (something that was important as we had a limited time window). We'd still be able to run 1-2e6 different approaches in under a second. Although we couldn't guarentee the "best" approach possible we generally came up with something good enough, often in many orders of magnitude less time. A good example of the performance improvements you can make when you move from thinking of what the best solution is to what a "good enough" one is.
- cypherpunks01 2y agoWouldn't using a constraint programming solver like CP-SAT be overall a faster way to do this? Then one would only have to specify the constraints and let the solver optimize a solution, rather than trying to write a customized packing problem algorithm from scratch. I'm sure it'd be fun, but when trying to best solve a real-world problem, I'd think using well-researched tools would be the quickest and safest way to go.
- Minor49er 2y agoI stumbled across a PHP library that aims to solve this kind of thing https://github.com/dvdoug/BoxPacker?tab=readme-ov-file#boxpacker https://github.com/dvdoug/BoxPacker?tab=readme-ov-file#boxpa...
- jiggawatts 2y agoThe author mentioned 10^20 combinations taking millions of years, but a modern server GPU can put out 10^15 computations per second (about a petaflop), assuming you use them in FP16 mode. Keep in mind that 65K divisions of a box one meter per side is 15 micrometers! This means that roughly speaking, it would be possible to brute-force through all possibilities in about 10^5 seconds, which is just one day. It helps that this type of algorithm is almost all computation with very little data transfer to and from main memory, and is "embarrassingly parallel". Some light optimisation such as utilising symmetries to reduce work, combined with multiple GPUs in parallel could bring this down to hours or even minutes. It would be a fun thing to cloud-host, spinning up spot-priced GPUs on demand. Similar brute-force tricks can be applied to other NP-hard problems such as optimising electronic circuit board wiring, factory floor planning, etc... The ridiculous amount of compute we have available to us in a GPU reminds me of this quote from Stargate Atlantis: JEANNIE: The energy you'd need would be enormous to the point of absurd. McKAY: Absurd we can do. We have something called a Zero Point Module which essentially does what we're attempting on a smaller scale -- extract energy from subspace time.
- saagarjha 2y agoThe program taking a million of years is hyperbole but spinning up a GPU cluster for this can't possibly be an effective use of time.
- jiggawatts 2y agoThat's your intuitive take on it, because it feels wasteful somehow, but it boils down to simple dollar terms. If for a few hundred dollars worth of compute you can make a box smaller, that might save the company hundreds of thousands of dollars over years.
- saagarjha 2y agoThis seems very unlikely considering how people would have different things they wanted packed
- MattFreeman123 2y ago[flagged]