Cutting Stock Problem - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: HP Prime (/forum-5.html) +--- Thread: Cutting Stock Problem (/thread-4165.html) Cutting Stock Problem - DrD - 06-17-2015 12:26 PM I'm trying to locate existing hp programming that might relate to the "Cutting Stock Problem." In particular, the 2D CSP is of special interest to me. I would appreciate any help! Thanks, -Dale- RE: Cutting Stock Problem - roadrunner - 06-19-2015 04:09 PM I know you asked for a 2d cutting stock problem; I am currently working on one. All I have so far is a solution to a 1d cutting stock problem. You input a size list, a quantity list, and the length of the raw stock. It outputs a list and the wasted stock. You cut the pieces in the order of the output list. For an example, if you want to cut 3 boards 2 feet long, 1 board 8 feet long, and 3 boards 4 feet long out of 10 foot long boards type on the command line: main({3,8,4},{2,1,3},10) The output in this case is: {{4,4,8,4,3,3},4} This indicates you cut 2 boards of 4 feet from the first 10 footer and toss the 2 feet left over, cut 1 board 8 feet long out of a second 10 footer and toss the 2 feet left over, then cut 1 board 4 feet long and two boards 3 feet long out of the third 10 footer. You’ve wasted 4 feet of board. Problems I have with this code are: 1. More than 6 or 7 boards takes forever to run on the emulator (and forever and a day on the handheld) because it checks every permutation, even the repeated ones; 2. Has a for loop that may subtract 1 from the index inside the loop; dangerous because, if not done correctly, it could result in an infinite loop; 3. Has a subroutine that calls itself, also dangerous because that hogs a lot of memory and may lead to a crashed calculator. 4. Ignores the width of the saw blade. I am still trying to decide if this program returns a “best” solution or not. I plan to modify it to eliminate the redundant checks on repeated permutations and to work on a 2d problem that cuts rectangles out of round stock. Road Here is the code: local mainlist; local bestlist; local bestwaste; local sizeofrawstock; local mainlistsize; local getwastedstock() BEGIN local tempstocksize, waste; waste:=0; tempstocksize:=sizeofrawstock; for I from 1 to mainlistsize do tempstocksize:=tempstocksize − mainlist(I); if tempstocksize < 0 then waste:=waste + tempstocksize + mainlist(I); I:=I−1; tempstocksize:=sizeofrawstock; end; end; waste:=waste + tempstocksize; if waste < bestwaste then bestwaste:=waste; bestlist:=mainlist; end; print(); print("best so far: " + string(bestlist) + " / " + string(bestwaste)); print("checking: " + string(mainlist) + " / " + string(waste)); END; local lastelement(number) BEGIN mainlist:=concat(number,mainlist); getwastedstock(); mainlist:=sub(mainlist,2,size(mainlist)); END; local takeanelementout(list,n) BEGIN local s; s:=size(list); if s == 1 then return {}; end; if n == 1 then return sub(list,2,s); end; if n == s then return sub(list,1,s-1); end; return concat(sub(list,1,n-1),sub(list,n+1,s)); END; local putanelementin(list, location, element) BEGIN if location == 1 then return concat(element, list); end; local listsize; listsize:=size(list); if location == listsize + 1 then return concat(list, element); end; return concat(sub(list,1,location−1), element, sub(list, location, listsize)); END; local doalist(list) BEGIN local listsize, i; listsize:=size(list); if listsize = 1 then lastelement(list(1)); return 0; else for i from 1 to listsize do mainlist:=putanelementin(mainlist,1,list(i)); list:=takeanelementout(list,i); doalist(list); list:=putanelementin(list,i,mainlist(1)); mainlist:=takeanelementout(mainlist, 1); end; end; END; local makealist(piecesize,quantity) BEGIN local list:={}; for I from 1 to size(piecesize) do for J from 1 to quantity(I) do list:=CONCAT(list, piecesize(I)); end; end; mainlistsize:=size(list); bestwaste:=sizeofrawstock*mainlistsize; return list; END; export main(piecesize, quantity, stocksize) BEGIN if max(piecesize) > stocksize then return "you need bigger stock"; end; print(); mainlist:={}; bestlist:={}; sizeofrawstock:=stocksize; doalist(makealist(piecesize, quantity)); return {bestlist,bestwaste}; END; RE: Cutting Stock Problem - DrD - 06-19-2015 05:05 PM This may be a problem unsuitable for the calc for all but a few cuts. Especially if a non-guillotine solution is desirable. Matlab code can be found on the net, for a solution for this problem. I've been tinkering with that, just for the agony of it. -Dale- EDIT: There are some YouTube lectures on the subject,( if you haven't already seen them): Lecture 4