I'm not set up to write LUA code at the moment (haven't done it in more than 5 years), but I'm going to install LUA and find a development environment (hopefully there's Eclipse support).
But this means I can't write any code at the moment.
If someone else wants to implement it I can explain how to implement the heuristic I used as a generic program.
Note: this isn't the same thing as a program that can find the best solution (see below). It would probably be a useful starting point though.
As for finding the best solution: That's possible by a variant of this heuristoc ... and if you don't mind the program possibly taking a long time (tens of minutes) it might be possible to run it in LUA. But please don't underestimate the complexity issue: computation for problems like this grows
much faster than the number of extra elements that are added to the specific problem - e.g. they run its "big brother", the Knapsack Problem, for hours on supercomputers.
Anyway we can move forward now if someone else wants to play a bit with LUA. I'll explain the steps for a generic implementation here.
I'm not sure it will be practical to hack a program that runs inside OT that always find the optimal solutuion, but I suppose we could make a version of the heuristic that enumerates every possible solution, and perhaps has some logic to reject obviously bad ones (to improve efficiency a bit.
If an optimal solution is
required for an
open-ended version of your objective, it will almost certainly be smarter to study the techniques used by commercial solutions, starting with the first wikipedia article I linked above.
All that said, the first step is just to write some logic to enumerate all the possible combinations of the smaller pieces that, in total, are less than or equal to the larger piece.
An aside: this becomes computationally inefficient with a large number of distinct longer pieces and/or a larger number of distinct shorter pieces. On the other hand, with a forest worth of trees and lots of smaller pieces, an easier approach (a different heuristic) can be used.
So: the enumeration can e.g. start with the longest cut piece, and go through the possibilities like this (using the initial example):
Start with the largest: 5, then continue in order:
- 5 < 12, 2 x 5 is less than 12, 3 x 5 is > 12; => (1 x 5) and (2 x 5) are a possible cuts
- 5 + 4.5 < 12 , (5 + (2x4.5)) > 12, 5 + 4.5 + 3.5 > 12 => 5 + 4.5 is a possible cut
- 5 + 3.5 < 12, 5 + (2 x 3.5) = 12 => (5 + 3.5) and (5 + (2 x 3.5)) are possible cuts
- -----
- 4.5 < 12, 2 x 4.5 < 12, 3 x 4.5 > 12, so (1 x 4.5) and (2 x 4.5) are possible cuts
- etc
Edit:
The next bit generates a solution.
It turns out the approach I used even has a wikipedia page
en.wikipedia.org
It's probably a good place to start looking for better algorithms, but I'm hoping that won't be necessary
Given the knows variables (Original size(s): 12 m in our example, and useful output sizes and numbers (10x3.5, 8x4.5, 15x5)).
Keep looping on this until all useful outputs have been produced:
- Fully allocate the "best fit" possible cuts: in this case only 5 + 3.5 + 3.5 = 12 (no waste)
- This can be done 5 times before the 3.5's are fully cut
- Step to the next available best fit, which is 2 x 5 = 10 (2 waste) and fully allocate that
- Loop until you have a solution.
Important: by starting with (5 + (2 x 3.5) ) we
lose some possibilities.
This is why we can't get an optimal solution just with this particular heuristic.
Each early selection is likely to remove some options, such as 3 x 3.5 = 10.5).
This can be handled by another simple heuristic: try multiple different starting points, starting with the best one(s) (i.e. zero waste), and e.g. moving down through a fixed number, or until efficiency is too low (e.g. 40% waste) or something like that.
This is where my earlier comment:
There are two others I'd test next that might be better
came from. The two other obvious starting points were:
A programmed solution might also try starting at (4.5 +(2 x 3.5)) and (2 x 4.5).
Trying different starting points could be added in version 0.3 (0.1 being the enumeration, 0.2 adding the first solution).
NB: even trying all the different starting points doesn't guarantee an optimal solution: starting with (3 x 3.5), but then applying "fully allocate the next best fit" could also remove some options.