Use IA for 2D nesting, they said ...

Well, I have gone down the rabbit hole of applying IA to solve free-form 2D nesting problems, but the results weren't what I expected. However, I have learned a lot of things in the process, and created some software you might find useful, such as this packer, which has nothing to do with AI (initially), but it is a basic Left-Bottom First packer. The AI part comes in when you provide it with a somewhat "intelligent" parts sequence. And there, my friend, is where many different attempts and hours of AI training went.

Let me explain what I did and how I did not accomplish much in the process: I had a collection of 2D part geometries and the results of a professional nesting tool applied to them. I thought I could use that to teach a model how to tell a dumb LBF to do better by either providing the optimal part sequence and/or rotation angle. I used different approaches to that, but I underestimated my ability to mess things up, so I ended up with six different transformers, one of them even including vision capabilities, that provided a relatively small edge over my relatively simple approach. I used not only Supervised Learning, but also Reinforcement Learning, but the main problem was that I failed to understand some of the approach's shortcomings, as I trusted my data to an AI agent that misinterpreted the dataset. Unfortunately, I learned about this subtle detail long after quite some work was already done: My dataset contained the geometry of the parts and how they were placed on various bins, but the order of the parts on each sheet, although it was numerical, was just an index number completely unrelated to the placement order. As you might expect, AI is no different from other algorithms subject to GIGO. 
 

So I ended up with some beautiful transformers that spit out sequences that make nesting not particularly good, though these same models did not improve when retrained after fixing my error and providing a somewhat educated guess about the actual bin filling order for my dataset. Adding some stochastic variations to these sequences and keeping the best results helped to improve a bit, but the real killer was to try what I called the stochastic shotgun, that will consider a few of the most common sequencing heuristics for LBF packing (longest side first, largest area first, and so on) and them applied a bit of stocastic variation to them, keeping the best result. Building this last idea took just a few minutes and beat the crap out of all the AI-based models I created before (that took weeks). However, the result was still far from commercial nesting software.

Just use open-source

Well, actually, that was part of the solution, and I had encountered it before, but since I knew nothing about Rust, I did not explore it enough. For most of the work above, I used my own C++ LBF packer, but later I switched to jagua-rs LBF, which is a high-performance, open-source packer. I also knew the same coder had created Sparrow, and I learned that it was a state-of-the-art Strip Packing Problem optimizer. Unfortunately, what I wanted was not an SPP but a BPP (bin packing problem) solver/optimizer. 

But then I thought to myself: Cannot I build a decent BPP based on an SPP that I know is already pretty good? Well, it turns out that you can, and so I did, reaching sometimes up to 87% bin utilization.