
1. Re: Looking for a function to calculate optimized cut
fitch Nov 16, 2015 5:55 PM (in response to golife)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.
Cutting stock problem  Wikipedia, the free encyclopedia
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.

2. Re: Looking for a function to calculate optimized cut
golife Nov 16, 2015 6:45 PM (in response to golife)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 ).

3. Re: Looking for a function to calculate optimized cut
fitch Nov 16, 2015 10:55 PM (in response to golife)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.

4. Re: Looking for a function to calculate optimized cut
golife Nov 17, 2015 8:33 AM (in response to fitch)I will give it a try both ways and publish here if there is something useful coming up )

5. Re: Looking for a function to calculate optimized cut
jml Nov 17, 2015 9:23 AM (in response to golife)Suggest that you also google "Linear Programming" beforehand.

6. Re: Looking for a function to calculate optimized cut
golife Nov 17, 2015 10:31 AM (in response to jml)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 noneven shapes... Maybe such solution is a candidate for a plugin.
I will look into Linear Programming.

7. Re: Looking for a function to calculate optimized cut
jbante Nov 17, 2015 12:50 PM (in response to golife)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 plugin, there's nothing a plugin can do for this that FileMaker can't, computationally speaking; and an allFileMaker solution would be less fragile in a certain sense. FileMaker doesn't have the same supporting libraries as are available to plugins, 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 plugin, we should opt for a plugin 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 multidimensional math problems, but the fact is that we have to construct FileMakerbased data structures to handle the concepts anyway just to communicate with the plugin, 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).

8. Re: Looking for a function to calculate optimized cut
golife Nov 17, 2015 5:21 PM (in response to jbante)Dear jbante
That is the original idea you express in your words: Use FileMaker. I also do not see a big problem for myself handling the FileMaker data structures as input data are simply a list of data, and output data is another list of data. To visually present cuts (for example aluminium extrusion profiles) it is another challenge, and here Javascript might help.
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 0180 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.
I have not yet solved the algorithm (whether it is scripted or a custom function or a function of a plugin or coming as a webservice or being done using JavaScript locally) needed to iterate through all the CutFrom's and possible Cut's as many times as possible to find all variations of Cut's fitting to the matching CutFrom's.
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. )))

9. Re: Looking for a function to calculate optimized cut
jbante Nov 17, 2015 6:45 PM (in response to golife)I agree that something in a web viewer (such as JavaScript) may be the best way to render a visual display of the cutting plan.
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 nonbrute force algorithms turn out to be more complicated than you want to deal with, sometimessuboptimumbutstillprettygood heuristic approaches tend to be a better tradeoff.

10. Re: Looking for a function to calculate optimized cut
DavidJondreau Nov 18, 2015 12:55 PM (in response to golife)I think you're underestimating the difficulty of arriving at a formula that gives an optimal solution and doing it bruteforce is not feasible. Even more so considering that you've got a nonzero cut width and non90 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 34 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"

11. Re: Looking for a function to calculate optimized cut
jbante Nov 18, 2015 2:47 PM (in response to DavidJondreau)I wouldn't say the math is unmanageable (only that bruteforce 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 handwaving 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 metaheuristic. A good heuristic isn't always perfect, but it can often be good enough; and can often be better than a lessdisciplined 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.

12. Re: Looking for a function to calculate optimized cut
golife Nov 18, 2015 5:09 PM (in response to jbante)(Well, I am open to suggestions and mail to me privately in case....)
I have been looking up websites suggested and also found some source code for this subject written in C#, Java, Javascript, PH, Python and C/C++, available DLLs and crossplatform solutions.
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.
If what I am reading and partially experimenting with is correct, also a seamless integration of Javascript through webviewer could be beneficial since then also a graphical representation of best cut solutions could be rendered. And in my  maybe naive  thinking, values would be handed over to Javascript where the "hard stuff" is done, and the values are returned from there. And such Javascript solutions seem to exist. No need for any plugin. But also forgetting about a native FM approach.
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:
phpCuttingStockProblem/cuttingStock.php at master · lovattj/phpCuttingStockProblem · GitHub
Cutting Stock Problem Solver Python
[C#] Board Cuttting Brute Force  Pastebin.com
For the time being I suggested to my customer using a solution from the market (50 dollars) where the to be cut list can be exported, and then the resulting solution list can be imported after it was computed, and actually that is already working fine after having tested it. It is even fast, not even a second for a list of 500 cuts, including angles and more than I could wish for. Without having to export and import it would be better since still some manual steps are required. Or using a solution calling a command line interface (console) if such external solution provides that through an available FMP plugin, or... as stated above... using existing Javascript code.
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 ))).

13. Re: Looking for a function to calculate optimized cut
jbante Nov 18, 2015 7:28 PM (in response to golife)Many FileMaker folks are excited about using JavaScript someone else has already written in a web viewer for various purposes. It's not my first instinct for math solutions, though. (It's not my first instinct for anything, really; and user interface elements are the only thing it's my second instinct for.) The folks doing solid math are much more likely to be expressing their work in Python or C++ than JavaScript, to be consistent with the conventions of the field.

14. Re: Looking for a function to calculate optimized cut
beverly Nov 18, 2015 8:08 PM (in response to jbante)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 recreate within FM alone.
If there is a PHP method AND if you can use it webpublished, then the exchange of data with FMP may be relatively easy.
But only you can determine what works for you.
beverly