# What algorithm to use, least waste when sawing wood planks

Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 30cm 50cm and 20cm. Is there an algorithm for calculating the least waste? When using brute force it quickly escalates in time :(

Formally we have $N$ wooden planks each $L_1, \dots, L_N$ cm long. And we want to have $M$ pieces, $l_1, l_2, \dots, l_M$ cm long. How to minimize the waste?

• Is your problem only for 2 planks 1 meter each, and your pieces are always 4 with 60, 30, 50, and 20 cm? What is input? What varies? What is constant? For this specific scenario is not 60 + 30 and 50 + 20 a solution? – fade2black Jul 28 '17 at 9:27
• Can you formulate your problem more generally and formally? Assume I know nothing about woodworking. – Yuval Filmus Jul 28 '17 at 9:41
• The number of planks can vary as well as different lengths and different amount and sizes of sawed pieces. So all variables varies. – Viktor Eriksson Jul 28 '17 at 9:42
• Please check if I guessed correctly. – fade2black Jul 28 '17 at 9:50
• Also, it would be helpful if you added a specific example with the corresponding optimal solution. – fade2black Jul 28 '17 at 9:55

## 1 Answer

This problem seems to be NP-hard. Please check Cutting stock problem. Nevertheless, you could attack it using LP or other approximation methods.

• Having some problems mapping my problem to the definition of cutting stock problem. Would my problem one dimensional ? – Viktor Eriksson Aug 1 '17 at 18:14