About the problem

The cutting optimization problem belongs to the class of Nondeterminist Polynomial Complete (NP-Complete) problems [1]. No polynomial-time algorithm is known for this kind of problems. The only perfect algorithm for them is an exponential one. An exponential algorithm will run in an exponential amount of time (2ⁿ, 3ⁿ, n! - where n is the number of pieces to be optimized). Thus, even for small instances (lets say 10 pieces) an exponential algorithm will run in several minutes. For 1000 pieces an exponential algorithm will require more years than the age of the Universe.

Another possibility (which is employed by our component too) is to use heuristics. A heuristic is an algorithm which is fast and returns a good solution (often the best one) of the problem. However, there is no guarantee that the obtained solution is the optimal one.

An important parameter of the component is the OptimizationLevel. This will basically tell how many configurations are explored before the best found solutions is outputted. If you set the OptimizationLevel to very low value you will obtain a solution very fast. But the quality of the solution might be not so good. If you set the OptimizationLevel to very high value you will obtain a good solution but not so fast. Thus, one must employ a trade-off between the quality of the solutions and the running time.

References

[1].      Garey, M.R., Johnson D.S., Computers and Intractability: A Guide to NP-completeness, Freeman & Co, San Francisco, USA, 1979.