{"id":9,"date":"2010-10-17T19:20:27","date_gmt":"2010-10-17T16:20:27","guid":{"rendered":"http:\/\/optimalprograms.com\/blog\/?p=9"},"modified":"2012-07-26T11:09:52","modified_gmt":"2012-07-26T08:09:52","slug":"about-the-cutting-and-nesting-optimization-problem","status":"publish","type":"post","link":"https:\/\/optimalprograms.com\/blog\/?p=9","title":{"rendered":"About the cutting and nesting optimization problem"},"content":{"rendered":"

The cutting optimization problem belongs to the class of?Nondeterminist Polynomial Complete<\/a> (NP-Complete) problems [1]. Other problems in this class are the?Hamiltonian path<\/a>,?Travelling Salesman<\/a>,?Subset sum<\/a>,?Clique<\/a>,?Independent set<\/a>,?Graph colouring<\/a> etc. All these problems have been deeply analyzed by a huge number of researchers, but no polynomial-time algorithm was discovered for them. This has a direct consequence over the running time and the quality of the optimization.<\/p>\n

A polynomial-time algorithm is that one whose running time is bounded by a polynomial function of its input size. For instance, if we have n = 1000 pieces to cut and the cutting algorithm would have the complexity O(n2<\/sup>), then the running time would have been directly and linear proportional to 10002<\/sup> which is (106<\/sup>) units of time. Assuming that our computers can perform 109<\/sup> operations per second, the cutting optimization algorithm would run in less than a fraction of a second. Sadly, this is not the case for the cutting optimization problem. There is no such fast algorithm for solving it.<\/p>\n

The only perfect algorithm for solving the cutting optimization problem is an exponential one. An exponential algorithm will run in an exponential amount of time (2n<\/sup><\/em>, 3n<\/sup><\/em>,?n<\/em>! – where?n<\/em> is the number of pieces to be optimized). Thus, even for small instances (lets say 1000 pieces) an exponential algorithm will run as follows:<\/p>\n\n\n\n
\n