1 2 Previous Next 15 Replies Latest reply on Apr 11, 2016 12:26 PM by Siroos Jafary

    Looking for a function to calculate optimized cut

    golife

      My customer is producing windows with aluminium frames of almost any size using profiles. Aluminium profiles are extruded with a standard length of 6 meters in the factory. Now I am looking for a way (recursive loop, function...) to know how many profiles must be cut with a minimum amount of waste to fit to a certain order.

       

      Assume a list of profiles of arbitrary length, but not longer than 6 m.

       

      How in FileMaker would an algorithm be best applied to know:

       

      - What would be the best cut to produce minimal waste?

      - How many profiles from extrusion are needed?

       

      Assume for example we need 10 profiles of 1200 mm each, 10 profiles of 900 mm each, 4 profiles of 1300 mm each, and 4 profiles of 1100 mm each. We know that in total we need 30,600 mm or 30.6 m of profiles. But just cutting them from the 6 m profiles will produce some waste, more or less, depending on my cutting plan.

       

      A lot of combinations for cutting are possible, but we want the best one.

        • 1. Re: Looking for a function to calculate optimized cut
          fitch

          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

            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

              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

                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

                  Suggest that you also google "Linear Programming" beforehand.

                  • 6. Re: Looking for a function to calculate optimized cut
                    golife

                    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.

                    • 7. Re: Looking for a function to calculate optimized cut
                      jbante

                      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).

                      • 8. Re: Looking for a function to calculate optimized cut
                        golife

                        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 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.

                         

                        I have not yet solved the algorithm (whether it is scripted or a custom function or a function of a plug-in or coming as a web-service 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

                          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 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.

                          • 10. Re: Looking for a function to calculate optimized cut
                            DavidJondreau

                            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"

                            • 11. Re: Looking for a function to calculate optimized cut
                              jbante

                              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.

                              • 12. Re: Looking for a function to calculate optimized cut
                                golife

                                (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 cross-platform 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 plug-in. 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:

                                 

                                php-CuttingStockProblem/cuttingStock.php at master · lovattj/php-CuttingStockProblem · 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 plug-in, 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

                                  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

                                    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.

                                     

                                    beverly

                                    1 2 Previous Next