Cutting Stock Problem - Worked Example
Mark Lawton
Problem at http://docs.google.com/View?docid=dfkkh8qj_64rrpz86db . It
uses simple methods, and the open source program lp_solve. Briefly,
the solution shown is:
* create a list of cut combinations (not permutations - there would be
too many of those to work with in most cases)
* from this list, generate a set of linear programming (simplex)
expressions, and output them to a file
* this file becomes the input to lp_solve, which calculates an optimal
solution
* most of the cut combinations in the solution will have a score of
zero. For those that have a score greater than zero, look them up on
the list created in step 1
Seeker of Truth
I often find that good web pages have a habit of disappearing when
referred to after a period of time, so may we be permitted to paste
the text of the document into this news group, please?
On 14 May, 22:29, Mark Lawton <creamrisestothe...@gmail.com> wrote:
> There is a worked example of how to solve a basic Cutting Stock
> Problem athttp://docs.google.com/View?docid=dfkkh8qj_64rrpz86db. It
Mark Lawton
with the layout and formatting in the original document at
http://docs.google.com/View?docid=dfkkh8qj_64rrpz86db .
Just a quick reminder of the process in summary:
* create a list of cut combinations (not permutations - there would
be
too many of those to work with in most cases)
* from this list, generate a set of linear programming (simplex)
expressions, and output them to a file
* this file becomes the input to lp_solve, which calculates an
optimal
solution
* most of the cut combinations in the solution will have a score of
zero. For those that have a score greater than zero, look them up on
the list created in step 1
...and here it is in detail:
Cutting Stock Problem Solution
This is a demonstration of solving the cutting stock problem example
given at http://en.wikipedia.org/wiki/Cutting_stock_problem using open
source software and simple methods. The software is Maxima (online
manual at http://maxima.sourceforge.net/docs/manual/en/maxima.html )
and lp_solve ( http://sourceforge.net/projects/lpsolve ), a linear
programming package, which is also needed because, at time of writing,
Maxima's linear programming solver, "Simplex", cannot specify
integers.
The problem given is this: the master paper rolls are 5600 mm wide,
and the customers have ordered rolls of paper at the following widths:
Width Rolls
1380 22
1520 25
1560 12
1710 14
1820 18
1880 18
1930 20
2000 10
2050 12
2100 14
2140 16
2150 18
2200 20
A lower limit for the number of rolls required is 73, which can be
generated as follows:
(1380*22+1520*25+1560*12+1710*14+1820*18+1880*18+1930*20+2000*10+2050*12+2100*14+2140*16+2150*18+2200*20) /
5600 = 72.707
From the set or orders in the table above, a set of cutting
combinations must be generated. Of these, for each combination, there
will be many permutations. To avoid duplication, each permutation is
sorted and appended to a set (a Maxima set will automatically remove
any duplications). The maximum number of rolls which can be cut from a
master roll is the integer part of 5600/1380, which is 4, and the
widest amount of "waste" allowed in a cut is 2200 - equal to the
widest of the orders. The following Maxima code will generate the
combinations:
(solns: {},
widths: {1380, 1520, 1560, 1710, 1820, 1880, 1930, 2000, 2050, 2100,
2140, 2150, 2200},
for a1 in widths do
for a2 in widths do
for a3 in widths do
if a1 + a2 + a3 > 5600 then (
if 5600 - a1 - a2 < 2200 then
solns: adjoin(sort([a1, a2]), solns)
)
else
for a4 in widths do
if a1+a2+a3+a4 > 5600 then (
if 5600-a1-a2-a3 < 2200 then
solns: adjoin(sort([a1,a2,a3]), solns)
)
else
if 5600-a1-a2-a3-a4 < 2200 then
solns: adjoin(sort([a1,a2,a3,a4]), solns)
)$
279 cut combinations are thus generated. In order to be able to refer
to these cut combinations by number, they are now transformed into a
list:
solnList: listify(solns);
The following function will generate an inequality for a given "cut
width" and "number ordered" pair:
equate(n, order) := (
expr: concat(">= ", order, ";"),
for i: 1 thru 279 do
for k in solnList[i] do
if k = n then
expr: concat("+e", i, " ", expr),
printf(s, expr)
);
The following code will use the above function to generate the
expression to be optimised, the inequalities (using the above
function), and the list of variables to be treated as integers (which
is all of them). This "simplex" linear programming code will be output
to a file, in readiness for lp_solve to work with:
(wids: [[1380, 22],[1520, 25],[1560, 12],[1710, 14],[1820, 18],[1880,
18],[1930, 20],[2000, 10],[2050, 12],[2100, 14],[2140, 16],[2150, 18],
[2200, 20]],
s: openw("c:/temp/maxout.txt"),
printf(s,"e1 "),
for i: 2 thru 279 do
printf(s, concat("+e", i, " ")),
printf(s, ";"),
for wid in wids do
equate(wid[1], wid[2]),
printf(s, "int e1"),
for i: 2 thru 279 do
printf(s, concat(" e", i)),
printf(s, ";"),
close(s))$
See appendix 1 below for the output from this code (which is also the
input to the lp_solver program). Note: it may be necessary to edit
this text file and add line breaks after each ; character to be
accepted by lp_solve.
The lp_solve program is run from a command prompt, using file
redirection for both input and output. It also requires a parameter to
tell it to minimise (rather than maximise) the provided expressions.
Using Windows, the lp_solver command will thus look like this:
c:\temp\solver> lp_solve -min <c:\temp\maxout.txt >solution.txt
Most of the variables in the solution will have a value of 0. For
those that do not, we must retrieve the cut combinations from the
"solnList" list in Maxima:
(%i21) solnList[62];
(%o21) [1380,1880,2140]
(%i22) solnList[77];
(%o22) [1380,2000,2200]
(%i23) solnList[81];
(%o23) [1380,2050,2140]
(%i24) solnList[82];
(%o24) [1380,2050,2150]
(%i25) solnList[84];
(%o25) [1380,2100,2100]
(%i26) solnList[130];
(%o26) [1520,1880,1880]
(%i27) solnList[137];
(%o27) [1520,1880,2200]
(%i28) solnList[144];
(%o28) [1520,1930,2150]
(%i29) solnList[147];
(%o29) [1520,2000,2050]
(%i30) solnList[182];
(%o30) [1560,1820,2200]
(%i31) solnList[189];
(%o31) [1560,1880,2140]
(%i32) solnList[211];
(%o32) [1710,1710,2140]
(%i33) solnList[222];
(%o33) [1710,1880,2000]
(%i34) solnList[234];
(%o34) [1820,1820,1930]
These cut combinations, together with the number of each required,
have been transposed into a spreadsheet at
http://spreadsheets.google.com/pub?key=pH1Pv1Bl90LG589TIT6cQDw&gid=10
.
Appendix 1: lp_solver Program Input
e1 +e2 +e3 +e4 +e5 +e6 +e7 +e8 +e9 +e10 +e11 +e12 +e13 +e14 +e15 +e16
+e17 +e18 +e19 +e20 +e21 +e22 +e23 +e24 +e25 +e26 +e27 +e28 +e29 +e30
+e31 +e32 +e33 +e34 +e35 +e36 +e37 +e38 +e39 +e40 +e41 +e42 +e43 +e44
+e45 +e46 +e47 +e48 +e49 +e50 +e51 +e52 +e53 +e54 +e55 +e56 +e57 +e58
+e59 +e60 +e61 +e62 +e63 +e64 +e65 +e66 +e67 +e68 +e69 +e70 +e71 +e72
+e73 +e74 +e75 +e76 +e77 +e78 +e79 +e80 +e81 +e82 +e83 +e84 +e85 +e86
+e87 +e88 +e89 +e90 +e91 +e92 +e93 +e94 +e95 +e96 +e97 +e98 +e99 +e100
+e101 +e102 +e103 +e104 +e105 +e106 +e107 +e108 +e109 +e110 +e111
+e112 +e113 +e114 +e115 +e116 +e117 +e118 +e119 +e120 +e121 +e122
+e123 +e124 +e125 +e126 +e127 +e128 +e129 +e130 +e131 +e132 +e133
+e134 +e135 +e136 +e137 +e138 +e139 +e140 +e141 +e142 +e143 +e144
+e145 +e146 +e147 +e148 +e149 +e150 +e151 +e152 +e153 +e154 +e155
+e156 +e157 +e158 +e159 +e160 +e161 +e162 +e163 +e164 +e165 +e166
+e167 +e168 +e169 +e170 +e171 +e172 +e173 +e174 +e175 +e176 +e177
+e178 +e179 +e180 +e181 +e182 +e183 +e184 +e185 +e186 +e187 +e188
+e189 +e190 +e191 +e192 +e193 +e194 +e195 +e196 +e197 +e198 +e199
+e200 +e201 +e202 +e203 +e204 +e205 +e206 +e207 +e208 +e209 +e210
+e211 +e212 +e213 +e214 +e215 +e216 +e217 +e218 +e219 +e220 +e221
+e222 +e223 +e224 +e225 +e226 +e227 +e228 +e229 +e230 +e231 +e232
+e233 +e234 +e235 +e236 +e237 +e238 +e239 +e240 +e241 +e242 +e243
+e244 +e245 +e246 +e247 +e248 +e249 +e250 +e251 +e252 +e253 +e254
+e255 +e256 +e257 +e258 +e259 +e260 +e261 +e262 +e263 +e264 +e265
+e266 +e267 +e268 +e269 +e270 +e271 +e272 +e273 +e274 +e275 +e276
+e277 +e278 +e279;
e87 +e86 +e85 +e84 +e83 +e82 +e81 +e80 +e79 +e78 +e77 +e76 +e75 +e74
+e73 +e72 +e71 +e70 +e69 +e68 +e67 +e66 +e65 +e64 +e63 +e62 +e61 +e60
+e59 +e58 +e57 +e56 +e55 +e54 +e53 +e52 +e51 +e50 +e49 +e48 +e47 +e46
+e45 +e44 +e43 +e42 +e41 +e40 +e39 +e38 +e37 +e36 +e35 +e34 +e33 +e32
+e31 +e30 +e29 +e28 +e27 +e26 +e25 +e24 +e23 +e22 +e21 +e20 +e19 +e18
+e17 +e16 +e15 +e14 +e14 +e13 +e13 +e12 +e12 +e11 +e11 +e10 +e10 +e9
+e9 +e8 +e8 +e7 +e7 +e6 +e6 +e5 +e5 +e4 +e4 +e3 +e3 +e2 +e2 +e2 +e2
+e1 +e1 +e1 >= 22;
e152 +e151 +e150 +e149 +e148 +e147 +e146 +e145 +e144 +e143 +e142 +e141
+e140 +e139 +e138 +e137 +e136 +e135 +e134 +e133 +e132 +e131 +e130
+e129 +e128 +e127 +e126 +e125 +e124 +e123 +e122 +e121 +e120 +e119
+e118 +e117 +e116 +e115 +e114 +e113 +e112 +e111 +e110 +e109 +e108
+e107 +e106 +e105 +e104 +e103 +e102 +e101 +e100 +e99 +e99 +e98 +e98
+e97 +e97 +e96 +e96 +e95 +e95 +e94 +e94 +e93 +e93 +e92 +e92 +e91 +e91
+e90 +e90 +e89 +e89 +e88 +e88 +e88 +e26 +e25 +e24 +e23 +e22 +e21 +e20
+e19 +e18 +e17 +e16 +e15 +e15 +e3 >= 25;
e202 +e201 +e200 +e199 +e198 +e197 +e196 +e195 +e194 +e193 +e192 +e191
+e190 +e189 +e188 +e187 +e186 +e185 +e184 +e183 +e182 +e181 +e180
+e179 +e178 +e177 +e176 +e175 +e174 +e173 +e172 +e171 +e170 +e169
+e168 +e167 +e166 +e165 +e164 +e163 +e163 +e162 +e162 +e161 +e161
+e160 +e160 +e159 +e159 +e158 +e158 +e157 +e157 +e156 +e156 +e155
+e155 +e154 +e154 +e153 +e153 +e153 +e110 +e109 +e108 +e107 +e106
+e105 +e104 +e103 +e102 +e101 +e100 +e100 +e89 +e37 +e36 +e35 +e34
+e33 +e32 +e31 +e30 +e29 +e28 +e27 +e27 +e16 +e4 >= 12;
e230 +e229 +e228 +e227 +e226 +e225 +e224 +e223 +e222 +e221 +e220 +e219
+e218 +e217 +e216 +e215 +e214 +e213 +e212 +e212 +e211 +e211 +e210
+e210 +e209 +e209 +e208 +e208 +e207 +e207 +e206 +e206 +e205 +e205
+e204 +e204 +e204 +e203 +e203 +e173 +e172 +e171 +e170 +e169 +e168
+e167 +e166 +e165 +e164 +e164 +e154 +e120 +e119 +e118 +e117 +e116
+e115 +e114 +e113 +e112 +e111 +e111 +e101 +e90 +e47 +e46 +e45 +e44
+e43 +e42 +e41 +e40 +e39 +e38 +e38 +e28 +e17 +e5 >= 14;
e243 +e242 +e241 +e240 +e239 +e238 +e237 +e236 +e235 +e234 +e234 +e233
+e233 +e232 +e232 +e232 +e231 +e231 +e218 +e217 +e216 +e215 +e214
+e214 +e213 +e205 +e182 +e181 +e180 +e179 +e178 +e177 +e176 +e175
+e174 +e174 +e165 +e155 +e129 +e128 +e127 +e126 +e125 +e124 +e123
+e122 +e121 +e121 +e112 +e102 +e91 +e56 +e55 +e54 +e53 +e52 +e51 +e50
+e49 +e48 +e48 +e39 +e29 +e18 +e6 >= 18;
e251 +e250 +e249 +e248 +e247 +e246 +e245 +e244 +e244 +e236 +e236 +e235
+e233 +e222 +e221 +e220 +e220 +e219 +e215 +e206 +e190 +e189 +e188
+e187 +e186 +e185 +e184 +e184 +e183 +e175 +e166 +e156 +e137 +e136
+e135 +e134 +e133 +e132 +e131 +e130 +e130 +e122 +e113 +e103 +e92 +e64
+e63 +e62 +e61 +e60 +e59 +e58 +e57 +e57 +e49 +e40 +e30 +e19 +e7 >= 18;
e258 +e257 +e256 +e255 +e254 +e253 +e252 +e252 +e245 +e237 +e234 +e224
+e224 +e223 +e221 +e216 +e207 +e195 +e194 +e193 +e192 +e192 +e191
+e185 +e176 +e167 +e157 +e144 +e143 +e142 +e141 +e140 +e139 +e139
+e138 +e131 +e123 +e114 +e104 +e93 +e71 +e70 +e69 +e68 +e67 +e66 +e65
+e65 +e58 +e50 +e41 +e31 +e20 +e8 >= 20;
e264 +e263 +e262 +e261 +e260 +e259 +e259 +e253 +e246 +e238 +e225 +e222
+e217 +e208 +e197 +e197 +e196 +e193 +e186 +e177 +e168 +e158 +e147
+e146 +e146 +e145 +e140 +e132 +e124 +e115 +e105 +e94 +e77 +e76 +e75
+e74 +e73 +e72 +e72 +e66 +e59 +e51 +e42 +e32 +e21 +e9 >= 10;
e269 +e268 +e267 +e266 +e265 +e265 +e260 +e254 +e247 +e239 +e226 +e218
+e209 +e198 +e194 +e187 +e178 +e169 +e159 +e148 +e147 +e141 +e133
+e125 +e116 +e106 +e95 +e82 +e81 +e80 +e79 +e79 +e78 +e73 +e67 +e60
+e52 +e43 +e33 +e22 +e10 >= 12;
e273 +e272 +e271 +e270 +e270 +e266 +e261 +e255 +e248 +e240 +e227 +e210
+e199 +e195 +e188 +e179 +e170 +e160 +e149 +e142 +e134 +e126 +e117
+e107 +e96 +e84 +e84 +e83 +e80 +e74 +e68 +e61 +e53 +e44 +e34 +e23 +e11
>= 14;
e276 +e275 +e274 +e274 +e271 +e267 +e262 +e256 +e249 +e241 +e228 +e211
+e200 +e189 +e180 +e171 +e161 +e150 +e143 +e135 +e127 +e118 +e108 +e97
+e85 +e81 +e75 +e69 +e62 +e54 +e45 +e35 +e24 +e12 >= 16;
e278 +e277 +e277 +e275 +e272 +e268 +e263 +e257 +e250 +e242 +e229 +e212
+e201 +e190 +e181 +e172 +e162 +e151 +e144 +e136 +e128 +e119 +e109 +e98
+e86 +e82 +e76 +e70 +e63 +e55 +e46 +e36 +e25 +e13 >= 18;
e279 +e279 +e278 +e276 +e273 +e269 +e264 +e258 +e251 +e243 +e230 +e202
+e182 +e173 +e163 +e152 +e137 +e129 +e120 +e110 +e99 +e87 +e77 +e71
+e64 +e56 +e47 +e37 +e26 +e14 >= 20;
int e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 e14 e15 e16 e17 e18 e19
e20 e21 e22 e23 e24 e25 e26 e27 e28 e29 e30 e31 e32 e33 e34 e35 e36
e37 e38 e39 e40 e41 e42 e43 e44 e45 e46 e47 e48 e49 e50 e51 e52 e53
e54 e55 e56 e57 e58 e59 e60 e61 e62 e63 e64 e65 e66 e67 e68 e69 e70
e71 e72 e73 e74 e75 e76 e77 e78 e79 e80 e81 e82 e83 e84 e85 e86 e87
e88 e89 e90 e91 e92 e93 e94 e95 e96 e97 e98 e99 e100 e101 e102 e103
e104 e105 e106 e107 e108 e109 e110 e111 e112 e113 e114 e115 e116 e117
e118 e119 e120 e121 e122 e123 e124 e125 e126 e127 e128 e129 e130 e131
e132 e133 e134 e135 e136 e137 e138 e139 e140 e141 e142 e143 e144 e145
e146 e147 e148 e149 e150 e151 e152 e153 e154 e155 e156 e157 e158 e159
e160 e161 e162 e163 e164 e165 e166 e167 e168 e169 e170 e171 e172 e173
e174 e175 e176 e177 e178 e179 e180 e181 e182 e183 e184 e185 e186 e187
e188 e189 e190 e191 e192 e193 e194 e195 e196 e197 e198 e199 e200 e201
e202 e203 e204 e205 e206 e207 e208 e209 e210 e211 e212 e213 e214 e215
e216 e217 e218 e219 e220 e221 e222 e223 e224 e225 e226 e227 e228 e229
e230 e231 e232 e233 e234 e235 e236 e237 e238 e239 e240 e241 e242 e243
e244 e245 e246 e247 e248 e249 e250 e251 e252 e253 e254 e255 e256 e257
e258 e259 e260 e261 e262 e263 e264 e265 e266 e267 e268 e269 e270 e271
e272 e273 e274 e275 e276 e277 e278 e279;
Seeker of Truth
I've taken you maxima program to solve the one-dimensional Cutting
Stock problem (see http://en.wikipedia.org/wiki/Cutting_stock_problem
), and I have made a couple of amendments:
* I have modified the pattern generator to avoid to need for
increasingly deeply nested "for" loops as the number of possible cuts
increases, so that any size of problem can be input. My replacement
pattern generator is very far from being optimised (maybe someone in
the sci.math.symbolic group could suggest a quick way to generate
cutting stock patterns?) - it's not especially fast, and I think it
would fall over if the number of patterns was greater than a few
thousand - but for small scale problems (and many one-dimensional
cutting stock problems are small in scale) it works fine
* I have rewritten it as two functions - one to generate the linear
programming schema for lp_solve, and one to interpret the results that
lp_solve produces
Maxima actually has its own Simplex solver, but it cannot yet do
integer solutions. I hope this capability will be added - then the
whole thing can be done just in Maxima (lp_solve is an absolutely
excellent open source program - but it would be more convenient not to
have to switch programs and then type the results back into Maxima for
interpretation).
Here's the function to produce the lp_solve input file:
CutStock(cutList, theWidth, filename) := (
width: theWidth,
cuts: sort(cutList),
minTotal: width - cuts[1][1],
solns: {},
source: {},
for i: 1 thru length(cuts) do (
source: adjoin(cuts[i][1], source),
productsMax: floor((width - cuts[i][1]) / cuts[1][1]) + 1,
for products: 1 thru productsMax do (
expr: "cartesian_product(source",
for k: 2 thru products do
expr: concat(expr, ", source"),
expr: concat(expr, ")"),
candidates: eval_string(expr),
for candidate in candidates do (
total: sum(candidate[z], z, 1, length(candidate)),
if (total > minTotal) and (total <= width) then
solns: adjoin(sort(candidate), solns)
)
)
),
solnList: listify(solns),
s: openw(filename),
printf(s,"min: e1 "),
for i: 2 thru length(solnList) do
printf(s, concat("+e", i, " ")),
printf(s, "; ~% ~&"),
for cut in cuts do (
expr: concat(">= ", cut[2], ";"),
for i: 1 thru length(solnList) do
for k in solnList[i] do
if k = cut[1] then
expr: concat("+e", i, " ", expr),
printf(s, concat(expr, " ~% ~&"))
),
printf(s, "int e1"),
for i: 2 thru length(solnList) do
printf(s, concat(" e", i)),
printf(s, ";"),
close(s),
print("LP schema created. There were", length(solnList), "cut
patterns generated.")
)$
...and here's the function to interpret the results from lp_solve:
interpret(solutions) := (
bigTotal: 0,
for solution in solutions do (
print(solution[2], "x", solnList[solution[1]]),
bigTotal: bigTotal + solution[2]
),
print(" "),
for cut in cuts do (
total: 0,
for solution in solutions do
for sol in solnList[solution[1]] do
if sol = cut[1] then
total: total + solution[2],
print("Total of size", concat(cut[1], ":"), total, "(Target:",
concat(cut[2], ")"))
),
print(" "),
print("Overall total:", bigTotal),
total: 0,
for cut in cuts do
total: total + cut[1] * cut[2],
print("Theoretical minimum:", ceiling(total / width))
)$
Here is an example of it's use, using the example one-dimensional
cutting stock problem given in the above-linked wikipedia article:
CutStock([[1380, 22],[1520, 25],[1560, 12],[1710, 14],[1820, 18],
[1880, 18],[1930, 20],[2000, 10],[2050, 12],[2100, 14],[2140, 16],
[2150, 18],[2200, 20]], 5600, "c:/temp/maxout.txt")$
LP schema created. There were 213 cut patterns generated.
Then lp_solve is run against the generated file (lp_solve c:\temp
\maxout.txt). Finally, the results from lp_solve are input into the
interpret() function as [pattern number, number lp_solve requires]
pairs:
interpret([[61,1],[76,3],[79,9],[80,2],[81,7],[124,1],[131,7],[137,16],
[139,1],[169,10],[175,2],[189,4],[198,6],[202,4]])$
1 x [1380, 1880, 2140]
3 x [1380, 2000, 2200]
9 x [1380, 2050, 2140]
2 x [1380, 2050, 2150]
7 x [1380, 2100, 2100]
1 x [1520, 1880, 1880]
7 x [1520, 1880, 2200]
16 x [1520, 1930, 2150]
1 x [1520, 2000, 2050]
10 x [1560, 1820, 2200]
2 x [1560, 1880, 2140]
4 x [1710, 1710, 2140]
6 x [1710, 1880, 2000]
4 x [1820, 1820, 1930]
Total of size 1380: 22 (Target: 22)
Total of size 1520: 25 (Target: 25)
Total of size 1560: 12 (Target: 12)
Total of size 1710: 14 (Target: 14)
Total of size 1820: 18 (Target: 18)
Total of size 1880: 18 (Target: 18)
Total of size 1930: 20 (Target: 20)
Total of size 2000: 10 (Target: 10)
Total of size 2050: 12 (Target: 12)
Total of size 2100: 14 (Target: 14)
Total of size 2140: 16 (Target: 16)
Total of size 2150: 18 (Target: 18)
Total of size 2200: 20 (Target: 20)
Overall total: 73
Theoretical minimum: 73
pnachtwey
> Hi Mark,
> My replacement
> pattern generator is very far from being optimised (maybe someone in
> the sci.math.symbolic group could suggest a quick way to generate
> cutting stock patterns?)
the need for nested for loops. The recursive method starts by calling
the optimizing routine with the size or dimension of the volume you
are trying to optimize. You subtract out a piece from the table and
then pass the remaining volume back to the optimizing routine. I
have always added a cost for value that gets returned so the real goal
is not to fill the original volume but to get the best value from the
volume. If you do this right the value can be used to prune the tree
so that some branches are terminated when it is obvious they can't
return a better value. I had to do this real time so many of the
optimal volumes were pre-computed and treated as entries in the size
table. This is very important to avoid the excessive recursive calls
that remove only small pieces from the volume.
In your case you don't have just one volume but rather many volumes
but the tricks apply. Since you don't have price per piece you should
consider the cost being the waste or material left that will not make
another piece. The cost function can reduce the tree search if done
right.
Since I am new to using Maxima, I find it interesting to see the
example.
Peter Nachtwey
