Algorithm for optimal cutting of linear materials

Question

There is a list of blanks with their lengths. There is a list of parts with their lengths, which should be obtained from blanks. The task is to calculate the most optimal distribution of parts on the workpieces so that the remnants are minimized.

The very first thing that comes to mind is a banal enumeration of all possible combinations and the search for minimal waste. But, the number of blanks and the number of parts can be quite large. And when iterating, the number of combinations will grow exponentially.

Probably who faced, whether there are any more effective decisions, than usual search.

It seems to me that there is a fairly simple math when sorting through, you can try them.
Consider the amount of waste and, if the previously reached minimum is exceeded, stop searching through this branch to stop - the solution will not be better than the one found earlier.
@KiTE, by the way, if it's not a secret, is it something that is a university test or is it such a problem in real life?)
If memory does not change you need to look in the direction of "linear algebra" .
IMHO in the 30s for someone optimizing the cutting of plywood someone Kantorovich got the Nobel Prize.
Nobel 1975, "Pioneer and one of the creators of linear programming."
I advise you to google "np complete tasks", this will give you a base for solving this type of tasks.
IMHO, if you have not encountered similar problems before, it will be difficult to solve it (even if you are of course not a genius of mathematics).
As far as I know, there are 2 ways to find a solution: 1) complete enumeration of all the options - then you will certainly be able to choose the best (time consuming) 2) partial enumeration of options, the search continues until the obtained results meet the criteria.
eg: you have a real output of blanks from the material 80%, you are satisfied with any solution to the problem where% is higher

Costantino Rupert Costantino Rupert 22.6k one 28 52 · Accepted Answer · 2012-02-18T20:23:45

This problem in the English-language literature is called Cutting stock problem and is one of the varieties of the backpack problem when there are several backpacks.

It can be solved in different ways - by dynamic programming or approximate heuristics.

The heuristic solution you, apparently, does not fit (you need an exact solution) , so you should look in the direction of the dynamics.

Many thanks for the tip! I will understand and train English :) - KiTE

Answer 2 · 2012-02-18T17:49:37

The task is not easy, but we must understand that the sum of the residues of the blanks in any selection of blanks to parts in any case will be the same.

Addition:

Well, because anyway you have to deal with each element of the arrays (blanks and parts), then you can simply find the minimum remainder for each part by running through all the blanks and finding the remainder for the current part. And so for every detail. If there are too many details (so many!), Then why don't you just use such a beautiful thing as flows?

@alexz, on the one hand, he is right (the area of the details of the permutation will not change, right?), on the other hand, this is irrelevant to the task.
@Asen, meaning the arrangement in such a way that the parts are as tight as possible and the remainder is not a bunch of 1x1 squares, but a large piece of material.

Algorithm for optimal cutting of linear materials

2 answers 2

More articles: