(Solution to original problem further below)
MarcoB indicated useful keywords in his comment, in particular this problem is a subclass of the cutting stock problem.
For the reference, two links that I did not use directly:
Since, as formulated in the OP, it is a difficult mathematical problem with probably no guaranted optimal solution, I (for now) raised the constraint that there are different lengths and costs. I believe the following can be adapted to deal with the original problem, but I am not sure yet.
I will illustrate the answer on the following example, starting from the result: I will buy 5 boards, cut 1 in 2m + 2m, 1 in 1m+1m+1m+1m, 1 in 1m + 3m, 1 in 3.9m and 1 in 4m.
Accordingly, the desired order is (units in mm to make avoid confusion between quantities and lengths):
order = {{5, 1000}, {2, 2000}, {1, 3000}, {1, 3900}, {1, 4000}};
The key idea is to "preprocess" the cutting combinations:
lengths = order[[All, 2]];
maxWaste = 0.2;
maxLength = 4000;
possibleQuantities = Table[Range[0, Floor[maxLength/lengths[[i]]]], {i, Length@lengths}];
possibleConfigurations = Select[Tuples[possibleQuantities],
(1 - maxWaste)*maxLength <= Total[lengths*#] <= maxLength &];
possibleCuts = SortBy[possibleConfigurations, maxLength - Total[lengths*#] &]
(* {{0, 0, 0, 0, 1}, {0, 2, 0, 0, 0}, {1, 0, 1, 0, 0}, {2, 1, 0, 0,
0}, {4, 0, 0, 0, 0}, {0, 0, 0, 1, 0}} *)
For instance, {1, 0, 1, 0, 0} means that one 4m board can be cut into 1x1000mm + 1x3000mm. {0, 0, 0, 1, 0} means one 4m board can be cut to 1x3900mm. The maxWaste parameter was meant to help the optimization by rejecting the bad cutting choices, such as wasting 3m when keeping 1m. But it can be chosen as 1 (i.e. 100%).
Then, the problem is reduced to finding the number of the different combination cuts so that the number of boards is minimal, under the constraint that the order is filled:
cost[weights_] := Total[weights]
vars = Table[a[i], {i, Length@possibleCuts}];
cons = Thread[Total[vars*possibleCuts] - quantities >= 0]~
Join~{Thread[vars \[Element] NonNegativeIntegers]};
sol = LinearOptimization[cost[vars], cons, vars];
(* {a[1] -> 1, a[2] -> 0, a[3] -> 1, a[4] -> 2, a[5] -> 0, a[6] -> 1} *)
Interpretation The first configuration {0, 0, 0, 0, 1} is to be chosen a[1], which is the 1x4m board. The fourth configuration {2, 1, 0, 0, 0} (2 times 1m and 1 time 2m) is to be chosen a[4] times (= twice).
This uses 5 boards as expected:
cost[vars /. sol]
(* 5 *)
Tried on few thousand samples (e.g. order = {{186, 700}, {182, 750}, {178, 1250}, {121, 2000}, {89, 2150}, {229, 2500}, {89, 2850}, {112, 3000}, {43, 3060}}), runs instantly.
Solution to the OP
The above solution can be adapted to deal with multiple stock lengths and prices.
displaySol[list_, availableLengths_] := Column@Table[Block[{},
j = list[[i, 1]];
number = list[[i, 2]];
cutconfig = list[[i, 3]];
correspondingLengths =
lengths[[Flatten@Position[list[[i, 2]], _?(# > 0 &)]]];
listsubdivisions =
Flatten@Table[
lengths[[q]], {q, Length@cutconfig}, {p, cutconfig[[q]]}];
"Cut " <> ToString[list[[i, 2]]] <> " boards of " <>
ToString[availableLengths[[j]]/1000] <> "m into " <>
StringRiffle[listsubdivisions, "mm + "] <> "mm (loss = " <>
ToString[availableLengths[[j]] - Total@listsubdivisions] <> "mm)"
], {i, Length@list}]
computeOptimal[order_, availableLengths_, prices_] := Block[{},
quantities = order[[All, 1]];
lengths = order[[All, 2]];
maxLength = Max@availableLengths;
possibleQuantities =
Table[Range[0, Floor[availableLengths[[j]]/lengths[[i]]]], {j,
Length@availableLengths}, {i, Length@lengths}];
possibleConfigurations =
Table[Select[Tuples[possibleQuantities[[i]]],
0 <= Total[lengths*#] <= availableLengths[[i]] &], {i,
Length@availableLengths}];
possibleCuts =
Table[SortBy[possibleConfigurations[[i]],
availableLengths[[i]] - Total[lengths*#] &], {i,
Length@availableLengths}];
vars = Table[
a[j][i], {j, Length@availableLengths}, {i,
Length@possibleCuts[[j]]}];
cost[vars_] :=
Table[Total[
ConstantArray[prices[[i]], Length@possibleCuts[[i]]]*
vars[[i]]], {i, Length@availableLengths}] // Total;
cons = Thread[
Total[Table[
Total[vars[[j]]*possibleCuts[[j]]], {j,
Length@availableLengths}]] - quantities >= 0]~
Join~{Thread[vars \[Element] NonNegativeIntegers]};
vars2 = Flatten@vars;
sol = LinearOptimization[cost[vars], cons, vars2];
list = Flatten[
Table[Select[
Table[{j, a[j][i] /. sol, possibleCuts[[j, i]]}, {i,
Length@possibleCuts[[j]]}], #[[2]] > 0 &], {j,
Length@availableLengths}], 1];
Print["You need :" <>
StringJoin@
Table["\n - " <> ToString@quantities[[i]] <> " pieces of " <>
ToString@lengths[[i]] <> " mm", {i, Length@order}]];
Print@displaySol[list, availableLengths];
Print["Total cost: " <> ToString@cost[vars /. sol]];]
Example:
order = {{275, 500}, {186, 700}, {182, 750}, {178, 1250}, {89,
2150}, {57, 2300}, {178, 2500}, {159, 2750}, {145, 2800}, {89,
2850}, {75, 3000}};
computeOptimal[order, {3000, 4000}, {3, 4}] returns:
You need :
- 275 pieces of 500 mm
- 186 pieces of 700 mm
- 182 pieces of 750 mm
- 178 pieces of 1250 mm
- 89 pieces of 2150 mm
- 57 pieces of 2300 mm
- 178 pieces of 2500 mm
- 159 pieces of 2750 mm
- 145 pieces of 2800 mm
- 89 pieces of 2850 mm
- 75 pieces of 3000 mm
- Cut 75 boards of 3m into 3000mm (loss = 0mm)
- Cut 57 boards of 3m into 700mm + 2300mm (loss = 0mm)
- Cut 122 boards of 3m into 500mm + 2500mm (loss = 0mm)
- Cut 67 boards of 3m into 750mm + 2150mm (loss = 100mm)
- Cut 89 boards of 3m into 2850mm (loss = 150mm)
- Cut 16 boards of 3m into 2800mm (loss = 200mm)
- Cut 156 boards of 4m into 1250mm + 2750mm (loss = 0mm)
- Cut 56 boards of 4m into 750mm + 750mm + 2500mm (loss = 0mm)
- Cut 3 boards of 4m into 500mm + 750mm + 2750mm (loss = 0mm)
- Cut 129 boards of 4m into 500mm + 700mm + 2800mm (loss = 0mm)
- Cut 22 boards of 4m into 500mm + 1250mm + 2150mm (loss = 100mm)
Total cost: 2742
