5
$\begingroup$

That is probably a common optimization problem, but I don't know how to solve it efficiently.

Say you want to buy the following wood boards: 2 to 1m, 3 of 1.5m, 2 of 2m. The shop has the following boards: 1m @ 10€, 2m @ 15€, 3m @ 19€.

What boards should you buy to minimize you cost (cutting boards is free)?

The following brute-force approach works in that case, but it is very inelegant:

(* shop specifications*)
lengthPriceAssociation = {1 -> 10, 2 -> 15, 3 -> 19} // N;

(* your desired boards *)
targets = {1, 1, 1.5, 1.5, 1.5, 2, 2};

(* define all possible combinations *)
Needs["Combinatorica`"]
comb = SetPartitions[targets]
(* {{{1, 1, 1.5, 1.5, 1.5, 2, 2}}, {{1}, {1, 1.5, 1.5, 1.5, 2, 2}}, ... *)

(* select combinations that do not exceed max length available in shop *)
feasable = Select[comb, 
  Max[Total /@ #] <= Max@lengthPriceAssociation[[All, 1]] &]

(* sum the lengths of each combination *)
potentialOrdersRaw = Sort /@ Map[Total, feasable, {2}]

(* round up to existing lengths [credits to \
https://mathematica.stackexchange.com/a/97520/18767] *)
potentialOrders = 
 Flatten[Nearest[{1, 2, 3}, #, 
     DistanceFunction -> (Abs[#1 - #2] + 100 Boole[#2 < #1] &)] & /@ 
   potentialOrdersRaw, {3}];
 (* {{{2, 3, 3, 3}, {2, 3, 3, 3}, {2, 3, 3, 3}, {2, 3, 3, 3}, ... *)

 (* compute cost of each combination *)
 Map[Total, (N[potentialOrders] /. lengthPriceAssociation), {2}];
 (* 72, 72, ... , 95 *)

So the worst choice would lead to 95€, the optimal choices lead to 72€.

Ok, but what if I have a few thousands of boards to buy? The above approach is very inefficient and unusable for even a few dozens of boards.

$\endgroup$
1
  • 4
    $\begingroup$ Look up the knapsack problem and its continuous version, the linear cutting stock problem, or the bin packing problem. These are hard problems with great practical implications for which brute force approaches are typically intractable. Clever approximation algorithms have been devised but, as far as I know, these do not guarantee an optimal solution. $\endgroup$
    – MarcoB
    Jun 12 at 2:20

1 Answer 1

7
$\begingroup$

(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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.