2D Cutting Stock Problem for Glass - Details mentioned I am trying to work on Cutting Stock Problem. I have seen some algorithm. Can anybody suggest the best 2D cutting stock problem algorithm?

I am looking for kind of best acceptable solution for 2D Glass Cutting problem. The constraints/features for this are as follows: Input to this problem is a set of Large Rectengular Glass Sheets (say approximately 100) with varied Length and Breaths called stocks. Requirement is cut Rectengular Glass pieces out of them (say approximately 200) with varied length and breadth. All (stocks &amp; output sheets) are rectangular. Also,cuts has to be guillotine cuts that mean each cut has to be end to end. 

Example of input:Stock (200 X 100 X 10, 200 X 90 X 5, etc), Required Glasses (50 X 50 X 8, 50 X 40 X 8, etc) in format of (Length X Width X No of sheets)

Here is small history of my approach for the problem: 
I wrote algorithm which would in following 4 passes:

Pass1: Take One Stock. Create a tree with all cuts possible for all the public required glasses. Also, I could rotate the glass. This step created a huge tree and is exponential.

Pass2: Iterate Pass2 for all the stocks. 

Pass3: Iterate each of the tree and covert the problem into ILP problem, as is done for 1D-CSP.

Pass4: Solve the ILP to get the best solution.

The problem with this approach is that at the first step itself the tree becomes so huge for big number of required glasses that it could not be completed in desired amount of time.

Hope this helps, please let me know if extra information is required.

Regards Sandeep Jindal
It sounds like your glass cutting problem is exactly like the 2D guillotine stock cutting problem -- am I correct that there is no difference?

I think Macleod et al's O(n^3) approximation algorithm from the 1990s is still the best known result with proven optimality bounds for very large instances of this problem, but for only 100-200 pieces the exact algorithm by Christofides and Hadjiconstantinou should be able to find the optimal solution in reasonable time.  There are also good heuristics for this problem via dynamic programming.

A survey on software solvers for the cutting stock problem was written by Macedo et al here in case you're looking for practical solutions.