Talk:Cutting stock problem

Note

From [1] which is public domain [2]. Thue | talk 14:23, 15 Jul 2004 (UTC)

Tone

We should avoid the first-person plural "we". BenB4 15:49, 8 July 2007 (UTC)

Resolved

List of solutions for problem instance

While 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?

"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?=

"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

Please 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

The 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)