Greycon is happy to announce a significant breakthrough in the transformation heuristics, used inside X-Trim to reduce pattern count without affecting waste.

As outlined in the paper that can be downloaded from here, on a testbed of 120 problems, the new heuristic, called KBP, reduced the total number of patterns by 4.2% using (only) 0.24 seconds processing time per instance. The number of reductions in X-Trim will be a bit higher than this, thanks to synergistic effects with other heuristics. The savings are more noticeable on the larger problems, on the smaller ones the impact is not so big.

We had a small puzzle constructed to illustrate the new algorithm:

The question is how to re-arrange the tiles (reels) so that two of the rows are identical, i.e. only use 5 patterns. The solution can be found on page 6 of the attached paper.

Greycon is applying for a US patent for this new algorithm, so, on legal advice, we could not make this algorithm available prior to filing. The application has now been filed and the new algorithm is available automatically via the Web Update function in version 8.6:

No settings need to change in X-Trim in order to take advantage of this new algorithm.

As the corresponding paper demonstrates, the idea behind KBP started as something that was relevant to only a small set of problems, but gradually, over the last 8 months, we have been able to generalise it. It is no panacea (there remains room for further improvement), but clearly is an important step in the path to fewer patterns.