1-dimensional nesting algorithm

Question

What is an effective algorithm for nesting 1 dimensional lengths into predefined stock lengths?

For example, If you required steel bars in the following quantities and lengths,

• 5 x 2 metres
• 5 x 3 metres
• 5 x 4 metres

and these can be cut from 10 metre bars. How could you calculate the pattern for cutting the 10m bars so that the minimum number of bars are used?

In addition, how could you incorporate multiple stock lengths into the algorithm?

---

I've had a bit of time to work on this so I'm going to write up how I solved it. I hope this will be useful to someone.I'm not sure if it is ok to answer my own question like this. A moderator can change this to an answer if that is more appropriate.

First thanks to everyone that answered. This pointed me to the appropriate algorithm; the cutting stock problem.

This post was also useful; "Calculating a cutting list with the least amount of off cut waste".

Ok, on to the solution.

I'll use the following terminology in my solution;

• Stock: a length of material that will be cut into smaller pieces
• Cut: a length of material that has been cut from stock. multiple cuts may be taken from the same piece of stock
• Waste: the length of material that is left in a piece of stock after all cuts have been made.

There are three main stages to solving the problem,

1. Identify all possible cut combinations
2. Identify which combinations can be taken from each piece of stock
3. Find the optimal mix of cut combinations.

Step 1

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

Where A,B,C are unique cuts;

A B C | 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

A for-loop with some bitwise operators can be used to quickly create groupings of each cut combination.

This can get quite time consuming for large values of N.

In my situation there were multiple instances of the same cut. This produced duplicate combinations.

A B B | 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 exploit this redundancy to reduce the time to calculate the combinations. I grouped the duplicate cuts together and calculated the unique combinations of this group. I then appended this list of combinations to each unique combination in a second group to create a new group.

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

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

Call this group X.

Append X to unique instances of B,

B B X | 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.

Append Y to unique instances of C,

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

This example produces 17 unique combinations instead of 31 (2^5-1). A saving of almost half.

Once all combinations are identified it is time to check how this fits into the stock.

Step 2

The aim of this step is to map the cut combinations identified in step 1 to the available stock sizes.

This is a relatively simple process. For each cut 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 a valid nested cut combinations. It is not strictly necessary to store the waste as this can be calculated from the cut lengths and stock length. However, storing waste reduces processing required in step 3.

Step 3

In this step we will identify the combination of cuts that produces the least waste. This is based on the list of valid nests generated in step 2.

In an ideal world we would calculate all possibilities and select the best one. For any non-trivial set of cuts it would take forever to calculate them all. We will just have to be satisfied with a non optimal solution. There are various algorithms for accomplishing this task.

I chose a method that will look for a nest with the least waste. It will repeat this until all cuts have been accounted for.

Start with three lists

• cutList: a list of all required cuts (including duplicates).
• nestList: The list of nests generated in step 2. This is sorted from lowest waste to highest waste.
• finalList: Initially empty, this will store the list of cut combinations that will be output 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

With this method I managed to get a total waste of around 2-4% for some typical test data. Hopefully I will get to revisit this problem at some point and have a go at implementing the Delayed column generation algorithm. This should give better results.

I hope this helped anyone else having this problem.

David

Answer 1

Actually, there's an even more specific problem that applies: The cutting stock problem:

The cutting stock problem is an optimization problem, or more specifically, an integer linear programming problem. It arises from many applications in industry. Imagine that you work in a paper mill and you have a number of rolls of paper of fixed width waiting to be cut, yet different customers want different numbers of rolls of various-sized widths. How are you going to cut the rolls so that you minimize the waste (amount of left-overs)?

The reason this applies better than the bin packing problem is because you are trying to minimise the waste, rather than minimise the number of 'bins'. In a sense, the bin packing problem is the inverse of the cutting stock problem: How would you take lengths of steel and reassemble them into as few bars as possible under a certain size?

Answer 2

Least Cost Bin Packing

edit: Here's a better link: http://en.wikipedia.org/wiki/Bin_packing_problem

Answer 3

Thanks for suggesting bin packing problem plinth. This lead me to the following post, Calculating a cutting list with the least amount of off cut waste. This appears to cover my question well