loinburger's Optimization Challenge: One-dimensional bin packing is NOT the same as three-dimensional bin packing

[loinburger]

The bin packing problem is where you have an infinite number of containers that hold up to N1 units (usually each container holds the same amount of stuff, but the problem can be extended to include multiple types of containers), and you've got a whole bunch of crap that's got different sizes N1[0], N1[1], N1[2], ... and you want to minimize the number of containers needed to hold the crap. (The problem is trivial if you're able to cut up your crap into smaller pieces of crap, but if you can't cut the crap then the problem is an NP Hard optimization problem meaning that it probably doesn't have a precise polynomial time solution which means that it's a difficult problem.)

A few years ago I worked at a logistics company that had an algorithm for estimating the number of boxes needed to ship a bunch of packages, so instead of a one-dimensional bin packing problem it was a three-dimensional bin packing problem. The one-dimensional bin packing problem has a nice heuristic called the best-fit-decreasing heuristic, where you sort your crap in order of largest piece of crap to smallest piece of crap and then you pack your crap in order, and you always put the next piece of crap in the container with the smallest difference between available space and size of crap. This is fast and gives a reliable approximate solution. The doofus who wrote our three-dimensional bin packing algorithm used this heuristic, using he box and package volume as the input. This doesn't work. Let's say I have a 12x12x12 box, volume 1728, and three 8x8x8 packages, total volume 1536; this guy's ****ty algorithm would say that you could put all three packages in the box, even though this is impossible (unless you crush or cut up the packages, which you probably don't want to do). Anyway, there are a couple ways to account for package dimensions in a three-dimensional bin packing algorithm, and because we just wanted a rough estimate I went with a fast but imprecise technique called the guillotine cut: when you put an 8x8x8 package in a 12x12x12 box then you slice the box into a 12x8x4 box, a 12x8x4 box, and an 8x8x4 box, none of which can hold another 8x8x8 package. (The source of imprecision is that in reality a 12x12x12 box could hold four 12x8x4 packages, but the guillotine cut heuristic would split up the remainder boxes such that you could only put in three 12x8x4 boxes.)

My next challenge is that the doofuses in QA didn't like my algorithm because according to their ****ty metrics the old algorithm gave better results, where "better" just means "put the packages in a smaller volume of boxes," not taking into account whether the estimate could actually be accomplished in reality (for example the old algorithm would say that you could put three 8x8x8 packages in a 12x12x12 box whereas my algorithm would say that you'd need three 12x12x12 boxes, so the old algorithm gave a "better" estimate that was also completely wrong). After a week of this crap the head of software development intervened and told QA to pull their heads out of their asses.

And thus ends the worlds best and worst copycat thread.

[giblets]

The majority of Apolyton posters are too drunk and/or stupid to read this.

[Lorizael]

You probably could have fit all those boxes in with time travel, or so says Dirk Gently.

[Kidlicious]

In a parallel universe you're the doofus.

[Ben Kenobi]

Interesting problem. I wonder how that would work in my workplace where we have deliberately standardized sizes of boxes to make this problem easier.

[loinburger]

This company had about six or seven different box sizes, but the package sizes were all over the place.

Some variants of the problem had orientation restrictions, for example a shipping container has a fixed orientation and a barrel of toxic sludge has a fixed orientation whereas the stuff we were shipping was light, non-toxic, and non-fragile (once we'd added packing peanuts) and so it didn't have a fixed orientation (it didn't matter if we shipped it rightside up, upside down, or sideways). There also isn't a good heuristic for splitting the remainder of a box after putting in a package (in general you either get one big remainder and two small remainders, or else you get three middling remainders). After preprocessing (e.g. sorting the packages) the program ran in linear time i.e. it was very fast, so I just used a random split with random orientations, ran the program a few dozen times concurrently, and picked the best result.

[loinburger]

Another important consideration is: what's the program's output? In my case all I wanted to do was estimate the number of boxes that our human packers would use so that we could tell the customer what their shipping cost would be, and then the human packers would use common sense to pack their boxes. In other scenarios a robot will do the packing, in which case the algorithm's output is the sequence of steps needed to pack the box.

There's a related problem in the lumber industry where you try to cut up a tree using the minimal number of cuts, since each cut takes time, generates waste, and damages the blades, and meanwhile there are only a few standard widths/lengths/thicknesses that you can produce.

[Kidlicious]

I gave this thread the appropriate number of stars.

[Aeson]

My next challenge is that the doofuses in QA didn't like my algorithm because according to their ****ty metrics the old algorithm gave better results, where "better" just means "put the packages in a smaller volume of boxes," not taking into account whether the estimate could actually be accomplished in reality

You should have designed an algorithm optimized to QA's assessment criteria. Like just outputting "all your packages fit into our smallest box [that's what she said]"

[loinburger]

That QA team was awful. They had no concept of where they fit in the big picture - their goal wasn't to make the software better, their goal was just to make people jump through hoops.

QA: Your software didn't pass this metric.
loinburger: Who wrote that metric and what does it mean?
QA: Nobody knows and nobody cares.

[Ben Kenobi]

Some variants of the problem had orientation restrictions, for example a shipping container has a fixed orientation and a barrel of toxic sludge has a fixed orientation whereas the stuff we were shipping was light, non-toxic, and non-fragile (once we'd added packing peanuts) and so it didn't have a fixed orientation (it didn't matter if we shipped it rightside up, upside down, or sideways). There also isn't a good heuristic for splitting the remainder of a box after putting in a package (in general you either get one big remainder and two small remainders, or else you get three middling remainders). After preprocessing (e.g. sorting the packages) the program ran in linear time i.e. it was very fast, so I just used a random split with random orientations, ran the program a few dozen times concurrently, and picked the best result.

IIRC, and this isn't my field, but wouldn't you have something like a 90 percent confidence after a particular period of time, beyond which further optimization was rather slow? It would seem sensible to me that you'd have a time cutoff for your algorithm but I guess it would depend on the process that you're using.

There's a related problem in the lumber industry where you try to cut up a tree using the minimal number of cuts, since each cut takes time, generates waste, and damages the blades, and meanwhile there are only a few standard widths/lengths/thicknesses that you can produce.

Yeah, that's what my dad had to design around.

[loinburger]

Depends on the domain. In general, numerical problems like bin packing often have good approximate solutions, while set/graph problems usually don't have good approximate solutions. By "good approximate solution" I mean something that is guaranteed to be within X% of the optimal solution, for example if you use a best fit decreasing heuristic on a one dimensional bin packing problem then you're guaranteed to get within something like 40% of the optimum, whereas most heuristics are just good rules of thumb but won't guarantee anything in terms of the errors that they produce.

[loinburger]

The worst co-worker I ever had was a senior front end developer for a website that tried and failed to be a thing. Users could embed Youtube videos in their posts or messages or whatever, sort of like here or on Facebook or whatever. What management wanted is for users to be able to upload their videos to Youtube from our website and then we'd embed the video in their posts or whatever, like if apolyton had an "upload+embed video" button in the post form. So my idiot doofus moron ****** co-worker tells me that I have to write some Java code that will let users upload videos to the company's Youtube account (using OAuth, if you know what that is). Oh, and a couple of years prior he'd written some awful Ruby code to do this as a proof of concept thing, and I had to write my code to do the exact same thing or else I'd be insulting his code or something (even going so far as to stipulate that I needed to use version 2 of an API instead of version 3, just because his code used version 2).

You may have already spotted the problem here. What are random people on the internet going to do if you let them upload anything they want to a company's Youtube account? For example, what do you think would happen if Aeson said "hey guys, I've written some code that will let you upload anything you want to Aeson's Personal Youtube Account and then we'll embed that video in your post, surely nothing can go wrong with this plan"? Yeah, Aeson's account would get banned for excessive dickgirling within an hour. The same thing was going to happen to our company's Youtube account, and this pickledick was too arrogant to realize it. I pointed this out to him, but was shot down. So I found a blog written by the Youtube API team where they said "for the love of god, don't use OAuth to let random people upload dickgirls to your company's Youtube account, instead you should use Youtube Direct which is faster and safer and easier and free," and I showed him the blog, and it didn't make a dent. I tried explaining the problem to the CTO, but either I'm really bad at explaining things or else the CTO was really dumb or else this senior developer had compromising photographs of the CTO felching a goat or whatever, because he didn't understand what the problem was.

At this point the best case is that our account would get spammed with copyrighted porn within an hour of my awful code going on the production server, resulting in our company's Youtube account getting banned. This would be a bit embarrassing, but we'd recover (ideally sans one senior front end developer). The worst case would be for my code to survive for several months before our company's account was porn-banned, which would probably kill the company. So, I was trying to find ways to convince Redditors to spam our website or something so that it would die sooner rather than later, all without leaving a paper trail so I wouldn't get fired. Fortunately, the front end guy couldn't figure out how to set up our OAuth codes or something, and so the project died without my having to kill it.

[Ben Kenobi]

By "good approximate solution" I mean something that is guaranteed to be within X% of the optimal solution, for example if you use a best fit decreasing heuristic on a one dimensional bin packing problem then you're guaranteed to get within something like 40% of the optimum, whereas most heuristics are just good rules of thumb but won't guarantee anything in terms of the errors that they produce.

See if understand this correctly, you mean 40 percent in terms of packing space? Umm, wow. That's a lot of money. Shows you how much a clue about this that I have. Only thing I've had to deal with anything like this was some packing things in Physics and lattices. Thanks for the post loinburger.

[loinburger]

A couple years prior to thar we were writing path finding algorithms for Lego robots while working for the airforce. The idea is that one contractor would make robot radio relays and another can tractor would make the software for them, meanwhile me and my fellow civil servants made the baseline hardware using Legos and also the baseline software to test against. This was an np-hard graph connectivity problem, because the purpose of the robots was to configure them in a network that would survive if a few robots were stepped on or blown up but that also maximized the radio coverage; because it was a graph problem we didn't have a good approximate solution, and we also had a very tight resource constraint in the robots' batteries