4
$\begingroup$

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 Sandeep Jindal

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The bin packing problem 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? $\endgroup$
    – Jukka Suomela
    Commented Sep 14, 2010 at 8:54
  • $\begingroup$ I'll reiterate Jukka's remarks. The asker will benefit from taking a look at how to ask a good question here; it's not clear what aspect of the problem is interesting to the questioner. $\endgroup$
    – Anand Kulkarni
    Commented Sep 16, 2010 at 6:21
  • $\begingroup$ 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. $\endgroup$
    – Sandeep Jindal
    Commented Sep 17, 2010 at 14:06
  • $\begingroup$ 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? Can you write out the ILP you are using? $\endgroup$
    – Anand Kulkarni
    Commented Sep 17, 2010 at 18:13

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Sandeep Jindal
    Commented Sep 17, 2010 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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