Talk:Cutting stock problem
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
| |||||||||||||||||||||
Note
editFrom [1] which is public domain [2]. Thue | talk 14:23, 15 Jul 2004 (UTC)
Tone
editWe should avoid the first-person plural "we". BenB4 15:49, 8 July 2007 (UTC)
ResolvedList of solutions for problem instance
editWhile trying out the problem instance in the article to get a better understanding of the problem, I found this exhaustive list of solutions (copied below). I've updated the article with the updated figures. I don't think this list of solutions would be appropriate in the article, but it's given here as numerical support of the figures in the article. Note that all 19 solutions use the minimum number of patterns (10), replicated 73 times in total, and therefore all have the same wastage (0.4%). Patterns have not been further sequenced for optimal knife positions. -- Brhaspati\talk/contribs 03:52, 7 October 2009 (UTC)
Pattern A 1820+1820+1930 Pattern B 1820+1820+1820 Pattern C 1710+1880+2000 Pattern D 1710+1710+2150 Pattern E 1710+1710+2140 Pattern F 1560+1820+2200 Pattern G 1520+1930+2150 Pattern H 1520+1930+2140 Pattern I 1520+1880+2200 Pattern J 1520+1820+2140 Pattern K 1380+2100+2100 Pattern L 1380+2050+2150 Pattern M 1380+2050+2140 Pattern N 1380+1930+2150 Pattern O 1380+1930+2140 Pattern P 1380+1880+2200 Pattern Q 1380+1820+2140 ============== Solution file1 Pattern B times 2 Pattern C times 10 Pattern D times 2 Pattern F times 12 Pattern G times 4 Pattern H times 13 Pattern I times 8 Pattern K times 7 Pattern L times 12 Pattern O times 3 ============== Solution file2 Pattern B times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 18 Pattern I times 7 Pattern K times 7 Pattern M times 12 Pattern O times 2 Pattern P times 1 ============== Solution file3 Pattern A times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 18 Pattern I times 7 Pattern K times 7 Pattern M times 12 Pattern P times 1 Pattern Q times 2 ============== Solution file4 Pattern B times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 6 Pattern H times 14 Pattern I times 5 Pattern K times 7 Pattern L times 12 Pattern P times 3 ============== Solution file5 Pattern A times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 17 Pattern I times 8 Pattern K times 7 Pattern M times 12 Pattern N times 1 Pattern Q times 2 ============== Solution file6 Pattern B times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 18 Pattern H times 2 Pattern I times 5 Pattern K times 7 Pattern M times 12 Pattern P times 3 ============== Solution file7 Pattern B times 2 Pattern C times 10 Pattern D times 1 Pattern E times 1 Pattern F times 12 Pattern G times 17 Pattern I times 8 Pattern K times 7 Pattern M times 12 Pattern O times 3 ============== Solution file8 Pattern B times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 17 Pattern I times 8 Pattern K times 7 Pattern L times 1 Pattern M times 11 Pattern O times 3 ============== Solution file9 Pattern B times 2 Pattern C times 10 Pattern D times 2 Pattern F times 12 Pattern G times 16 Pattern H times 1 Pattern I times 8 Pattern K times 7 Pattern M times 12 Pattern O times 3 ============== Solution file10 Pattern B times 2 Pattern C times 10 Pattern D times 2 Pattern F times 12 Pattern G times 16 Pattern H times 4 Pattern I times 5 Pattern K times 7 Pattern M times 12 Pattern P times 3 ============== Solution file11 Pattern B times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 15 Pattern H times 2 Pattern I times 8 Pattern K times 7 Pattern M times 12 Pattern N times 3 ============== Solution file12 Pattern B times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 17 Pattern I times 8 Pattern K times 7 Pattern M times 12 Pattern N times 1 Pattern O times 2 ============== Solution file13 Pattern B times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 6 Pattern H times 11 Pattern I times 8 Pattern K times 7 Pattern L times 12 Pattern O times 3 ============== Solution file14 Pattern B times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 3 Pattern H times 14 Pattern I times 8 Pattern K times 7 Pattern L times 12 Pattern N times 3 ============== Solution file15 Pattern B times 2 Pattern C times 10 Pattern D times 2 Pattern F times 12 Pattern G times 4 Pattern H times 16 Pattern I times 5 Pattern K times 7 Pattern L times 12 Pattern P times 3 ============== Solution file16 Pattern B times 2 Pattern C times 10 Pattern D times 2 Pattern F times 12 Pattern G times 1 Pattern H times 16 Pattern I times 8 Pattern K times 7 Pattern L times 12 Pattern N times 3 ============== Solution file17 Pattern A times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 18 Pattern I times 5 Pattern J times 2 Pattern K times 7 Pattern M times 12 Pattern P times 3 ============== Solution file18 Pattern B times 2 Pattern C times 10 Pattern D times 2 Pattern F times 12 Pattern G times 13 Pattern H times 4 Pattern I times 8 Pattern K times 7 Pattern M times 12 Pattern N times 3 ============== Solution file19 Pattern A times 2 Pattern C times 10 Pattern E times 2 Pattern F times 12 Pattern G times 15 Pattern I times 8 Pattern J times 2 Pattern K times 7 Pattern M times 12 Pattern N times 3
Software?
edit"Suppliers of such software"... What software??
121.44.118.97 (talk) 10:26, 12 October 2009 (UTC)
- in the cnc-world software can be found under the word "nesting" in the web . free : deepnest . Konfressor (talk) 09:31, 1 September 2022 (UTC)
What does this mean?=
edit"This limitation is overcome in modern algorithms, which can solve to optimality (in the sense of finding solutions with minimum waste)"... But if practical ways of guaranteeing optimal wastage are known, how can the problem still be NP-hard? What are these glorious algorithms doing? Please could someone expand on this a little to stop beginners like me getting the wrong end of the stick. 82.144.242.122 (talk) 15:07, 11 October 2010 (UTC)
Good Question: This is decribed in quite detail in the article "Linear Optimization" (I assume the case is similar here): There IS always (shown for the usual algorithms "by-hand") a worst-case problem setting (usually very symmetric) that requires brute-force i.e. exponentially many steps to solve - whereas the experience says, that linear optimization is practically always linear. So it's a matter of hope :-) — Preceding unsigned comment added by Pacman 2.0 (talk • contribs) 13:08, 5 April 2012 (UTC)
Example
editPlease stop restoring unreferenced example. It is original research disallowed in wikipedia. It is useless because it cannot be verified by hand and does not illustrate the solution process. - üser:Altenmann >t 14:08, 3 May 2016 (UTC)
A simple example, which can be easily verified step-by step, is OK without references, per WP:Verifiabilty, but a complicated example and various nontrivial statements, such as "it has 70 solutions" is disallowed per wikipedia rules. - üser:Altenmann >t 14:14, 4 May 2016 (UTC)
- (cur | prev) 03:46, May 4, 2016 Cngoulimis (talk | contribs) . . (16,686 bytes) (+2,806) . . (Undid revision 718544683 by Altenmann (talk)Please don't try to find new reasons to delete something.) (undo | thank)
- (cur | prev) 21:17, May 3, 2016 Altenmann (talk | contribs) . . (13,880 bytes) (-2,806) . . (Reverted 1 edit by 83.244.151.146 (talk): Rv unreferenced. Please dont add information without references. (TW)) (undo)
- (cur | prev) 15:13, May 3, 2016 83.244.151.146 (talk) . . (16,686 bytes) (+2,806) . . (Undid revision 718435051 by Altenmann (talk)The example is not incomprehensible and there is no requirement for it to be solveable by hand. What's the definition of solveable by hand anyway?) (undo)
- (cur | prev) 07:05, May 3, 2016 Altenmann (talk | contribs) . . (13,880 bytes) (-2,806) . . (Reverted 1 edit by *83.244.151.146 (talk): The example is incomprehensible; cannot be verified by hand and without references. (TW)) (undo)
- (cur | prev) 03:59, May 3, 2016 83.244.151.146 (talk) . . (16,686 bytes) (+2,806) . . (Undid revision 718169384 by Altenmann (talk) The example is really useful and Altenmann is mistaken in thinking that it does not help) (undo)
- (cur | prev) 15:58, May 1, 2016 Altenmann (talk | contribs) . . (13,880 bytes) (-2,806) . . (Reverted 1 edit by Cngoulimis (talk): Rv unreferenced poor illustration. (TW)) (undo)
- (cur | prev) 13:41, May 1, 2016 Cngoulimis (talk | contribs) . . (16,686 bytes) (+2,806) . . (Undid revision 712448958 by Altenmann (talk)) (undo | thank)
- (cur | prev) 21:28, March 28, 2016 Altenmann (talk | contribs) . . (13,880 bytes) (-2,806) . . (Reverted 1 edit by Cngoulimis (talk): Rv original math. This is not "small example" an has no explanatory value. (TW)) (undo)
- (cur | prev) 14:58, March 27, 2016 Cngoulimis (talk | contribs) . . (16,686 bytes) (+2,806) . . (Undid revision 705013676 by Altenmann (talk) The definition of small example (verifiable by hand) is not appropriate for combinatorial optimisation problems in
NP-hardness
editThe article says:
In terms of computational complexity, the problem is an NP-hard problem reducible to the knapsack problem.
Technically, you can certainly perform such a reduction, which is hardly surprising. However, if the aim is to say something about how the problem is shown to be NP-hard, the important point is that you can reduce *from* an NP-complete problem such as the knapsack problem (which, in turn, means you can reduce from all problems in NP, including all NP-complete ones, so there is nothing special about the knapsack problem here). I'd suggest something along the following lines:
In terms of computational complexity, the problem is NP-hard, with a straightforward reduction from the knapsack problem, for example.
Mlhetland (talk) 10:35, 24 November 2023 (UTC)
- Or, for that matter, the reduction part could be removed, leaving just the statement about NP-hardness. I'm not sure the reduction from the knapsack problem is all that straightforward, really. Probably easier to reduce from the bin packing problem. Mlhetland (talk) 10:44, 24 November 2023 (UTC)