# HP Forums

Full Version: Cutting Stock Problem
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
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-
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.

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;
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
Reference URL's
• HP Forums: https://www.hpmuseum.org/forum/index.php
• :