Gary, If you want a quick answer to get your task done, I found a few online tools to calculate for you. eg: https://www.kurraglenindustries.com.au/linear-cutting-list-calculator.htm http://cutlist.dotordotdot.com/current https://www.cutlistoptimizer.com/
Then to study the problem later, it looks like your problem is well-known as the one-dimensional cutting stock problem <https://en.wikipedia.org/wiki/Cutting_stock_problem> and is NP-Hard. It's also equivalent to the bin packing problem. There's quite a few papers applying Ant colony optimization (ACO) as a successfu heuristic to both problems. And by golly, there's an extension to the cutting stock problem that involves welding :-) https://www.hindawi.com/journals/aor/2019/6507054/ On Sat, Sep 21, 2019 at 8:59 PM Stephen Guerin <redfishgroup...@gmail.com> wrote: > Gary, > > Thanks for posing this problem to the group - it's been fun to have in the > back of the mind for a day. I agree with Pieter that this is a kind of > knapsack problem for which Dynamic Programming is a popular approach where > you would extend to multiple knapsacks. > > I might approach it with a variant of the multiple traveling salesman > (mTSP) problem where your purchased tubes are salesman and the tubes you > want cut are cities which all need to be visited once with the constraint > to minimize the number of salesmen and the upper bound on how far each > salesman can travel (6 meters/miles). The difference of the tube cutting > model with mTSP is that the tubes aren't in a spatial layout so you would > use the length of the tube to be cut as the distance to visit that city. I > like that the edges between tubes to be cut that tend to show up in > successful solutions will get reinforced over time. Do you remember > Alberto Gallo's model from Bios where he used ant colony optimization to > solve the problem? > > A GA could also be used by indexing the tubes to be cut as genes in the > genome. > > Owen has an elegant optimization on the TSP in Agentscript just using > random swaps based on a fitness function - a kind of simulated annealing > heuristic. http://agentscript.org/models/travsalesman.html > > Another approach would be a market model where 6m tubes bid on tubes > segments and their value determined by how much a given tube would complete > their unclaimed space. This was similar to Dick Gordon's paint booth > problem at Bios bidding on cars to paint based on the cost of changing > colors. > > Stephen > > -Stephen > > On Fri, Sep 20, 2019, 5:48 PM Steven A Smith <sasm...@swcp.com> wrote: > >> Gary - >> >> I understand better now... >> >> I definitely agree that the *most* naive eyeballing methods can be >> excruciatingly wasteful. >> >> I presume that your conduit length requirements are not precise... that >> you might be designing them to allow for leaving the window partially >> open but otherwise not subject to intrusion or compromise? That seems >> to complicate the problem but may pose opportunities. In particular, >> *I* might be looking for solutions which leave me with a *minimum* of >> leftover conduit by making them longer than their shortest possibles in >> some cases. Or looking at it the other way, even if you don't need to >> leave the windows open much when "locked" a more complete use of the >> material might be obtained by relaxing the length a little without >> compromising security (if a given window can only be opened a few inches >> for example). >> >> I will be interested in hearing the results of whatever optimization (or >> satisficing) method you use yields. >> >> - Steve >> >> PS. regarding guerin's solution, an alternate would be to measure as >> suggested, then cut naively until the remaining spaces are larger than >> the remaining pieces. Only *then* does one break out the welder and >> begin to piece together as-needed. I don't think these are equivalent. >> It also occurs to me that *2* pieces of conduit (end to end, unwelded) >> in a window channel might be *nearly* as effective as a single piece, >> albeit less elegant? >> >> > Hey Steve. The actual project is nothing elaborate. My house has a >> > couple or three dozsen horizontally sliding windows with pretty weak >> > locks. Since I've had a couple of break-ins in the past, I decided >> > that the easiest way to shore up security for that aspect of the house >> > is to just cut short pieces of 3/4 inch conduit to lay horizontally in >> > the spaces where the windows slide. When I want to open a window, I >> > will just stand its conduit piece up, and when I want to "lock" it >> > again, just lay it back horizontally. I asked on FRIAM because instead >> > of just eyeballing it and having lots of extra (even potentially >> > useful in the future) pieces left over, I'd rather use my (and >> > FRIAM's) brain to look at possible ways of optimizing this. Kind of >> > fun actually putting my mind to something for a change (retirement can >> > be boring if you're not careful). >> > >> > On Fri, Sep 20, 2019 at 5:55 PM Steven A Smith <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.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