<p>It sounds like your glass cutting problem is exactly like the 2D guillotine stock cutting problem -- am I correct that there is no difference?</p>

<p>I think Macleod et al's O(n^3) <a href="http://linkinghub.elsevier.com/retrieve/pii/037722179390196T" rel="noreferrer">approximation algorithm</a> 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 <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6VCT-4031R2C-16&amp;_user=4420&amp;_coverDate=05%2F18%2F1995&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1462326123&amp;_rerunOrigin=scholar.google&amp;_acct=C000059607&amp;_version=1&amp;_urlVersion=0&amp;_userid=4420&amp;md5=171fafb32c985eb73cdd51be160fa8d1&amp;searchtype=a" rel="noreferrer">Christofides and Hadjiconstantinou</a> should be able to find the optimal solution in reasonable time.  There are also good heuristics for this problem via dynamic programming.</p>

<p>A survey on software solvers for the cutting stock problem was written by Macedo et al <a href="http://www.scoop-project.net/DOCUMENTI/File/MacedoEtAlii_080715.pdf" rel="noreferrer">here</a> in case you're looking for practical solutions.</p>

CC BY-SA 2.5
2010-09-17T14:15:12.677Z
yes it is exactly like 2D guillotine stock cutting problem. Also the survey helped me. But I am trying to write one of the algorithms that those software makers have written.
Sandeep Jindal
CC BY-SA 2.5
2010-09-15T17:09:34.763Z
2010-09-16T23:19:32.187Z
2010-09-16T23:19:32.187Z
Anand Kulkarni
<p>I am trying to work on Cutting Stock Problem. I have seen some algorithm. Can anybody suggest the best 2D cutting stock problem algorithm?</p>

<p>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. </p>

<p>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)</p>

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

<p>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.</p>

<p>Pass2: Iterate Pass2 for all the stocks. </p>

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

<p>Pass4: Solve the ILP to get the best solution.</p>

<p>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.</p>

<p>Hope this helps, please let me know if extra information is required.</p>

<p>Regards Sandeep Jindal</p>

CC BY-SA 2.5
2010-09-14T08:54:41.210Z
The [bin packing problem](http://www.nada.kth.se/~viggo/wwwcompendium/node160.html) is a simple special case of your problem; hence it is NP-hard to decide if your problem has a feasible solution or not. Are you looking for exponential-time algorithms that find an exact solution? Or some kind of polynomial-time approximations that don't necessarily find an optimal solution? If approximations, how do you measure the quality of an approximation? (E.g., almost all required glasses produced? Little extra stock needed? Little waste glass produced?) What are the shortcomings of existing algorithms?
Jukka Suomela
CC BY-SA 2.5
2010-09-16T06:21:29.953Z
I'll reiterate Jukka's remarks.  The asker will benefit from taking a look at [how to ask a good question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question) here; it's not clear what aspect of the problem is interesting to the questioner.
Anand Kulkarni
CC BY-SA 2.5
2010-09-17T14:06:44.890Z
Thanks for the comments! Frankly, I am researcher kind of guy. Thus probably could not wrote all the specifications as asked by Jukka. As mentioned by Anand in the post below, I am looking for solution for 2D guillotine Stock Cutting Problem.
Yes, I would want a polynomial-time approximations and the quality can be reduced. I cannot quantify the quality, but it would be like ending up using more glasses, having more waste than an optimal solution.
I am adding history of what I was trying to do and where did I failed. Hope that can help to make it more elaborative.
Sandeep Jindal
CC BY-SA 2.5
2010-09-17T18:13:00.427Z
It looks like the first step is the problem. It's not quite clear which algorithm you are following, but I presume it's one of the integer programming approaches.  Is it the one mentioned [here](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6VCT-48NBG1F-1R7&_user=4420&_coverDate=09%2F25%2F1991&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1464887988&_rerunOrigin=scholar.google&_acct=C000059607&_version=1&_urlVersion=0&_userid=4420&md5=7789b85f62494d2d0f975580e5228da1&searchtype=a)?  Can you write out the ILP you are using?
Anand Kulkarni
<ds.algorithms><ds.data-structures>
2D Cutting Stock Problem for Glass - Details mentioned
Sandeep Jindal
# 2D Cutting Stock Problem for Glass - Details mentioned

(Asked by: username_0 on 2010-09-14)

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 & 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 username_0

**Tags:** ds.algorithms, ds.data-structures

> **Comments:**
> **username_1**: The [bin packing problem](http://www.nada.kth.se/~viggo/wwwcompendium/node160.html) is a simple special case of your problem; hence it is NP-hard to decide if your problem has a feasible solution or not. Are you looking for exponential-time algorithms that find an exact solution? Or some kind of polynomial-time approximations that don't necessarily find an optimal solution? If approximations, how do you measure the quality of an approximation? (E.g., almost all required glasses produced? Little extra stock needed? Little waste glass produced?) What are the shortcomings of existing algorithms?  
> **username_2**: I'll reiterate Jukka's remarks.  The asker will benefit from taking a look at [how to ask a good question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question) here; it's not clear what aspect of the problem is interesting to the questioner.  
> **username_0**: Thanks for the comments! Frankly, I am researcher kind of guy. Thus probably could not wrote all the specifications as asked by Jukka. As mentioned by Anand in the post below, I am looking for solution for 2D guillotine Stock Cutting Problem. Yes, I would want a polynomial-time approximations and the quality can be reduced. I cannot quantify the quality, but it would be like ending up using more glasses, having more waste than an optimal solution. I am adding history of what I was trying to do and where did I failed. Hope that can help to make it more elaborative.  
> **username_2**: It looks like the first step is the problem. It's not quite clear which algorithm you are following, but I presume it's one of the integer programming approaches.  Is it the one mentioned [here](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6VCT-48NBG1F-1R7&_user=4420&_coverDate=09%2F25%2F1991&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1464887988&_rerunOrigin=scholar.google&_acct=C000059607&_version=1&_urlVersion=0&_userid=4420&md5=7789b85f62494d2d0f975580e5228da1&searchtype=a)?  Can you write out the ILP you are using?  

---

## 1 answers

### Answer by username_2 on 2010-09-15. Score: 9

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](http://linkinghub.elsevier.com/retrieve/pii/037722179390196T) 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](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6VCT-4031R2C-16&_user=4420&_coverDate=05%2F18%2F1995&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1462326123&_rerunOrigin=scholar.google&_acct=C000059607&_version=1&_urlVersion=0&_userid=4420&md5=171fafb32c985eb73cdd51be160fa8d1&searchtype=a) 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](http://www.scoop-project.net/DOCUMENTI/File/MacedoEtAlii_080715.pdf) in case you're looking for practical solutions.

> **Comments:**
> **username_0**: yes it is exactly like 2D guillotine stock cutting problem. Also the survey helped me. But I am trying to write one of the algorithms that those software makers have written.  

---

