Linear Programming - Cutting Stock Problem

[ijester]

I am building a house, and to make things go, I have a list of all the molding/trim/baseboard pieces that are going into the house. I also have a list of all the pieces you can buy and the lengths they come in.

I started writing some code to mesh the two, and realized this is not nearly as simple as it sounds.

Example (much simplified for illustration):

Baseboard

Pieces To Cut: 14,16,17,19,21,22,28,45,48,69,88,98,123,144,158,162,188,189,194,210

Available in: 96,120,144,168,192

How would you figure out the most efficient way to determine the best cuts with the least waste?

Assumptions:
You don't make a piece from multiple pieces of waste eg: 24 = 8,8,8
Any size available stock is ok to use
Brute force is not acceptable. An average house can have more than a 1000 pieces of molding cut from 40-60 stock sizes. To try every possible combination would be nearly impossible.

Most of my programming is in c#

 

[alpha88]

Just a thought, but you might be able to transpose this problem into a find the shortest route type problem, in which case you could use dijkstra's algorithm

 

[itachi]

use a bin packing algorithm. it's ideal for trying to minimize the number of bins that can hold N items.
in your case, each item would be a piece to cut.. and the bin size would be the available sizes.
start out with 1 piece in each bin, sort them from largest to smallest (has better packing), and run the algorithm.. as it runs, the algorithm will start out at the largest item and attempt to find a piece that'll fit into the slack space.. once it fills it up the best it can, it moves onto the next bin.. it'll keep on repeating that until it either can't find a place to put a piece or has no more pieces left.

after that it'd simply be a matter of basic algebra to figure out which size is the most economic.

 

[Velk]

Originally posted by: itachi
use a bin packing algorithm. it's ideal for trying to minimize the number of bins that can hold N items.
in your case, each item would be a piece to cut.. and the bin size would be the available sizes.
start out with 1 piece in each bin, sort them from largest to smallest (has better packing), and run the algorithm.. as it runs, the algorithm will start out at the largest item and attempt to find a piece that'll fit into the slack space.. once it fills it up the best it can, it moves onto the next bin.. it'll keep on repeating that until it either can't find a place to put a piece or has no more pieces left.

after that it'd simply be a matter of basic algebra to figure out which size is the most economic.

Other way around I think. Each bin would be a stock size of wood that you could buy, with each moulding piece being dropped into one of those 'bins' until you ran out.

At that point you know how many of each stock size you need, with no further work necessary, just from the bin counts.

 

[sdifox]

One of your piece cannot be made with the no join rule. 210 cannot be made when the longerst stock is 192 🙂 Also, what is the wastage factor? You have to build that in since cutting involves losing.
And this cannot be a real problem since baseboard come in 14 or 7 Feet sections, at least in north america. But I digress.
Brute Force in terms of mapping all possible combinations is not the way to go obviously, but brute force is the only way to do this. Bin Packing is brute force.