1-dimensional nesting algorithm

Question

What is an efficient algorithm for embedding 1-dimensional lengths into predefined stock lengths?

For example, if you need steel bars in the following quantities and lengths,

• 5 x 2 meters
• 5 x 3 meters
• 5 x 4 meters

and they can be cut off from 10 meter bars. How could you design a template for cutting 10 mm bars to use the minimum number of bars?

In addition, how could you include several stock lengths in the algorithm?

---

I did not have much time to work on this, so I will write how I decided it. I hope this will be helpful to someone. I am not sure if it is ok to answer my own question. The moderator can change this to answer if it is more appropriate.

First, thanks to everyone who answered. This indicated an appropriate algorithm; cutting tool problem .

This post has been helpful; Calculation of the list of sections with the least amount of waste without waste .

Ok, to the solution.

I use the following terminology in my solution:

• Stocks: the length of the material to be cut into smaller pieces.
• Cut: the length of the material cut from the warehouse. multiple cuts can be taken from the same warehouse.
• Waste: the length of the material left in stock after all cuts.

There are three main steps to solving the problem:

• Identify all possible cut combinations
• Determine which combinations can be taken from each warehouse.
• Find the perfect combination of cutout combinations.

Step 1

With N cuts, there are 2 ^ N-1 unique cutout combinations. These combinations can be represented as a binary truth table.

Where A, B, C are unique sections,

ABC | Combination ------------------- 0 0 0 | None 0 0 1 | C 0 1 0 | B 0 1 1 | BC 1 0 0 | A 1 0 1 | AC 1 1 0 | AB 1 1 1 | ABC 

And for a loop with some bitwise operators, you can use it to quickly create groupings of each cutout combination.

This can be time consuming with large N.

In my situation, there were several instances of the same section. This led to duplication of combinations.

 ABB | Combination ------------------- 0 0 0 | None 0 0 1 | B 0 1 0 | B (same as previous) 0 1 1 | BB 1 0 0 | A 1 0 1 | AB 1 1 0 | AB (same as previous) 1 1 1 | ABB 

I was able to use this redundancy to reduce the time for calculating combinations. I grouped duplicate abbreviations and calculated unique combinations of this group. Then I added this list of combinations for each unique combination in the second group to create a new group.

For example, with the abbreviations AABBC, the process is as follows.

 AA | Combination ------------------- 0 1 | A 1 1 | AA 

Call this group X.

Add X to unique instances of B,

 BBX | Combination ------------------- 0 0 1 | A | AA 0 1 0 | B 0 1 1 | BA | BAA 1 1 0 | BB 1 1 1 | BBA | BBAA 

Call this group Y.

Add Y to unique instances of C,

 CY | Combination ----------------- 0 1 | A | AA | B | BA | BAA | BB | BBA | BBAA 1 0 | C 1 1 | CA | CAA | CB | CBA | CBAA | CBB | CBBA | CBBAA 

In this example, 17 unique combinations are obtained instead of 31 (2 ^ 5-1). Saving almost twice.

Once all combinations are identified, it's time to check how it fits into the stock.

Step 2

The goal of this step is to compare the cutout combinations defined in step 1 with the available stock sizes.

This is a relatively simple process. For each cutting combination

  calculate the sum of all cut lengths. for each item of stock, if the sum of cuts is less than stock length, store stock, cut combination and waste in a data structure. Add this structure to a list of some sort. 

This will result in a list of valid combinations of nested abbreviations. There is no need to store waste, as this can be calculated by the length of the cut and the length of the hopper. However, waste storage reduces the processing required in step 3.

Step 3

At this stage, we will determine the combination of cuts that produces the least waste. This is based on the list of valid sockets generated in step 2.

In an ideal world, we calculate all the possibilities and choose the best. For any nontrivial set of cuts, it would take forever to calculate all of them. We just have to be satisfied with not the optimal solution. There are various algorithms for performing this task.

I chose the method that will look for the nest at the lowest cost. This will be repeated until all reductions are taken into account.

Start with Three Lists

• cutList: a list of all required cuts (including duplicates).
• nestList: The list of nests generated in step 2. It is sorted from the lowest waste to the highest waste.
• finalList: Initially empty, this will keep a list of cutout combinations that will be displayed to the user.

Method

 pick nest from nestList with the least waste if EVERY cut in the nest is contained in cutList remove cuts from cutList copy this nest into the finalList if some cuts in nest not in cutList remove this nest from nestList repeat until cutlist is empty 

Using this method, I was able to get a total spend of about 2-4% for some typical test data. I hope that at some point I will move on to this problem and go on to implement the Delayed column generation algorithm. This should give better results.

Hope this helped someone else with this issue.

David

Answer 1

Actually there is an even more specific problem: stock problem :

The problem of cutting material is the problem of optimization, or more specifically, the integer linear programming problem. It arises from many industrial applications. Imagine that you work in a paper mill and you have several rolls of paper with a fixed width, waiting to be cut, while different customers want the number of rolls of different sizes of width. How are you going to cut the rolls so that you minimize waste (left)?

The reason that this is better than the problem of packing the basket is because you are trying to minimize the amount of waste, and not minimize the number of “bins”. In a sense, the problem of packing bins is the inverse of the cutting tool: how would you take steel parts and assemble them as few bars as possible under a certain size?

Answer 2

Low Cost Packaging

edit: Here's the best link: http://en.wikipedia.org/wiki/Bin_packing_problem

Answer 3

Thanks for offering the skirting board for packing bottles. This led me to the next post, Calculation of the list of abbreviations with the least amount of waste discarded . This seems to illuminate my question well.

Answer 4

A problem similar to this many years ago has been resolved. I ended up using the genetic algorithm. That would be redundant for small issues. This program was somewhat interesting for writing, but not for pleasure at the same time when it returned to 16-bit days.

First, he compiled a list of all the ways in which a 10-inch piece of raw material could be cut using predetermined lengths. For each, the amount of material lost was recorded. (Although this is quick math, it’s faster to store them for searching later.) Then he looked through the list of necessary fragments. In the loop, he would choose from a list of “path to the cutting” cutting method that did not cut more pieces of any size than required. A greedy algorithm chooses one with minimal cost, but sometimes the best solution can be found by loosening it. Ultimately, the genetic algorithm made the choice, and “DNA” is a set of paths that have been very well reflected in past decisions.

All this was back in pre-Internet days, breaking into the mind and experimenting. These days, there probably is some kind of .NET or Java library to do this already in the black box - but that would be less fun and less education, right?