I googled 'stack overflow optimized cut length' and got about what I expected, a lot of links to mathematical solutions. Apparently a lot of people have thought about this.
My math skills are not strong enough to follow the formulas, so I can only suggest finding a math wiz to work this out with you. From the bits I could understand, my guess would be your particular case might not be as difficult as some, if you only have a handful of standard lengths. It sounds like having a finite number of combinations makes the problem much more tractable.
Thank you Tom
Thank you for googling this))) and sharing with me and us.
I am hoping that maybe someone has already done something similar in FileMaker. Otherwise of course I will go the "hard" way scripting it myself. Maybe it is not so difficult as you say. I just imagine some recursive functions. But I can not say that recursive functions in FileMaker are my daily bread and I am really proficient enough in writing them. Spending more time, i would learn.
If someone showed how to best do it in FileMaker going through all combinations of possible cuts (there are not that many, yes) I really would appreciate. And I hope, many others as well.
The logic is one thing. To correctly apply is a different thing.
If there is nobody, well, then I hopefully will soon post my own solution ).
Crafting an elegant custom function can certainly be challenging and fun, but personally I'd go for a scripted approach with this, it's so much more flexible.
I will give it a try both ways and publish here if there is something useful coming up )
Suggest that you also google "Linear Programming" beforehand.
My math skills are questionable to myself. But I am giving it a try ). For simple cuts with a 90 degree straight cut in 1D it should be possible without too many problems. But when it goes into 2D or 3D .... and non-even shapes... Maybe such solution is a candidate for a plug-in.
I will look into Linear Programming.
Looking at the cutting stock problem will direct your search better than looking at linear programming, which is more general. Let me know if you'd like any help translating the solution strategies into FileMaker.
While it's certainly possible to implement solutions to this problem in a plug-in, there's nothing a plug-in can do for this that FileMaker can't, computationally speaking; and an all-FileMaker solution would be less fragile in a certain sense. FileMaker doesn't have the same supporting libraries as are available to plug-ins, but that's only because we haven't invested the effort to write the FileMaker equivalents yet. And if that's the motivation for a plug-in, we should opt for a plug-in for 1D solutions, too. Jumping to multiple dimensions makes the math more complicated, but it doesn't change anything about the relationships of the software components. FileMaker doesn't always make it easy to formulate multi-dimensional math problems, but the fact is that we have to construct FileMaker-based data structures to handle the concepts anyway just to communicate with the plug-in, and that's half the challenge solved already. We may as well keep such solutions in FileMaker to maximize portability and to minimize the number of technologies involved in maintaining the solution (thereby maximizing the number of people who can contribute).
Let us focus on the 1D task:
I call parts to be cut simply Cut's. Those parts which are used to cut from - are CutFrom's. CutFrom's usually have a fixed maximum length.
- There a pipes, or beams, from wood, plastics, steel, aluminium or whatever. This means different materials.
- Profiles have a special form, and not each side is the same. But cuts must cut correct the correct side if not 90 degrees. So, you may include the possibility an angle on each side of the Cut's with values between 0-180 degrees.
- The type of CutFrom's must be exactly the same as Cut's. They must always match.
- You have precision and also the cut itself has a dimension which is not zero.
- In the result we will have an enumeration of same types of Cut's for each CutFrom's including quantity of CutFrom's needed. (These parts may addtionally also all have an ID number, receive a custom labels, etc.)
All such data can be provided as simple text data in list form, and the result again will be in list form. We provide a list of Cut's and CutFroms' as input parameters with different attributes, and we receive a resulting list with output values (for example the sizes of all cuts and quantities of CutFroms used plus the waste generated). // Such lists must be parsed to use it with FileMaker table fields. That is not too difficult.
I also have an idea how the values (row and column data) for such lists would have to be structured.
The first resulting list would contain a calculation of the waste for each CutFrom, the quantity of CutFrom's for associated Cut's - and all that can easily be presented in a list form.
And the one combination found which produced the minimal waste is the optimized solution.
My first idea would be "brute force" running through all possible combinations. But there may be increasing Cut numbers and increasing combinations. The number of iterations would rise exponentially. Very quickly a limit might be reached. And I am sure, some limit must be set.
But for practical reasons, all seems to be solvable I have no doubt.
P.S. A related problem would be how to best pack a container or truck or store room items of varying sizes and forms in 3D using FileMaker. Or how to best cut cloth with minimal waste to produce whatever. )))
I strongly recommend you consider some of the other approaches to the cutting stock problem, and don't even consider a brute force approach. Brute force solutions to combinatorial optimization problems (of which the cutting stock problem is a subset) tend to have exponential runtimes. If perfectly optimum non-brute force algorithms turn out to be more complicated than you want to deal with, sometimes-sub-optimum-but-still-pretty-good heuristic approaches tend to be a better trade-off.
I think you're under-estimating the difficulty of arriving at a formula that gives an optimal solution and doing it brute-force is not feasible. Even more so considering that you've got a non-zero cut width and non-90 degree angles to consider. Sure, you can input values and get results, but you're hand waving over the hard part. The math is crazy here. If you can prove me wrong, I welcome it!
I think Jeremy is right, going for "optimization" is really, really hard. But doing "better than guessing" is possible. When Jeremy is saying use heuristics, I interpret that as coming up with 3-4 manageable formulas and, for a particular quote, run them all and pick the one with the best result. For example:
1) "Start with the longest length and cut those from stock, then the next longest, etc until all cuts are done"
2) "Start with the smallest length and cut those from stock, then the next smallest, etc until all cuts are done"
3) "Start with the longest length plus the next longest that is still smaller than stock, cut those, and repeat until done"
I wouldn't say the math is unmanageable (only that brute-force solution can easily take an unreasonably long time), but as someone who is especially mathematically inclined, my opinion my not be representative of what anyone else is willing to do. The math is crazy enough that it involves math no one picked up in high school, and that I'm not willing to implement for free for a forum thread, which I suppose is pretty crazy, considering.
Yes, we've been hand-waving over the hard part, but some of the meat of the last couple posts in the exchange amount to clarifying how shifting some of the work outside FileMaker does or does not make the hard part any easier. I don't mean to say that computing perfect optimum solutions is really really hard (maybe just "hard" without either of the "really"s), only that doing that computation outside of FileMaker doesn't necessarily make it much easier.
David is on to the right idea with what I meant by "heuristics." Really, I had just his #3 in mind; but comparing the results of several different computationally convenient solutions is another good meta-heuristic. A good heuristic isn't always perfect, but it can often be good enough; and can often be better than a less-disciplined human operator.
This is not necessarily intended to dissuade you from pursuing perfect optimum solutions. It's up to you to decide if the cost difference in waste between "perfect" and "pretty good" is worth the difference in development effort.
(Well, I am open to suggestions and mail to me privately in case....)
To a degree the code seems to be more or less understandable when reading it, but I am neither a mathematician nor an expert for algorithms to value such code or twist it the way possibly desired.
For me it would just be a nice intellectual challenge trying to implement existing algorithms directly into native FileMaker - if I find the time - trying to use those algorithms published already. But to develop myself a really useful algorithm would most likely be out of scope and qualification.
In case anybody is interested, here are just three example links out of many others starting from links jbante gave. I just paste them without knowing if this any good or not so good code. I just was doing a Google search:
I have been looking into linear programming, dynamic programming, heuristics, again brute force (in C/C++), and it requires significant time to even understand the concepts well and be able to port the best to something like FileMaker.
Also thank you David for nice contribution. Those different approaches are being discussed in use groups elsewhere, and reading more about it also opens the mind about their logic, difficulties, constraints, etc.
We are solution oriented ))).
While there is a correct answer and I'm with jb on this. I like to think of ways to do this with external applications IF they are able to import/export. So if you have the data in FM and push to the app, do the calcs and pull back, you may get the best of both worlds without trying to re-create within FM alone.
If there is a PHP method AND if you can use it web-published, then the exchange of data with FMP may be relatively easy.
But only you can determine what works for you.