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?

  • $\begingroup$ 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? $\endgroup$ – fade2black Jul 28 '17 at 9:27
  • 1
    $\begingroup$ Can you formulate your problem more generally and formally? Assume I know nothing about woodworking. $\endgroup$ – Yuval Filmus Jul 28 '17 at 9:41
  • $\begingroup$ The number of planks can vary as well as different lengths and different amount and sizes of sawed pieces. So all variables varies. $\endgroup$ – Viktor Eriksson Jul 28 '17 at 9:42
  • $\begingroup$ Please check if I guessed correctly. $\endgroup$ – fade2black Jul 28 '17 at 9:50
  • $\begingroup$ Also, it would be helpful if you added a specific example with the corresponding optimal solution. $\endgroup$ – fade2black Jul 28 '17 at 9:55

This problem can be reduced to the binpacking problem (which is a special instance of the cutting stock problem, see @fade2black's answer)

The bins can represent the fixed size wood pieces, which are 100cm long in your example.

The items to be binned can be the list of needed wood lengths.

Minimizing for the minimal number of bins equates minimizing waste;

  • Let $L_M$ be the size of a bin, $L_{all} = \sum_{i=1}^N L_i$
  • Suppose there is a distribution of $L_i$ over $M_{min}$ bins, but it is not the minimum amount of waste.
    • Then there is a distribution of $L_i$ over $M_{minwaste}$ bins where $M_{min} < M_{minwaste} $
    • And then the waste can be expressed as $[M_{minwaste} * L_M - L_{all}] < [M_{min}*L_M - L_{all}] $
    • which simplifies to: $M_{minwaste} < M_{min} $
    • This contradicts our premise and its derivative of $M_{min} < M_{minwaste}$ .
  • Hence, $M_{minwaste}$ cannot be greater than $M_{min}$ and have less waste.

Python example using the binpacking module, note that binpacking is indeed NP-hard, as such the binpacking module is most likely using heuristiscs which will most likely result in approximation answers.

import binpacking
needed = [60, 30, 50, 20]
print(binpacking.to_constant_volume(needed, 100))

Outputs the following:

[[60, 30], [50, 20]]
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. You're left with one piece of about 10, another of 30 - is this minimum waste? Assuming width of cut zero, [[60], [50, 30, 20]] leaves one piece of 40. $\endgroup$ – greybeard Oct 19 '20 at 18:53
  • $\begingroup$ That's a real question right? The Question is not really clear, or is this a widely accepted definition of minimum waste? My rationale was, waste is waste, no need for it to be the least amount of pieces. $\endgroup$ – hbogert Oct 19 '20 at 18:59

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

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

If you find the subject interesting, there is a company that reduces waste by about 10% (according to their marketing material) by cutting trees not into rectangular shapes, but according to the shape of the tree. You order the floor boards for your room size, and you get non-rectangular floor boards that fit together exactly, and must be laid in exactly the right order.

And reducing waste by 10% means they need to process 10% less wood, which directly increases profits.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.