Marcus, for the couple of dozen pieces I need to cut, I suspect a purely brute force solution would be adequate. I've only begun to think about what an extremely naive algorithm would look like.
On Fri, Sep 20, 2019 at 6:07 PM Marcus Daniels <mar...@snoutfarm.com> wrote: > > In my experience, general purpose constraint and SMT solvers tend to have > poor performance compared to linear relaxation techniques found in > mathematical optimization products like CPLEX (which also have constraints > but from a limited repertoire). It depends on the nature of your > constraints whether CPLEX will work, but I think it will for your problem. > > On 9/20/19, 3:55 PM, "Friam on behalf of Steven A Smith" > <friam-boun...@redfish.com on behalf of sasm...@swcp.com> wrote: > > Gary - > > I *patently don't* recommend my method, though it does have some > charms. I recently was faced with a similar problem to yours where I > needed to cut and install trim around the perimeter of the room (with > door openings) I just layed hardwood floor in. > > Rather than go into it in detail (I already did that and realized it was > a TL;DR as usual, so cut it) I will just say that I approach these > problems as *satisficing* and *constraint* problems rather than > *optimization*. Once I had a candidate layout, I simply looked at the > results and determined that the *waste* was acceptable. Depending on > the circumstances I sometimes prefer to have for example, 2 3' leftovers > rather than 1 5' leftover, other times, vice-versa, depending on how I > might use said leftovers in some future application (or hedging against > a mistake in my measuring/cutting). > > Care to share what your actual conduit/pipe project is? > > - Steve > > > > Thanks for the links, Peter. I will probably use that software or > > similar, to get a quick solution, then look at the MOOCs. > > > > On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp > > <piet...@randcontrols.co.za> wrote: > >> Two possible approaches are: > >> a) Solve the problem yourself. Use one or a combination of standard > algorithms ( eg you mentioned linear programming and greedy algorithms, there > are many more of course) and/or your own custom algorithm. If you wish to go > this route and want to learn about the subject, I recommend the series of > MOOCS by Stanford's Tim Roughgarden > https://www.coursera.org/specializations/algorithms > >> Or, I think yours is probably a knapsack -type problem and the MOOC > https://www.coursera.org/learn/discrete-optimization covers that relatively > well. > >> b) But if you just want to get the solution you can use optimization > software like > https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have > a free edition that will be good enough for your application) will solve it > for you without you necessarily knowing how the software does it. > >> > >> On Fri, 20 Sep 2019 at 21:00, Gary Schiltz > <g...@naturesvisualarts.com> wrote: > >>> I'd like advice on possible ways to solve the following problem > >>> (plumbers must surely face this all the time). I need to cut a set of > >>> metal tubes of varying lengths from standard length (6 meter) > >>> galvanized conduit stock. The goal is to find the number of tubes I > >>> need to buy, and the order of cuts to produce the minimum amount of > >>> leftover, unused tube. I'm interested in what types of solutions > >>> people use for similar 1-dimensional problems, e.g. linear > >>> programming, greedy algorithms, etc. (I've been Googling). I'm only > >>> looking to cut around 15-25 pieces, so my gut feeling is that an > >>> exhaustive search of all possible solutions, though probably NP-hard, > >>> would be feasible to perform. Working programs, as well as libraries > >>> in any language would be a bonus. > >>> > >>> ============================================================ > >>> FRIAM Applied Complexity Group listserv > >>> Meets Fridays 9a-11:30 at cafe at St. John's College > >>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > >>> archives back to 2003: http://friam.471366.n2.nabble.com/ > >>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > >> ============================================================ > >> FRIAM Applied Complexity Group listserv > >> Meets Fridays 9a-11:30 at cafe at St. John's College > >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > >> archives back to 2003: http://friam.471366.n2.nabble.com/ > >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > ============================================================ > > FRIAM Applied Complexity Group listserv > > Meets Fridays 9a-11:30 at cafe at St. John's College > > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > > archives back to 2003: http://friam.471366.n2.nabble.com/ > > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove