How to find optimum combination for Cutting Stock Problem using Knapsack

Question

EDIT (31-12-2019) - https://jonathan.overholt.org/projects/cutlist

Above is the link of the free project which is what exactly I am looking for. I am just looking for proper guidance so that I can make it work.

I am working on minimizing the wastage of aluminium extrusion cutting for Aluminium Sliding Window Fabricators and I am not able to figure out which Algorithm/Data Structure I should go with for the problem.

I have done basic research and found that the problem falls in Cutting Stock Problem (Also called One dimensional cutting problem), Linear Programming Problem, Greedy Algorithm. BUT I am unable to decide which one I should go with and also how to start with.

Brief about the problem :

Basically the window fabricators have 3 sizes of material options to purchase.

12 | 15 | 16 (IN FT)

Now the input would be the size of Window.

WIDTH x HEIGHT (IN FT)

1) 6 x 8 - 10 Windows

2) 9 x 3 - 20 Windows

The calculation is (2 x Width) + (2 x Height). So from the above sizes of window, they need extrusion as follow.

1) 6' (FT) Size Pieces -> 2 x 10 = 20

2) 8' (FT) Size Pieces -> 2 x 10 = 20

3) 9' (FT) Size Pieces -> 2 x 20 = 40

4) 3' (FT) Size Pieces -> 2 x 20 = 40

Using knapsack, we can find out the combination but it has restriction of having size to 1 only whereas here in my case I have 3 different sizes available out of which I would like to generate the best optimum combination for the cutting stock problem.

I would need help in how should I proceed for the above problem with respect to data structure and algorithm in Java or any other language. My knowledge in Maths is not up to the mark and that's why I am facing issue in implementing the logic in my project and like to get some help from the community.

Answer 1

There is no algorithm that will guarantee you the optimal solution other than brute-force checking all possible combinations. That's obviously not a good algorithm, at least not if you have large data sets.

You should have a look at heuristic search algorithms like Simulated Annealing, MCTS or the like. It should be no problem finding existing implementations of heuristic search engines that allow you to provide them with

• an input set (random distribution of pieces on material),
• a transition function (move pieces between materials),
• and an evaluation function (the amount of waste)

and compute a near-optimal solution for you.

Answer 2

I'll echo the sentiment of the other answers: while there might be a "most correct" solution to this problem, what you're really looking for is a "correct enough" solution.

That said, I wrote up this little appendix to help make sense of the code in the project you referenced: cutlist generator design notes

Paraphrased:

Each iteration starts by creating a new instance of the longest stock and placing as many pieces into it as will fit. The stock is then reduced to the smallest stock that all of the selected pieces still fit into. This is all repeated until no pieces remain.

Another word of advice: make sure to clearly identify all of the assumptions you're building into the algorithm. Mine assumes that longer stock is cheaper per unit and that it's always preferred, but I've been asked for variations to optimize for the least number of cuts (bundle cutting) or to keep track of and prefer to use offcuts from previous runs first.

As always: Understand your customer's process very clearly before setting the assumptions.